由于数位增长很快，因此只保存每项的最后九位，若最后九位能形成1到9的全排列，检查前九位时使用通项公式
$$F_n=\frac{1}{\sqrt5}(\frac{1+\sqrt 5}{2})^n-\frac{1}{\sqrt5}(\frac{1-\sqrt 5}{2})^n,$$
解线性常微分方程$f''-f'-f=0$，$f(0)=f'(0)=1$，再取$F_n=f^{(n-1)}(0)$即可。该方程的解法是我国本科《高等数学》课程的标准内容。
取合适的实数t，将$F_n$写作$10^t$，则$F_n$共有$\lfloor t\rfloor+1$位，因此取其除以$10^{\lfloor t\rfloor-8}$的商就是前九位数。
此外，由于$(1-\sqrt 5)^n/2^n\to0$，因此计算前九位时只需考虑$(1+\sqrt 5)^n/2^n$即可。 结果是$329468$。
import math
x,y=math.log10((1+math.sqrt(5))/2),math.log10(1/math.sqrt(5))
def isPan(c,i):
t=i*x+y
d=str(int(10**(t-int(t)+8)))
return '0' not in c and len(set(list(c)))==9 and '0' not in d and len(set(list(d)))==9
m=10**9
a=b=i=1
while not isPan(str(a),i):
a,b,i=b,(a+b)%m,i+1
print(i)
|
