查找第k十一非免费电话 [英] Find the kth eleven-non-free number
问题描述
让我们定义十一非自由编号：
如果我们考虑一个数字作为一个字符串，那么如果内部的任何字符串是一个（非零）功率 11 ，那么这个数字是一个十一非自由数。
例如， 1123 是十一非自由号 11 里面的 11 ^ 1 。此外 12154 是一个为 121 是 11 ^ 2 。但 12345 不是，因为我们找不到任何的功率非零 11 里面。
所以AK给出，找到第k 十一非自由号。例如，13这样的数字是 211 。
我不知道如何有效地做到这一点。蛮力的方法是增加我从1，检查每个数字和计数，直到第k个。
我想我们应该考虑用不同长度（1，2，3，4，...）字符串。那么对于每个长度，我们尽量填写11，11 ^ 2,11 ^ 3等，并设法让所有的组合。
但似乎相当复杂也是如此。
有人吗？
OK，这花了几天的时间才能体现出来。要了解的第一个重要的事情是，欧拉谜442从这个问题源于，唯一的具体要求，是解决为E（10 ^ 18）。什么11的免费号码是指不相关的例子只是分心。
的蛮力选项是出了问题，有两个原因。
-
这需要从字面上昆体良字符串比较，并会采取一个星期来解决大多数家用电脑。
-
欧拉是一个数学家所以问题的精神是PTED在这方面除$ P $。
过了一阵子，我开始关注模式匹配为10的权力，而不是不断，包括11个在我的算法权力。当你计算一下11的权力，你有任何有关该做的。他们只重present字符串。他们甚至不包含在最终的算法，他们只是用在侦破工作。
我开始试图让11含数字是如何将新的10国之间引入了一个详细的了解，如果有一个predictable模式。如果有，那么它也只是使用模式来推断所有之前的任何10 ^停止点引入的11含号码的问题。
了解主要概念
有关每个新的10 ^达到，previous 11 ^串匹配的数目是相同的previous 10 ^范围。它更容易用图表来解释。
下面是10 ^ 2列表 - 显示到目前为止介绍，并分组由11 ^号码匹配字符串新的11-包含数字的计数10 ^ 6。
图1）的11 ^匹配号码在10 ^范围由11 ^字符串匹配分组
---------------------------
10 ^ 2范围内（10 - 100）
---------------------------
11 1
---------------------------
10 ^ 3范围内（100 - 1000）
---------------------------
11月18日
121 1
---------------------------
10 ^ 4的范围（1000 - 10000）
---------------------------
11 260
121 18
1331 1
---------------------------
10 ^ 5范围（10000 - 100000）
---------------------------
11 3392
121 260
1331 18
14641 1
---------------------------
10 ^ 6系列（100000 - 1000000）
---------------------------
11 41760
121 3392
1331 260
14641 18
161051 1
等等...
有制作这个名单的两个要求。
-
在11多含数字顺序匹配（如11000 - 11999）所有这些项目都必须归功于11 ^组的首场比赛中。这意味着，即使将有该实施例121和1331匹配，该范围内的所有的匹配都归于11，因为它是第一个。
-
匹配是基于最短的可能性，首次提出。如）11，121，1331，等等。这是因为有些数字匹配多个11 ^字符串，而其他出现的连续的范围之内。而且，从高匹配他们低不会产生predictable模式。功能上，它都是一样的。这只是带来了一大堆的清晰度进入画面。
请注意，在每一个新的10 ^范围内，只有1个新的11 ^匹配出台。并且，对于每一个previous 11 ^号码匹配的数目是相同的，而不管previous功率。这里的困难是，* 11串匹配的数目不能直接从previous功率的推断。
图2）区分等11 ^模式从* 11比赛
**** 11
*** 110模式
** 1100模式
* 11000模式
110000模式
等等...
所有的模式匹配的是高度在10 ^权力predictable。只有* 11数字并不明显他们是如何积累。这是不是真的，有没有一种模式，问题是，你必须是被扫描的从右到左presume数字和，结果，没有如果其他的模式将是predictable了。
事实证明，一个单独的蓄能器，必须同时跟踪，使我们能够使用previous * 11场比赛来计算新的* 11场比赛的数量。对于任何你数学天才在那里，有可能是一个更好的解决方案。但是，这里是我的。
您必须始终保持独立的人数轨道*从 previous 11场比赛2 的权力。使用这些作为操作数，就可以计算* 11匹配的数目为当前功率
例如：
的* 11场比赛中的10 ^ 3范围内的数字是8。还有10场比赛的110，但他们不事在这里，我们只是跟踪以11结尾的号码。所以，我们开始用2 previous * 11的比赛计数是8和0的 2 previous 10 ^范围。
重要提示：对于任何数量小于10 ^ 2，0是previous匹配计数此计算。这就是为什么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次幂
==================================
＃公式10 ^ 4
==================================
80 ** 11 = 8 * 10 - 0
80 * 110模式= previous电源的* 11次10
100 1100模式= previous功率的110倍10
==================================
260总的范围相匹配
==================================
＃公式10 ^ 5
==================================
792 *** 11 = 80×10 - 8
800 ** 110模式= previous功率的** 11倍10
800 * 1100模式= previous电源的* 110倍10
1000年11000模式= previous电源的1100倍10
==================================
3392达尔范围相匹配
在这些实施例中，只有* 11号，必须分别计算。看到堆放有点像这样，这些数字使得它感觉比它更复杂的。这是唯一重要的是要理解这个概念。在实践中，我们抽象出以外的所有* 11计算通过累积乘法。
现在，在我们进入了一个工作算法，最后要在概念上理解是如何使用这些模式来计算第N个11免费电话号码在每个^ 10结束。
这是一个两步骤的过程，所以我将演示使用的一个例子。让我们看看1000 - 10000范围从图1 10000是10 ^ 4所以这是我们正在解决的范围
下面11 ^基团是所有在该范围内。在18和1可以从previous权力来导出（参照图1）。
比赛＃
---------------
11 260
121 18
1331年1
-
计算总的11场比赛包含在目前的10 ^ 4的范围。要做到这一点，我们首先要计算为11的比赛类别的价值。在260以上的价值可以用数字从计算的两个的previous范围和单独的* 11的跟踪操作数，像这样：
计算* 11数为10 ^ 4
= 260（18 * 10）+（8×10 - 0）- 其中18所有11比赛的总（不一定* 11）从10 ^ 3范围内（参见图1）。
- 10的为常数。
- 和7,8和0是我们的出发点，提到previously，分开计算* 11的变化。
-
联合收割机10 ^ 4的结果与所有其他结果返回到10 ^ 2。 注意：的总比赛为10 ^ 2为1，因为只有一个11-含到100 0号
。共11个含10 ^ 4范围内的数字：279 = 260 + 18 + 1 共有10 ^ 4范围内加previous总计：299 = 279 + 19 + 1 --------------------- 10 ^ 4解决：9701 = 10 ^ 4 - 299
一个工作算法
下面是用C＃编写，解决每个10 ^ 1〜10 ^ 18的算法。它返回几乎瞬间。出于对项目欧拉的我没有直接发布解决他们的难题。输出是准确的，但。眼下只有＃442问题表明163人已经解决了这个问题相比，336260人解决问题＃1。如果这个数字开始增长没有任何理由，我会删除这个帖子。
私人ULONG GetNthElevenFreeForPow10（UINT POW）{
如果（POW＆GT; 18）
抛出新的ArgumentException（参数必须是1到18之间的正整数，POW）;
//所有的数字高达10 ^ 0＆安培; 10 ^ 1 11-免费
//如果1被认为是11免费为欧拉问题
// 状态。
如果（POW == 0 ||战俘== 1）
返程（ULONG）Math.Pow（10，POW）;
// 11S的序列不形成一个可重复的图案
//直到10 ^ 4，因为它需要回溯到
//计算运行总计。
如果（POW == 2）
返程（ULONG）Math.Pow（10，POW） - 1;
如果（POW == 3）
回报（ULONG）Math.Pow（10，POW） - （18 + 1 + 1）;
//在每个新的功率产生7-11的数目是
//轻易predicted基础上，previous力量。但，
//与11即结束的新条目）的数量xxx11
//是有点棘手。它需要一个回望的
// 2 previous权力。此数组存储回顾
//用于使该计算操作数。
ULONG [] lookbackOperands =新ULONG [] {
0,8
};
//这个数是用来计算全部11个含有新的
//为每个功率数。接下来的权力始终是一个计算
//在previous。
ULONG elevensConsumedCurrent = 18;
ULONG elevensConsumed previous = 18 + 1;
//这个数字拥有含11所有运行总和
//数字到目前为止所消耗。
ULONG elevensConsumedTotal = 20;
对于（INT N = 4; N＆LT; =战俘; N ++）{
//计算新项目的数量补充说，年底以11。
ULONG endsWith11Current = lookbackOperands [1] * 10 - lookbackOperands [0];
lookbackOperands [0] = lookbackOperands [1];
lookbackOperands [1] = endsWith11Current;
elevensConsumedCurrent = elevensConsumedCurrent * 10 + endsWith11Current;
elevensConsumed previous + = elevensConsumedCurrent;
elevensConsumedTotal + = elevensConsumed previous;
}
返程（ULONG）Math.Pow（10，POW） - elevensConsumedTotal;
}
用法：
StringBuilder的SB =新的StringBuilder（）;
对于（UINT N = 1; N＆LT; = 18; N ++）
sb.AppendLine（的String.Format（
第N个11免费号码@ 10 ^ {0} \ t {1}，
N，
GetNthElevenFreeForPow10（N）的ToString（）
）
）;
Console.WriteLine（sb.ToString（））;
下面是第15。
11 N次的免费号码@ 10 ^ 110
第N个11免费号码@ 10 ^ 2 99
第N个11免费号码@ 10 ^ 3 980
第N个11免费号码@ 10 ^ 4 9701
第N个11免费号码@ 10 ^ 5 96030
第N个11免费号码@ 10 ^ 6 950599
第N个11免费号码@ 10 ^ 7 9409960
第N个11免费号码@ 10 ^ 8 93149001
第N个11免费号码@ 10 ^ 9 922080050
第N个11免费号码@ 10 ^ 10 9127651499
第N个11免费号码@ 10 ^ 11 90354434940
第N个11免费号码@ 10 ^ 12 894416697901
第N个11免费号码@ 10 ^ 13 8853812544070
第N个11免费号码@ 10 ^ 14 87643708742799
第N个11免费号码@ 10 ^ 15 867583274883920
Let's define eleven-non-free numbers:
If we consider a number as a string, then if any substring inside is a (non-zero) power of 11, then this number is an eleven-non-free number.
For example, 1123 is an eleven-non-free number as 11 inside is 11^1. Also 12154 is one as 121 is 11^2. But 12345 is not, because we can't find any non-zero power of 11 inside.
So given a k, find the kth eleven-non-free number. For example the 13th such number is 211.
I don't know how to efficiently do it. the brute-force way is to increase i from 1 and check every number and count until the kth.
I guess we should consider strings with different length (1, 2, 3, 4, ...). then for each length, we try to fill in 11, 11^2, 11^3, etc and try to get all the combinations.
But it seems quite complicated as well.
Anyone?
OK, this took several days to figure out. The first important thing to understand is that the only concrete requirement of the euler puzzle 442 that this question stems from is to solve for E(10^18). The unrelated examples of what an 11-free number means are just distractions.
The brute force option is out of the question, for 2 reasons.
It requires literally a quintilian string comparisons and would take a week to resolve on most home computers.
Leonhard Euler was a mathematician so the spirit of the question has to be interpreted in that context.
After a while, I started focusing on pattern matching for powers of 10, instead of continually including powers of 11 in my algorithms. After you calculate what the powers of 11 are, you're done with anything related to that. They only represent strings. They aren't even included in the final algorithm, they are just used in the detective work.
I started trying to get a detailed understanding of how new 11-containing numbers are introduced between powers of 10 and if there was a predictable pattern. If there was, then it would just be a matter of using that pattern to deduce all of the 11-containing numbers introduced prior to any 10^ stopping point.
Understanding the Main Concepts
For each new 10^ reached, the number of previous 11^ string matches are identical to the previous 10^ range. It's easier to explain with a chart.
Here is a list of 10^2 - 10^6 that shows the count of new 11-containing numbers introduced so far and grouped by the 11^ number that matched the string.
Fig 1.) Number of 11^ matches in 10^ ranges grouped by 11^ string match
---------------------------
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...
There are two requirements for making this list.
When multiple 11-containing numbers are match sequentially (like 11000 - 11999) all of those items must be attributed to the 11^ group of the first match. Meaning that even though there will be matches for 121 and 1331 in that example, all matches in that range are attributed to 11, because it is first.
Matches are made based on the shortest possibility first. i.e.) 11, 121, 1331, etc... This is because some numbers match multiple 11^ strings while others appear inside of a contiguous range. And, matching them from high to low doesn't produce a predictable pattern. Functionally, it's all the same. This just brings a whole lot of clarity into the picture.
Notice that in each new 10^ range, only 1 new 11^ match is introduced. And, the number of matches for each previous 11^ number is identical, regardless of the previous power. The difficulty here is that the number of *11 string matches can't be directly inferred from the previous power.
Fig 2.) Differentiating other 11^ patterns from the *11 match
****11
***110 pattern
**1100 pattern
*11000 pattern
110000 pattern
etc...
All of the "pattern" matches are highly predictable within 10^ powers. Only the *11 numbers are not obvious in how they accumulate. It's not really that there isn't a pattern, the problem is that you would have to presume numbers that were scanned right to left and, as a result, none if the other patterns would be predictable anymore.
As it turns out, a separate accumulator has to be tracked concurrently that allows us to use the previous *11 matches to calculate the number of new *11 matches. For any of you math geniuses out there, there may be a more elegant solution. But, here is mine.
You have to always be separately keeping track of the number of *11 matches from the previous 2 powers. Using these as operands, you can calculate the number of *11 matches for the current power.
Example:
The number of *11 matches in the 10^3 range is 8. There are also 10 matches on "110" but they don't matter here, we are just tracking numbers that end with "11". So, we are starting with the 2 previous *11 match counts being 8 and 0 from the 2 previous 10^ ranges.
Important: For any number less than 10^2, 0 is the previous match count for this calculation. That is why 0 is the second look-back operand when working with 10^3.
Fig 3.) How to calculate *11 match counts per 10^ range using back-tracking
10^3 | 80 = 8 * 10 - 0;
10^4 | 792 = 80 * 10 - 8;
10^5 | 7840 = 792 * 10 - 80;
This number however is only useful by looking at it, again, from a different perspective.
Fig 4.) Illustration of how match groups scale by powers of 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
In these examples, only the *11 number has to be calculated separately. Seeing these numbers stacked like this sort of makes it feel more complicated than it is. It's only important to understand the concept. In practice, we abstract out everything except the *11 calculation through cumulative multiplication.
Now, before we get into a working algorithm, the last thing to understand conceptually is how to use these patterns to calculate the Nth 11-free number ending at each ^10.
This is a two step process so I'll demonstrate using an example. Lets look at the 1000 - 10000 range from Fig 1. 10000 is 10^4 so that is the range we are solving for.
The following 11^ groups are all within that range. The 18 and the 1 can be derived from the previous powers (see Fig 1).
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)- Where 18 is the total of all "11" matches (not necessarily *11) from the 10^3 range (see Fig 1).
- The 10's are constants.
- And, 8 and 0 are our starting points, mentioned previously, for separately calculating *11 changes.
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
A Working Algorithm
Here is an algorithm written in C# that solves for each of 10^1 through 10^18. It returns almost instantly. Out of respect for project euler I didn't post the answer to their puzzle directly. The output is accurate though. Right now the #442 question only shows 163 people have solved the problem compared to 336260 people solving problem #1. If that number starts growing for no reason, I will delete this post.
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;
}
Usage:
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());
Here are the first 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
这篇关于查找第k十一非免费电话的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
