Jeez, now I’ve solved Project Euler problems #297 and #299. I think I’m becoming an addict 😀 #299 required quite a lot of help from my friend (thank you 🙂 ) while #297 was particularly easy. I managed to code it correctly in about 15 minutes 🙂 Can you? ;D
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) = 1, z(14) = 2, z(100) = 3 etc. Also, for 0<n<10^6, ∑ z(n) = 7894453.
Find ∑ z(n) for 0<n<10^17
I wrote it using 30 lines of Python code and it takes 0.129s to compute the result for n<10^17 and 4.611s to do it for n<10^100 😀 I’ve gained access to the solutions thread and some guys are doing this in 3 (!) lines of code 😀 So I still have something to learn in this game 😉