algorithm - 求第 k 个非自由数

Question

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

如果我们将一个数字视为一个字符串，那么如果其中的任何子字符串是 11 的(非零)幂，那么这个数字就是 eleven-non-free数字。

例如，1123是 eleven-non-free编号为 11里面是11^1 .还有 12154是 121是 11^2 .但是12345不是，因为我们找不到 11 的任何非零幂里面。

所以给定一个 k，找到第 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 的数字意味着什么的无关示例只是分散注意力。

出于两个原因，无法使用蛮力选项。

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

Leonhard Euler 是一位数学家，因此必须在这种情况下解释问题的精神。

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

我开始尝试详细了解如何在 10 的幂之间引入包含 11 的新数字，以及是否存在可预测的模式。如果有，那么只需使用该模式来推断在任何 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...

制作这份 list 有两个要求。

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

首先根据最短的可能性进行匹配。即)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 匹配的数量。对于你们中的任何一个数学天才，可能有一个更优雅的解决方案。但是，这里是我的。

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

例子:

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

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

图 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 空闲数。

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

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

    match         #
    ---------------
    11          260
    121          18
    1331          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 变化。

将 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 人解决了问题，而 336260 人解决了问题#1。如果这个数字无缘无故地开始增长，我将删除这篇文章。

    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