欧拉计划759:平方递归关系

〇〇

直接算1的个数，python 比上面的慢，pypy差不多
def bcnt(i):
i = i - ((i >> 1) & 0x55555555)
i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
i = (i + (i >> 4)) & 0x0f0f0f0f
i = i + (i >> 8)
i = i + (i >> 16)
return i & 0x3f

import time as tm
import math as ms

def S(n):
s=0
for i in range(1,n+1):
  s+=(i*bcnt(i))**2
return s

def S2(n):
x=int(ms.log(n,2)+1)
s=[[]]
s.append([1])
s1=5
j=3
for i in range(2,x+1):
  c=[i+1 for i in s[i-1]]
  s.append(s[i-1][:-1]+[2]+c[:-1]+[1])
  for i in s[i]:
   s1+=(i*j)**2
   j+=1;
   if(j>n):return s1

def t2(x):
t=tm.time()
print(S(x),tm.time()-t)
t=tm.time()
print(S2(x),tm.time()-t)

'''
>>> t2(10**5)
26120813588787920 0.24960041046142578
26120813588787920 0.09360027313232422
>>> t2(10**6)
38208449849768505328 2.4591405391693115
38208449849768505328 1.0412578582763672
>>> t2(10**7)
48434107237907202397536 25.46634292602539
48434107237907202397536 11.190802574157715
>>>> t2(10**6)
38208449849768505328 1.0944249629974365
38208449849768505328 1.106062889099121
>>>> t2(10**7)
48434107237907202397536 10.662099838256836
48434107237907202397536 11.151171207427979

'''

〇〇

〇〇 发表于 2021-6-13 20:18
速度比较>>>> def S2(n):....  x=int(ms.log(n,2)+1)....  s=[[]]....  s.append([1])....  s1=5....  j=3. ...

左移一位，就不用单独处理1，2了

def S3(n):
x=int(ms.log(n,2)+1)
s=[[1]]
s1=1
j=2
for i in range(1,x+1):
  #c=[i+1 for i in s[i-1]]
  s.append(s[i-1]+list(map(lambda x:1+x,s[i-1])))
  for i in s:
   s1+=(i*j)**2
   j+=1;
   if(j>n):return s1

def t2(x):
t=tm.time()
print(S3(x),tm.time()-t)
t=tm.time()
print(S2(x),tm.time()-t)

>>>> t2(10**6)
38208449849768505328 1.0776209831237793
38208449849768505328 1.0938520431518555
>>>> t2(10**7)
48434107237907202397536 11.120742797851562
48434107237907202397536 11.012107133865356