2^7=128是前导数字为“12”的第一个2的幂。

2^80是前导数字为“12”的第一个2的幂。

定义p(L,n)为以数字L开头的第n小的2^j的j。

所以p(12,1)=7

而p(12,2)=80。

已知P(123,45)=12710。

求P(123,678910)。

数字很大,不可以直接计算,回忆起中学用对数来求大数位数的办法。比如2^10的位数=10*lg(2)=10*0.3=3,所以科学计数法的结果就是a*10^3,于是想到用对数来解决,实际上也可能是唯一可行的办法。

import time as tm
import math as m
ta=tm.time()
tb=ta
lg123=m.log(1.23)/m.log(10)
lg124=m.log(1.24)/m.log(10)
a=0
for i in range(1,12800000000):
 t= i*lg2-m.floor(i*lg2)
 if t >= lg123 and t<lg124:
  a=a+1
  if(a>=678910):
   tb=tm.time()
   print(a,i)
   print('time cost',tb-ta,'s')
   break

执行结果
678910 193060223
time cost 197.0109851360321 s

方法有点慢,观察到相邻的满足条件的幂次差值有规律

幂次    差值
2515    196
2711    289
3000    196
3196    485
3681    196
3877    289 

大胆猜测,对所有数都是这个规律,于是有

import time as tm
import math as m
ta=tm.time()
tb=ta
lg2=m.log(2)/m.log(10)
lg123=m.log(1.23)/m.log(10)
lg124=m.log(1.24)/m.log(10)
a=0
i0=0
for i in range(1,128):
 t= i*lg2-m.floor(i*lg2)
 if t >= lg123 and t<lg124:
  a=a+1
  i0=i

while i0<12800000000:
 for gap in[196,289,485]:
  t= (i0+gap)*lg2-m.floor((i0+gap)*lg2)
  if t >= lg123 and t<lg124:
   a=a+1
   i0=i0+gap
   break
  if(a>=678910):
   tb=tm.time()
   print(a,i0)
   print('time cost',tb-ta,'s')
   exit
执行结果
678910 193060223
time cost 3.5182394981384277 s

时间约为1/50,符合预期。

至于这几个魔术数,其实都是约等于1*10^n

In[1]:= 2.0^196

                  59
Out[1]= 1.00434 10

In[2]:= 2.0^289

                  86
Out[2]= 9.94646 10

In[3]:= 2.0^485

                 145
Out[3]= 9.9896 10

PE论坛上有人还发现196=14^2, 289=17^2,485=196+289