Harshad数

能够被其各位数字之和整除的数称为Harshad数或Niven数。

例如201是Harshad数，因为它能被$2+1=3$整除。

截去201的最后一位数字得20，20也是Harshad数。再截去20的最后一位数字得2，也仍是Harshad数。

若一个Harshad数不断截去最后一位数字的所得的结果始终是Harshad数，则称其为可右截Harshad数。

此外$201/3=67$是素数，若一个Niven数除以其各位数字之和的结果是素数，则称其为强Harshad数。

若一个素数截去最后一位数字后所得的数是可右截强Harshad数，则称这样的素数为可右截强Harshad素数，例如素数2011就是可右截强Harshad素数。

可以验证，所有小于10000的可右截强Harshad素数之和为90619。求所有小于$10^{14}$的可右截强Harshad素数之和。

本题难度:

解答

按数位递推，显然所有的一位数都是Harshad数，以此为初始列表作深度优先搜索。

每次尝试在当前数后添加一位，若获得的还是Harshad数，就添加进列表，并检查其是否为强Harshad数，若是，再尝试添加一位并检验素性。

最终结果是$696067597313468$。

注：为减少码量，以下用sympy作素性检验，因此代码为Python 3。

import sympy

bound=10**13
q=[1,2,3,4,5,6,7,8,9]
s=0
while q:
    h=q.pop()
    for i in range(10):
        m=h*10+i
        d=sum(map(int,str(m)))
        if m%d==0:
            if m<bound:
                q.append(m)
                if sympy.isprime(m//d):
                    s+=sum(n for j in (1,3,7,9) if sympy.isprime(n:=m*10+j))
                    
print(s)