Project Euler 686

题目

Powers of Two

$2^7=128$ is the first power of two whose leading digits are “$12$”.

The next power of two whose leading digits are “$12$” is $2^{80}$.

Define $p(L, n)$ to be the $n\text{th}$-smallest value of $j$ such that the base $10$ representation of $2^j$ begins with the digits of $L$.

So $p(12, 1) = 7$ and $p(12, 2) = 80$.

You are also given that $p(123, 45) = 12710$.

Find $p(123, 678910)$.

解决方案

将$2^k$对$10$进行取对数，那么得到$k\log{10} 2$。如果$2^k$是以$123$为开头，那么$k\log{10}2$的小数部分$d=k\log {10}2-\lfloor k\log{10}2\rfloor$满足$\log{10}1.23\le d<\log{10} 1.24$。因此，最朴素的一种做法是从小到大枚举$k$，观察$k\log_{10}2$的小数部分是否落在那个区间上即可。这个区间写成小数形式为：

$[0.08990511143939793,0.09342168516223506)\qquad(1)$

这个区间的长度为$0.0035165737228371324$

不过，朴素枚举区间的效率比较慢。暴力枚举出前一部分项后，发现相邻的两项差值总在集合$S={196, 289, 485}$中。

可以发现这几个数有以下特征：

$\begin{aligned}
&196\log{10}2=59+0.00187915014031\
&289\log{10}2=87-0.002331253109431941\
&485\log_{10}2=146-0.00045210296912046033
\end{aligned}$

后面的尾数都很小，比上面的区间长度都小。假设当前$2^a$是一个答案，也就是说，$a\log_{10}2$的小数部分$x$在区间$(1)$内。那么，

• 当$x\in[0.08990511143939793,0.09342168516223506-0.00187915014031)$时，对$a$相加$196$，那么就找到了下一个答案。
• 当$x\in[0.08990511143939793+0.002331253109431941,0.09342168516223506)$时，对$a$相加$289$，那么就找到了下一个答案。
• 当$x\in[0.08990511143939793+0.00045210296912046033,0.09342168516223506)$时，对$a$相加$485$，那么就找到了下一个答案。

并且发现，这三个条件所包括的区间的并，和原来的区间$(1)$是相同的。因此对于每个答案$a$，只需要对集合$S$中的数，从小到大尝试一遍，都将会找到答案。

枚举到第一个答案为$90$，因此从这个答案开始寻找。

注意在实现过程中，多次计算$a\log _{10}2$时，不要使用累加，因为这将会将浮点数误差累积起来。

代码

from math import log10

N = 678910
l, r = log10(1.23), log10(1.24)
lg = log10(2)
s = [196, 289, 485]
ans = 90
for _ in range(N - 1):
    for j in range(len(s)):
        val = (ans + s[j]) * lg
        if l <= val - int(val) < r:
            ans += s[j]
            break
    if j == len(s):
        print("FAIL")
        exit()
print(ans)