找到第k个十一 - 非免费号码

Question

我们来定义eleven-non-free数字:

如果我们将数字视为一个字符串,那么如果内部的任何子字符串是(非零)幂11,则该数字是一个eleven-non-free数字.

例如,内部是1123一个eleven-non-free数字.同样是一个为是.但事实并非如此,因为我们无法找到任何内部的非零力量.1111^11215412111^21234511

所以给定ak,找到第k个eleven-non-free数字.例如,第13个这样的数字是211.

我不知道如何有效地做到这一点.蛮力的方法是将i从1增加并检查每个数字和计数直到第k个.

我想我们应该考虑不同长度的字符串(1,2,3,4,...).然后对于每个长度,我们尝试填写11,11 ^ 2,11 ^ 3等,并尝试获得所有组合.

但它似乎也很复杂.

任何人？

Answer 1

好吧，这花了几天时间才弄清楚。首先要理解的是，这个问题所源于的欧拉难题 442 的唯一具体要求是求解 E(10^18)。与 11 自由数字的含义无关的例子只是分散注意力。

由于两个原因，暴力选项是不可能的。

1. 它实际上需要进行五次字符串比较，并且在大多数家用计算机上需要一周的时间才能解决。

2. 莱昂哈德·欧拉是一位数学家，因此必须在这种背景下解释问题的精神。

一段时间后，我开始专注于 10 次方的模式匹配，而不是在我的算法中不断包含 11 次方。当你计算出 11 的幂后，你就完成了与此相关的任何事情。它们仅代表字符串。它们甚至没有包含在最终的算法中，它们只是用于侦探工作。

我开始尝试详细了解新的包含 11 的数字是如何在 10 的幂之间引入的，以及是否存在可预测的模式。如果存在，那么只需使用该模式来推断在任何 10^ 停止点之前引入的所有包含 11 的数字即可。

理解主要概念

对于每个新达到的 10^，前一个 11^ 字符串匹配的数量与前一个 10^ 范围相同。用图表更容易解释。

以下是 10^2 - 10^6 的列表，显示了迄今为止引入的新的包含 11 的数字的计数，并按与字符串匹配的 11^ 数字进行分组。

图 1.)按 11^ 字符串匹配分组的 10^ 范围内的 11^ 匹配数

---------------------------
10^2 range (10 - 100)
---------------------------
    11            1
---------------------------
10^3 range (100 - 1000)
---------------------------
    11           18
    121           1
---------------------------
10^4 range (1000 - 10000)
---------------------------
    11          260
    121          18
    1331          1
---------------------------
10^5 range (10000 - 100000)
---------------------------
    11         3392
    121         260
    1331         18
    14641         1
---------------------------
10^6 range (100000 - 1000000)
---------------------------
    11        41760
    121        3392
    1331        260
    14641        18
    161051        1

etc...

制作此列表有两个要求。

1. 当多个包含 11 的数字按顺序匹配时（例如 11000 - 11999），所有这些项目都必须归因于第一个匹配的 11^ 组。这意味着即使在该示例中存在 121 和 1331 的匹配，该范围内的所有匹配都归因于 11，因为它是第一个。

2. 首先根据最短的可能性进行匹配。即）11、121、1331 等...这是因为某些数字匹配多个 11^ 字符串，而其他数字则出现在连续范围内。而且，从高到低匹配它们不会产生可预测的模式。从功能上来说，都是一样的。这只会让图片变得更加清晰。

请注意，在每个新的 10^ 范围中，仅引入 1 个新的 11^ 匹配。并且，无论之前的幂次如何，前一个 11^ 数字的匹配数都是相同的。这里的困难在于 *11 字符串匹配的数量不能直接从先前的幂推断出来。

图 2.)将其他 11^ 模式与 *11 匹配区分开来

    ****11
    ***110 pattern
    **1100 pattern
    *11000 pattern
    110000 pattern
    etc...

所有“模式”匹配在 10^ 次方内都是高度可预测的。只有 *11 数字的累积方式并不明显。并不是真的没有模式，问题是您必须假设从右到左扫描的数字，因此，如果其他模式不再可预测，则没有任何模式。

事实证明，必须同时跟踪一个单独的累加器，它允许我们使用之前的 *11 匹配来计算新的 *11 匹配的数量。对于任何数学天才来说，可能有一个更优雅的解决方案。但是，这是我的。

您必须始终单独跟踪前 2 次幂的 *11 匹配次数。使用这些作为操作数，您可以计算当前功率的 *11 匹配数。

例子：

10^3 范围内 *11 匹配的数量为 8。“110”上也有 10 个匹配，但它们在这里并不重要，我们只是跟踪以“11”结尾的数字。因此，我们从前 2 个10^ 范围中的前 2 个 *11 匹配计数开始，分别为 8 和 0 。

重要提示：对于任何小于 10^2 的数字，0 是此计算的先前匹配计数。这就是为什么 0 是使用 10^3 时的第二个回顾操作数。

图 3.)如何使用回溯计算每 10^ 范围 *11 匹配计数

    10^3 |   80 = 8 * 10 - 0;
    10^4 |  792 = 80 * 10 - 8;
    10^5 | 7840 = 792 * 10 - 80;

然而，只有从不同的角度来看这个数字才有用。

图 4.)说明匹配组如何按 10 的幂缩放

    ==================================
      #    Formulas for 10^4
    ==================================
     80    **11         = 8 * 10 - 0
     80    *110 pattern = previous power's *11 times 10
    100    1100 pattern = previous power's 110 times 10
    ==================================
    260   Total matches in range

    ==================================
       #  Formulas for 10^5
    ==================================
     792  ***11         = 80 * 10 - 8
     800  **110 pattern = previous power's **11 times 10
     800  *1100 pattern = previous power's *110 times 10
    1000  11000 pattern = previous power's 1100 times 10
    ==================================
    3392  Total matches in range

