Project Euler 647 - Randomly Decaying Sequence

Official link: https://projecteuler.net/problem=647

Thought Process

A fun simple problem.

While doing some research I found the Putnam 1988 Problem B6 which details the Tn case. If you can figure out why the proof works, you shouldn't need anymore help on this problem!

Note: This problem can be solved if you understand the proof linked above! Try it first before you read further!


Okay if you've decided to read further, the answer is really simple, below I illustrate how the proof gets the numbers A and B.

Now we can just start at b = 1 and we can find our A and B, stop once max(A, B) > N.

All thats left is to just generalise this method

Now the problem is simple. To find Fk(N) we just start at i = 1, compute A, B, increase i until max(A, B) > N. 

Then to find the sum start at k = 3, increment by 2 each time, compute Fk(N) until it is equal to 0, then you can stop incrementing k and the problem is solved

Interactive Code

Input an integer (yourinput)

Code will output sum(Fk(yourinput)), k = 3, 5, etc