小练习：20170925 齐肯多夫表示

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。

其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。

什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html

我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。

如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives

这里已经有了500余题。

                               
登录/注册后可看大图

要求：

以python语言完成，如果是python2请注明。

程序以代码文字格式发帖。

注重程序效率和创意。

答题在一周内完成，即10.2 10：00之前，其后将公开大家的答案，并评比成绩。

另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

-- 回帖需写明解题思路，鼓励在程序中加上注释 --

-- 一些鱼油反映题目有些过难，为此略过一部分偏难的题目 --

                               
登录/注册后可看大图

297

齐肯多夫表示

斐波那契数列的每一项都由前两项相加而得。
从1和2开始，前10项是：1、2、3、5、8、13、21、34、55、89。

每一个正整数可以唯一地写成斐波那契数列中非连续项的和。例如，100 = 3 + 8 + 89。
这样的和被称为数的齐肯多夫表示。

对于任意整数n>0，记z(n)为n的齐肯多夫表示中的项数。
因此，z(5) = 1，z(14) = 2，z(100) = 3，等等。
此外，对于0<n<10⁶，∑&#8201;z(n)&#8201;=&#8201;7894453。

对于0<n<10¹⁷，求∑&#8201;z(n)。

Zeckendorf Representation

Each new term in the Fibonacci sequence is generated by adding the previous two terms.
Starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

Every positive integer can be uniquely written as a sum of nonconsecutive terms of the Fibonacci sequence. For example, 100 = 3 + 8 + 89.
Such a sum is called the Zeckendorf representation of the number.

For any integer n>0, let z(n) be the number of terms in the Zeckendorf representation of n.
Thus, z(5)&#8201;=&#8201;1, z(14)&#8201;=&#8201;2, z(100)&#8201;=&#8201;3 etc.
Also, for 0<n<10⁶, ∑&#8201;z(n)&#8201;=&#8201;7894453.

Find ∑&#8201;z(n) for 0<n<10¹⁷.

jerryxjr1220

这题还是蛮简单的，求解思路是分治思想，把一个大数拆分成2个小数，递归求解，加上functools的lru_cache加速。

1. from functools import lru_cache
   
2. @lru_cache(maxsize=None)
   
3. def euler297(n, record={1: 0}):
   
4.     if n not in record:
   
5.         fib1 = fib2 = 1
   
6.         while fib1 < n:
   
7.             fib2, fib1 = fib1, fib1 + fib2
   
8.         record[n] = n - fib2 + euler297(n - fib2) + euler297(fib2)
   
9.     return record[n]
   
10. print(euler297(10 ** 17))

复制代码

2252639041804718029

gunjang

答案：2252639041804718029

1. import time
   
2. maxn = 10**17-1 #10^6 SigmaZ=7894453
   
3. st = time.time()
   
4. 
   
5. def generatorFeb(maxn):
   
6.         r = [1, 2]
   
7.         a = 1
   
8.         b = 2
   
9.         c = a + b
   
10.         while c < maxn:
    
11.                 r.append(c)
    
12.                 a, b = b, c
    
13.                 c = a + b
    
14.         return r
    
15. 
    
16. #∑Z(n) = Z(1)+Z(2)+...+Z(n)
    
17. #SigmaZ(1, feblist[i]-1) + SigmaZ(1, n-feblist[i]) + n-feblist[i]+1
    
18. #(n-feblist[i]+1) * Z(feblist[i]) = (n-feblist[i]+1) * 1
    
19. 
    
20. def calSigmaZ(maxn):
    
21.         def addSigmaZ(n, multiple, t):
    
22.                 for i in range(len(t)):
    
23.                         if t[i][0] < n:
    
24.                                 t.insert(i, (n,multiple))
    
25.                                 return t
    
26.                         elif t[i][0] == n:
    
27.                                 t[i] = (n, t[i][1]+multiple)
    
28.                                 return t
    
29.                 t.append((n, multiple))
    
30.                 return t
    
31. 
    
32.         feblist = generatorFeb(maxn)
    
33.         sigmaZlist = [(maxn,1)] #include maxn
    
34.         r = 0
    
35.         for i in range(len(feblist)-1, 1, -1):
    
36.                 t = []
    
37.                 for z in sigmaZlist:
    
38.                         if z[0] >= feblist[i]:
    
39.                                 r += (z[0]-feblist[i]+1) * z[1]
    
40.                                 t = addSigmaZ(feblist[i]-1, z[1], t)
    
41.                                 t = addSigmaZ(z[0]-feblist[i], z[1], t)
    
42.                                 #t.append(feblist[i]-1) #must merge
    
43.                                 #t.append(z-feblist[i])
    
44.                                
    
45.                         else:
    
46.                                 t = addSigmaZ(z[0], z[1], t)
    
47.                                 #t.append(z)
    
48.                 sigmaZlist = t
    
49.         for z in sigmaZlist: #z(1) z(2) z(3)
    
50.                 r += z[0] * z[1]
    
51.         return r
    
52. r = calSigmaZ(maxn)
    
53. print(maxn, r) #2252639041804718029       
    
54. print('cost {0}s'.format(time.time()-st)) #0.0004961490631103516s
    

复制代码

溪涯

sunnychou

写了一个最基础的解题方法，

1. 
   
2. def fio(number):
   
3.     x, y = 0, 1
   
4.     result = []
   
5.     while y <= number:
   
6.         result.append(y)
   
7.         x, y = y, x+y
   
8.     return result
   
9. #print(fio(20))#调用函数
   
10. 
    
11. def qiken1(mid):
    
12.     #计算一个齐肯多夫数，由几个数组成，
    
13.     a = fio(mid)
    
14.     count = 0
    
15.     #计算和为某个数的个数。计算前10**6-1次方
    
16.     for i in range(len(a)-1, 0 ,-1):
    
17.         if mid - a[i] == 0:
    
18.             count += 1
    
19.             break
    
20.         elif mid - a[i] > 0:
    
21.             mid -= a[i]
    
22.             count += 1
    
23.         else:
    
24.             i -= 1
    
25.     return count
    
26. 
    
27. def sum1(n):
    
28.     a = []
    
29.     for i in range(1, n+1):
    
30.         a.append(qiken1(i))
    
31. 
    
32.     return sum(a)
    
33. 
    
34. data = 10**6 - 1
    
35. print(sum1(data))
    

复制代码