欧拉项目 | 686题 | 2的幂

原题链接

$2^7=128$是第一个以12开头的2的幂次数。下一个是$2^{80}$。
$p(L,n)$表示满足$2^j$以$L$开头的第$n$个$j$的值。所以$p(12,1)=7$，$p(12,2)=80$。
题中给出$p(123,45)=12710$以验证程序。
求$p(123,678910)$。

$2^{12710}$就是一个比较大的数字，如果使用BigInteger.ToString检查其是否以123开头还好，但是这才第45个以123开头的幂次，第678910个满足条件的幂次要大的多得多，时间也要长太多，所以我们需要一个速度更快的方式来检查。

对这个数字进行简单的处理：
$$2^j=10^d=10^{\lfloor d \rfloor}\times 10^{d-\lfloor d \rfloor}$$
而后者就是我们想要的了，整数部分是第一个数字，小数点后面分别是第二个数字和第三个数字。

double Log102 = Math.Log10(2);
var d = j * Log102;
var rem = d - (int)d;

var leading = Math.Pow(10, rem);
int num = (int)(leading * 100);

如果num == 123的话，就说明它满足条件。我依次遍历$j$，大概需要10秒时间找到第678910个，也就是题目想要的答案。

怎么优化呢？
我打印了前面几十个满足条件的$j$，然后做差得到一个数列，我发现差值只可能是196，289和485，并且289后面只能是196，196后面只能是其他两数，485后面不会是289。按照这个思路，我修改了代码，只要不到100ms就能得到结果，因为省去了上百倍的后选值$j$。

为什么只能是这三个数呢？因为它们的$d$值非常的接近整数。

>>> import math
>>> math.log(2) / math.log(10) * 196
59.001879150140304
>>> math.log(2) / math.log(10) * 289
86.99766874689055
>>> math.log(2) / math.log(10) * 485
145.99954789703085