定义自然数完全平方数n为Sn,如果它的算术平方根等于其十进制数拆分为的各个数之和。
如:sqrt{81} = 8+1,sqrt{6724} = 6+72+4,sqrt{8281} = 8+2+81 = 82+8+1,sqrt{9801}=98+0+1
定义T(N)为n<= N的Sn之和。已知T(10^4) = 41333
求T(10^{12})
import time
def t(n,x):
if n==int(x):return 1
if n>int(x):return 0
for i in range(1,len(x)):
r= t(n-int(x[-i:]),x[:-i])
if r==1: return r
return 0
def T(n):
tm=time.time()
s=0
for i in range(9,n+1,9):
for j in [0,1]:
i+=j
z=t(i,str(i**2))*i**2
s+=z
print(time.time()-tm)
return s
n=10**6
print(T(n))
(a+b+c)^2=a*10^x+b*10^y +c
def is_sn(n):
nn=n*n
s=str(nn)
for i in range(1,len(s)):
tmp=int(s[i:])+int(s[:i])
if n==tmp: return 1
return 0
def is_sn(n):
nn=n*n
s=str(nn)
for i in range(1,len(s)):
tmp=int(s[i:])+int(s[:i])
if n==tmp: return 1
return 0
def is_sn2(n):
nn=n*n
s=str(nn)
for i in range(1,len(s)):
for j in range(i+1,len(s)):
tmp=int(s[0:i])+int(s[i:j])+int(s[j:])
if n==tmp: return 1
return 0
s=0
for i in range(1,101):
if is_sn(i)==1 or is_sn2(i)==1:
s+=i*i
print(i,i*i)
9 81
10 100
36 1296
45 2025
55 3025
82 6724
91 8281
99 9801
100 10000
235 55225
297 88209
370 136900
379 143641
414 171396
675 455625
703 494209
756 571536
792 627264
909 826281
918 842724
964 929296
990 980100
991 982081
999 998001
1000 1000000
def is_sn3(n):
nn=n*n
s=str(nn)
for i in range(1,len(s)):
for j in range(i+1,len(s)):
for k in range(j+1,len(s)):
tmp=int(s[0:i])+int(s[i:j])+int(s[j:k])+int(s[k:])
if n==tmp: return 1
return 0
s=0
for i in range(1,9001):
if is_sn(i)==1 or is_sn2(i)==1 or is_sn3(i)==1:
s+=i*i
print(i,i*i,is_sn(i),is_sn2(i),is_sn3(i),adds(i))
1000 1000000 1 1 1 1
1296 1679616 0 1 0 18
1702 2896804 0 1 0 10
1782 3175524 0 1 0 18
2223 4941729 1 0 0 9
2728 7441984 1 0 0 19
3366 11329956 0 1 0 18
3646 13293316 0 1 0 19
3682 13557124 0 1 0 19
4132 17073424 0 1 0 10
4879 23804641 1 1 0 28
4906 24068836 0 1 0 19
4950 24502500 1 0 0 18
5050 25502500 1 1 1 10
5149 26512201 0 1 1 19
5292 28005264 1 1 1 18
6832 46676224 0 1 0 19
7191 51710481 0 0 1 18
7272 52881984 1 0 0 18
7389 54597321 0 0 1 27
7533 56746089 0 0 1 18
7543 56896849 0 1 0 19
7777 60481729 1 0 0 28
8416 70829056 0 1 0 19
8767 76860289 0 1 0 28
8856 78428736 0 1 0 27
8910 79388100 0 0 1 18
8938 79887844 0 0 1 28
def adds(n):
s=0
c=str(n)
for i in range(0,len(c)):
s+=int(c[i])
return s
251名
import time
def test(N):
t=time.time()
s=0
for i in range(1,N+1):
if (adds(i)%9==0 or adds(i)%9==1) and (is_sn(i)==1 or is_sn2(i)==1 or is_sn3(i)==1 or is_sn4(i)==1 or (i>10**4 and is_sn5(i)==1) or (i>10**5 and is_sn6(i)==1)):
s+=i*i
#print(i,i*i,is_sn(i),is_sn2(i),is_sn3(i),is_sn4(i),is_sn5(i),is_sn6(i),adds(i))
print(time.time()-t)
return s
在麒麟980的m6平板上,用termux的python 3.8.3 84秒
在i3 4010上 python 3.8.3 149秒 pypy 7.3 28秒