这样的数统称为Automorphic number。
首先可以直接验证,符合题意的一位数是1,7,8。其次,若n是一个符合要求的d位数,那么
$$n^2-n=0 \pmod 14^d$$
从而$m=14^d+1-n$也符合要求。
最后,若$n_d$是一个符合要求的、能被7整除的d位数,考虑在其前面添加一位a得到的新数$n_{d+1}=a\cdot 14^d+n_d$,则有
$$n_{d+1}^2=(a\cdot 14^d+n_d)^2=a^2\cdot 14^{2d}+2an_d\cdot 14^d+n_d^2=n_d^2 \pmod{14^{d+1}}$$
由于$n_d^2$模$14^d$等于$n_d$,因此只要
$$a=\frac{n_d^2-n_d}{14^d} \bmod 14,$$
那么$n_{d+1}$就也符合要求。
按照这一规则从低位到高位生成n,一般而言m与n的各位数字之和是$13(d-1)+15$,但当$a=0$或13时m与n的位数不一致时,为避免遗漏或重复计算,在处理$n_d$时应当只记录所有满足要求的d位数的数字之和。
因此用一个变量z来记录n生成过程中各位数字之和,当$a=13$时计z作为数字和,当$a=0$时则记$13(d-1)+15-z$作为数字和,其他情况都计$13(d-1)+15$作为数字和,如此可得最终结果是$5a411d7b$。
s=1
n=0
a=7
z=0
p=1
for d in range(1,10001):
z+=a
if a==0:
s+=13*(d-1)+15-z
elif a==13:
s+=z
else:
s+=13*(d-1)+15
n+=a*p
p*=14
a=((n*n-n)/p)%14
x={10:"a",11:"b",12:"c",13:"d"}
r=""
while s:
d=s%14
r=x.get(d,str(d))+r
s=(s-d)/14
print r
|