0315 数根时钟
* * * *
拉格朗日计划
* * * *
数根时钟

张三和李四需要将两个数字时钟改装成两个数根时钟。所谓数根时钟就是不断迭代计算给定数字的数根(注:即该数的各位数字之和)的时钟。

当时钟接收到一个数时,它会先显示这个数,然后开始计算其数根,再此数根作为新的输入,直至计算结果不再变化为止。

例如若时钟接收到137,则它会依次显示137,11,和2,然后它会黑屏并等待接收下一个数。

钟面的数字用七段数码管显示,七段数码管由上、中、下三根水平数码管和左上、右上、左下、右下四根竖直数码管构成。

各数字的显示可以参考下图最后一行:



数码管只在打开或关闭时才消耗能量,因此,从黑屏显示2需要5点能量,而从黑屏显示显示7则只需要4点能量。

张三(上图左)和李四(上图右)制作了两个不同的时钟,每次显示不同的数时,张三总是先黑屏再显示新数,而李四则只切换必要的数码管的状态。

例如在上例中张三需要依次显示和关闭137,11和2,共需消耗$(2+5+4)\times 2+(2 + 2)\times 2+5\times 2=40$点能量。

而李四则需要先显示137,再关闭和打开最少的数码管将显示切换到11,再用同样的方式将显示切换到2,最后关闭所有能量管,共需消耗$11+7+3+4+5=30$点能量。

显然,李四的时钟更节能。

若两时钟会依次接收到$10^7$和$2\times 10^7$之间的所有质数,求张三比李四多消耗的能量值。

本题难度:



解答

本题只需要按规则模拟即可。

生成显示每个数字所需要的能量,以及不同数字间转换时所需要的能量。

再生成给定范围内的素数及其对应的数跟序列分别计算双方的能量,最终结果是$13625242$。

注:以下代码为Python 3,且打印了进度信息。

注2:本人使用的Python 3版本是3.9,使用3.10及其以后版本的可以在第15行改为直接使用i^j.bit_count()函数。

target=20000000
d=[0]*target
n=2
while n < target:
    for i in range(n*n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1

print("prime sieve ready")

switchs=[6,2,5,5,4,5,6,4,7,6]
s=[int(i,2) for i in ["1110111","0010010","1011101","1011011","0111010","1101011","1101111","1110010","1111111","1111011"]]
transitions=[[sum(k=="1" for k in format(i^j,"b")) for j in s] for i in s]

digitRoot=lambda x:sum(int(i) for i in str(x))
onOff=lambda x:sum(switchs[int(i)] for i in str(x))

sam=marks=0

for p in range(10000000,target):
    if d[p]==0:
        q=[p]
        while digitRoot(q[-1])!=q[-1]:
            q.append(digitRoot(q[-1]))
        sam+=sum(onOff(r)*2 for r in q)
        marks+=onOff(q[0])+onOff(q[-1])
        for i in range(len(q)-1):
            a=[int(j) for j in str(q[i])][::-1]
            b=[int(j) for j in str(q[i+1])][::-1]
            marks+=sum(transitions[a[j]][b[j]] if j < len(b) else switchs[a[j]] for j in range(len(a)))
    if (p-10000000)%100000==0:print((p-10000000)//100000,"percent completed")

print(sam-marks)