让我们定义eleven-non-free数字：
如果我们将一个数字视为字符串，那么如果其中任何子字符串是11的（非零）幂，则此数字是一个eleven-non-free数字。
例如，1123是一个eleven-non-free数字，因为内部的11是11^1。同样，12154也是一个eleven-non-free数字，因为121是11^2。但是12345不是，因为我们找不到任何非零幂的11。
所以给定一个k，找到第k个eleven-non-free数字。例如，第13个这样的数字是211。
我不知道如何高效地做到这一点。暴力的方法是从1开始递增i，并检查每个数字并计数，直到第k个。
我想我们应该考虑具有不同长度（1、2、3、4、...）的字符串。然后对于每个长度，我们尝试填充11、11^2、11^3等，并尝试获取所有组合。
但这看起来也很复杂。
有人能提供思路吗？
好的，这花了几天时间才解决。要理解的第一件重要的事情是，欧拉谜题442唯一的具体要求是解决E（10 ^ 18）。与11-free number意味着什么的无关示例只会分散注意力。
暴力选项是不可能的，原因有2个。
它需要进行五千万亿次字符串比较，并且在大多数家用电脑上需要一周才能解决。
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...
制作此列表有两个要求。
当多个包含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^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
match #
---------------
11 260
121 18
1331 1
Calculate the total 11-containing matches in the current 10^4 range. To do this, we first have to calculate the value for the "11" match category. The 260 value above can be calculated using numbers from both the previous ranges and the separate *11 tracking operands like so:
Calculating *11 count for 10^4
260 = (18 * 10) + (8 * 10 - 0)
Combine the result of 10^4 with all the other results back to 10^2. Note: The total matches for 10^2 is 1 because there is only one 11-containing number from 0 through 100.
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());
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
N(k,s) = N(k-length(s)+length(s_0),s_0)
s_0是s的后缀，所以让我们将s写成其他字符串q和s_0的串联形式：s=[q,s_0]。现在，让r是以s开头的任何数字字符串，并再次将其写成串联形式：r=[s,r_0]=[q,s_0,r_0]。r包含一个POE作为子串，那么这个POE要么包含在r_0中，要么跨越s和r_0之间的界限。在这种情况下，s必须以POE前缀结尾，由于我们知道出现在s后缀中的最长的POE前缀是s_0，所以如果r包含POE子串，则该子串必须包含在[s_0,r_0]中。这给了我们一一对应的关系，从以s=[q,s_0]开头的ENF到以s_0开头的ENF。length(s_0)=length(s)的实例，这意味着s本身是长度小于等于k的POE的前缀。由于这样的POE前缀不算多（最多k个选择2，即O(k^2)），这个公式导致了一种有效的算法。以下是伪代码：Given a prefix s and an integer k, this function computes N(k,s)
if s contains a POE then return 10^(k-length(s))
if length(s) = k return 0
let s0 = longest POE prefix which is a suffix of s
if(length(s0)<length(s))
return N(k-length(s)+length(s0),s0)
total = 0
for d = "0" to "9"
total += N(k,concatenate(s,d))
return total
public class Eleven {
public static final String[] digits =
{"0","1","2","3","4","5","6","7","8","9"};
public static BigInteger countENF(String prefix, int k){
return countENF(prefix,k,new HashMap(),getPowers(k));
}
public static BigInteger countENF(String prefix,
int k,
// This map contains stored results for dynamic programming
// Pair is an auxiliary class that does what you think it does
Map<Pair<String,Integer>,BigInteger> resultMap,
// precomputed list of powers of 11
List<String> powers
){
// Dynamic programming case
BigInteger res = resultMap.get(new Pair(prefix,k));
if(res != null)
return res;
// base cases
if(!isEFree(prefix, powers)){
res = new BigInteger("10").pow(k-prefix.length());
resultMap.put(new Pair<>(prefix,k), res);
return res;
}
if(prefix.length() >= k){
res = new BigInteger("0");
resultMap.put(new Pair<>(prefix,k), res);
return res;
}
String s0 = getMaxPrefix(prefix, powers);
if(s0.length() < prefix.length()){
return countENF(s0,k+s0.length()-prefix.length(),resultMap,powers);
}
// recursive summation
res = new BigInteger("0");
for(String d : digits){
String s1 = prefix + d;
res = res.add(countENF(s1,k,resultMap,powers));
}
resultMap.put(new Pair<>(prefix, k), res);
return res;
}
//
// helper functions
//
// returns all POEs of at most length digits
private static List<String> getPowers(int length) {
List<String> ret = new ArrayList<>();
BigInteger val = new BigInteger("11");
BigInteger eleven = new BigInteger("11");
while(val.toString().length() <= length){
ret.add(val.toString());
val = val.multiply(eleven);
}
return ret;
}
// finds the longest string that is both a prefix of s and a suffix of a POE
private static String getMaxSuffix(String s, List<String> powers){
for(int i=s.length(); i>0; i--){
String sub = s.substring(0,i);
for(String p : powers){
if(p.endsWith(sub))
return sub;
}
}
return "";
}
public static boolean isEFree(String s, List<String> powers){
for(String p : powers){
if(s.indexOf(p)>=0)
return false;
}
return true;
}
如上所述，这个算法并不能解决OP中的确切问题。但是，修改此代码以实际找到第n个ENF数字非常简单。通过反复调用countENF，我们首先确定第n个ENF数字有多少位数，然后逐个数字从左到右确定第n个ENF的数字。
public static String getNthENF(BigInteger i){
int k = i.toString().length();
HashMap results = new HashMap();
List<String> powers = getPowers(k);
while(countENF("",k,results,powers).compareTo(i) < 0){
k++;
powers = getPowers(k);
}
String solution = "";
BigInteger total = new BigInteger("0");
while(solution.length() < k){
for(String d : digits){
BigInteger newTotal = total.add(countENF(solution + d,k,results,powers));
int comp = newTotal.compareTo(i);
if(comp >= 0){
solution = solution + d;
break;
}
total = newTotal;
}
}
return solution;
}
以下是一些示例输出，显示使用动态规划计算的第N个ENF，以及使用暴力方法计算10的幂次方。
Dynamic Programming:
10^1: 118
10^2: 1178
10^3: 11680
10^4: 115730
10^5: 1146628
10^6: 11360558
10^7: 112558960
10^8: 1115229050
10^9: 11049731548
10^10: 103258311161
10^11: 935443232311
10^12: 8576360477119
10^13: 79330786951511
10^14: 732117130575070
10^15: 6880811638385388
10^16: 64284911460844887
10^17: 610616803411054857
10^18: 5759459802926457113
10^19: 54555977711878792498
10^20: 518773721711219891634
Brute Force:
10^1: 118
10^2: 1178
10^3: 11680
10^4: 115730
10^5: 1146628
10^6: 11360558
10^7: 112558960
O(k)，但您必须非常小心才能实现这一点。有许多复杂因素会使选择下一个最小的十一个非自由数字变得困难。例如，在生成所有11xxx、121xx、1331x时，例如13121位于中间，使得任何有序数字的自动生成都很困难，更不用说在xxx数字中出现模式引起的重复性等问题。您可能最终会得到一些复杂的数据结构，每一步都需要O(log k)，因此总共需要O(k log k)。O(k log k)，与查找k个数字相同。让我们采取一个原则性的方法，逐步构建解决方案，而不是试图一次处理所有问题。
设S为11的幂序列：
11、121、1331、14641、161051、……
设E(n)为包含n的字符串表示形式作为子字符串的数字集合。您要查找的集合是S中n的E(n)的并集。
如何为某些n生成E(n)的元素？（让我们以n = 121为例。）
创建一个有向无环图，其中n是根节点。使n指向以下19个数字中的所有数字：
附加0-9：n0 n1 n2 n3 n4 n5 n6 n7 n8 n9
在1-9之前添加：1n 2n 3n 4n 5n 6n 7n 8n 9n
procedure generate_eleven_non_free
i = 1
n = 11^i
//frontier nodes; F.insert(x) does nothing if x already in F
F = empty-min-heap-set
while (true)
{
if (F.empty() or F.min() > n)
{
F.insert(n)
i = i + 1
n = 11^i
}
else
{
m = F.extractmin()
yield m
for j = 0:9
F.insert(append(m,j))
for j = 1:9
F.insert(append(j,m))
}
}
给定一个k，找到第k个十一非自由数。...是一个很大的问题。
由于这是一个耗时的问题，我写了伪代码。
var eleven_powers = [];
for (var i=0; i<1000; i++)
eleven_powers.push(Math.pow(11,i));
非十一自由数。这将涉及到大整数的处理。for (var i=11; i<Integer.MAX_VALUE; i++){
if(string(i).substring(for each of eleven_powers) == true)
store it sequentially results_array
}
取k，返回results_array[k]10^18非常大。暴力破解不是你的朋友。
然而，让我们注意一些便利：
s表示一个十一位非自由数，则d s（其中d是数字字符串）也是如此。k位数字是十一位非自由数，则可以基于有多少个k-1位数字是十一位非自由数。最后，添加一些二分搜索样式的逻辑，您应该能够找到第N个十一位非自由数是哪个数字。
x s y 而不是 x s，其中 x 或 y 可以为空（但不能同时为空，因为你已经知道 s 的状态）。否则你可能会错过像 112 这样的东西... - twalberg{11, 121, ...} 开始，如果不考虑后缀，你怎么能确定 112 属于该类呢？我同意，如果你知道 112 已经在类中，那么你添加的任何前缀也应该产生一个类的成员，但如果你只考虑前缀，你就没有生成完整的集合。你需要考虑有前缀和后缀的情况，以及有前缀和后缀的情况。 - twalbergdef add(vals, new_vals, m, val):
if val < m and val not in vals and val not in new_vals:
new_vals.append(val)
def kth11(k):
vals = [ 11**i for i in range(1, k+1) ]
new_vals = [ ]
while True:
vals = sorted(vals + new_vals)
vals = vals[:k]
m = vals[-1]
new_vals = [ ]
for v in vals:
for s in range(1, 10):
val = int(str(s) + str(v))
add(vals, new_vals, m, val)
for s in range(0, 10):
val = int(str(v) + str(s))
add(vals, new_vals, m, val)
if len(new_vals) == 0: break
return vals[-1]
print kth11(130)
这听起来像是一个分治算法。
这个问题感觉非常类似于：http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/
以及这个：http://en.wikipedia.org/wiki/Maximum_subarray_problem
当你进行分治时，将原始字符串s分成大约一半大小的两部分。在递归的底部，您需要处理小型的易于处理的问题，这些问题包含所有不包含11的字符（因为它们不包含足够的字符以内部具有任何11的幂）。
“诀窍”在于当您“向上”递归时。在此步骤中，您需要利用要查找的任何“幂”（即121）必须跨越输入字符串的“中间”的事实。
例如，当您从长度为1的字符串“向上”迈进到长度为2的字符串时，您将知道您正在寻找的某些幂位于输入字符串的第一半部分，而另一些幂位于第二半部分。