0414 Kaprekar常数
* * * *
拉格朗日计划
* * * *
Kaprekar常数

考虑自然数6174,用把它的数字按降序排列所得的数减去把它的数字按升序排列所得的数有$7641-1467=6174$。

若从任意四位数开始,不断重复上述过程,则最终或者得6174,或者得0。

若在不足四位的数前添加0使之成为四位数,再重复上述过程,则上述结论同样成立。

例如从0837开始有$8730-0378=8352$,以及$8532-2358=6174$。

由于这一性质,6174被称为Kaprekar常数。上述把排序后再相减直至到达0或Kaprekar常数的过程则称为Kaprekar路径。

对其它进制和位数,也可以考察相应的Kaprekar路径,不过并非所有情况下都存在一个唯一的Kaprekar常数,有时该路径会进入循环,有时则存在多个不同的常数。

不过可以证明,对于五位b进制数而言,只要b模6余3且$b\neq 9$,那么就存在这样一个唯一的Kaprekar常数。例如15进制下的常数为$(10,4,14,9,5)_{15}$而21进制下的常数为$ (14,6,20,13,7)_{21}$。

记$C_b$是五位b进制下的Kaprekar常数常数。并令$sb(i)$为从i出发到到达$C_b$或到达所有数字都相同的状态所需要的步数。再记 $$S(b)=\sum_{i=0}^{b^5-1}sb(i)$$ 例如$S(15)=5274369, S(111)=400668930299$。

求$\sum_{k=2}^{300}S(6k+3)$的最后18位。

本题难度:



解答

设各个数位依次是$a_0,a_1,a_2,a_3,a_4$,注意到重排后$a_2$不变,因此实际只需计算最大和最小数字之差,以及次大和次小数字之差,而在b进制下这两者的轨道长度都是有限的。

先计算出各数字对的轨道,接下来缓存各数字的Kaprekar路径长度逐个搜索即可,最终结果是$552506775824935461$。

注:因数据量较大,代码中还打印了进度信息。

target=300
mod=10**18

res=0
for k in range(2,target+1):
    x=6*k+3
    counts=[[0]*(i+1) for i in range(x)]
    for u0 in range(x):
        for v0 in range(u0+1):
            if counts[u0][v0]==0:
                cnt=1
                chain=[]
                u,v=u0,v0
                while True:
                    chain.append((u,v))
                    if u==0:
                        break
                    if v==0:
                        u1,v1=x-u,u-1
                        if v1>u1:
                            u1,v1=v1,u1
                    else:
                        d0,d1,d2,d3=sorted((u,v-1,x-u,x-1-v))
                        u1,v1=x-1-d0, d3-d1
                    if u1==u and v1==v:
                        break
                    if counts[u1][v1]:
                        cnt+=counts[u1][v1]
                        break
                    u,v=u1,v1
                    cnt+=1
                for u,v in chain:
                    counts[u][v]=cnt
                    cnt-=1
    print k,"completed" 
    res+=(sum(10*(x-u)*((2*u-1)*counts[u][0]+(3*u-1)*counts[u][u]+sum((12*v*(u-v)-2)*counts[u][v] for v in range(1, u))) for u in range(1,x))-1)%mod

print res%mod