在这些示例中，仅需要单独计算 *11 数字。看到这些数字像这样堆积起来，让人感觉比实际情况更复杂。理解这个概念很重要。在实践中，我们通过累乘抽象出了除 *11 计算之外的所有内容。

现在，在我们进入工作算法之前，从概念上理解的最后一件事是如何使用这些模式来计算以每个 ^10 结尾的第 N 个 11-free 数字。

这是一个两步过程，因此我将使用示例进行演示。让我们看看图 1 中的 1000 - 10000 范围。10000 是 10^4，所以这就是我们要求解的范围。

以下 11^ 组均在该范围内。18 和 1 可以从之前的幂中导出（见图 1）。

    match         #
    ---------------
    11          260
    121          18
    1331          1

1. 计算当前 10^4 范围内总共包含 11 个的匹配项。为此，我们首先必须计算“11”匹配类别的值。上面的 260 值可以使用先前范围中的数字和单独的 *11 跟踪操作数来计算，如下所示：

   计算 10^4 的 *11 计数

       260 = (18 * 10) + (8 * 10 - 0)        
   

   • 其中 18 是 10^3 范围内所有“11”个匹配项（不一定是 *11）的总和（见图 1）。
   • 10 是常数。
   • 并且，8 和 0 是我们前面提到的起点，用于分别计算 *11 变化。

2. 将 10^4 的结果与所有其他结果合并回到 10^2。注意： 10^2 的总匹配数为 1，因为 0 到 100 中只有一个包含 11 的数字。

   Total 11-containing numbers in 10^4 range:  279 = 260 + 18 + 1
   Total 10^4 range plus previous totals    :  299 = 279 + 19 + 1
                                              ---------------------
                                 10^4 solved: 9701 = 10^4 - 299
   

有效的算法

以下是用 C# 编写的算法，可求解 10^1 到 10^18 中的每一个。它几乎立即返回。出于对欧拉项目的尊重，我没有直接发布他们的难题的答案。但输出是准确的。目前，#442 问题仅显示 163 人解决了该问题，而解决问题 1 的人数为 336260 人。如果这个数字无缘无故地开始增长，我将删除这篇文章。

    private ulong GetNthElevenFreeForPow10(uint pow){

        if(pow > 18)
            throw new ArgumentException("Argument must be a positive integer between 1 and 18", "pow");

        // All of the numbers up to 10^0 & 10^1 are 11-free
        // if 1 is considered 11-free as the euler question 
        // states.
        if (pow == 0 || pow == 1)
            return (ulong)Math.Pow(10, pow);

        // The sequence of 11s doesn't form a repeatable pattern
        // until 10^4 because it requires back tracking to 
        // calculated running totals.
        if (pow == 2)
            return (ulong)Math.Pow(10, pow) - 1;

        if (pow == 3)
            return (ulong)Math.Pow(10, pow) - (18 + 1 + 1);

        // At each new power the number of elevens created is 
        // easily predicted based on the previous power. But, 
        // the number of new entries ending with 11 i.e.) xxx11
        // is a little trickier. It requires a lookback at the 
        // two previous powers. This array stores the lookback 
        // operands used to make that calculation.
        ulong[] lookbackOperands = new ulong[] { 
            0, 8
        };

        // this number is used to calculate all of the new 11-containing 
        // numbers for each power. The next power is always a calculation 
        // on the previous.
        ulong elevensConsumedCurrent = 18;
        ulong elevensConsumedPrevious = 18 + 1;

        // this number holds a running total all 11-containing
        // numbers consumed so far.
        ulong elevensConsumedTotal = 20;

        for (int n = 4; n <= pow; n++) {
            // Calculate the number of new items added that end with "11".
            ulong endsWith11Current = lookbackOperands[1] * 10 - lookbackOperands[0];
            lookbackOperands[0] = lookbackOperands[1];
            lookbackOperands[1] = endsWith11Current;

            elevensConsumedCurrent = elevensConsumedCurrent * 10 + endsWith11Current;
            elevensConsumedPrevious += elevensConsumedCurrent;
            elevensConsumedTotal += elevensConsumedPrevious;
        }

        return (ulong)Math.Pow(10, pow) - elevensConsumedTotal;

    }

用法：

        StringBuilder sb = new StringBuilder();
        for (uint n = 1; n <= 18; n++)
            sb.AppendLine(String.Format(
                    "Nth 11-Free Number @ 10^{0}\t{1}", 
                    n, 
                    GetNthElevenFreeForPow10(n).ToString()
                )
            );

        Console.WriteLine(sb.ToString());

这是前 15 个。

Nth 11-Free Number @ 10^1   10
Nth 11-Free Number @ 10^2   99
Nth 11-Free Number @ 10^3   980
Nth 11-Free Number @ 10^4   9701
Nth 11-Free Number @ 10^5   96030
Nth 11-Free Number @ 10^6   950599
Nth 11-Free Number @ 10^7   9409960
Nth 11-Free Number @ 10^8   93149001
Nth 11-Free Number @ 10^9   922080050
Nth 11-Free Number @ 10^10  9127651499
Nth 11-Free Number @ 10^11  90354434940
Nth 11-Free Number @ 10^12  894416697901
Nth 11-Free Number @ 10^13  8853812544070
Nth 11-Free Number @ 10^14  87643708742799
Nth 11-Free Number @ 10^15  867583274883920