Haha, this was too much fun, wow.
My solution only has to check the fibonacci numbers downwards starting from the biggest one smaller than the number we aim for.
I can't really write it down mathematically, but my three key insights were these:
- An equation for a number in position j of a sequence starting with a and b can be written as F(j-1)*a + F(j)*b where F is the fibonacci sequence. This means checking from above going down you can't miss an optimal solution.
- Subsequent numbers in fibonacci sequences are always coprime.
- The modular multiplicative inverse of a fibonacci number to the modulus of its following fibonacci number is always another fibonacci number.
I'm not even sure if all these are needed or if this is a good solution, but I like it.
Language: Python
def check(n):
# generate fibonacci sequence, stop when bigger than n
fib = [0,1]
while fib[-1]<n: fib.append(fib[-1]+fib[-2])
# start at biggest fibonacci number smaller than n and iterate down
for j in range(len(fib)-2,1,-1):
res = (fib[j-1-(j%2)]*n)%fib[j] # magic
if fib[j-1]*res<=n: break # a solution was found
a = int(res)
b = int((n-(res*fib[j-1]))/fib[j])
if b==0: # we dont allow 0 solutions, even if I enjoy those
b=a
j-=2
assert(n==a*fib[j-1]+b*fib[j]) # it really is a solution
seq = [a,b]
for i in range(j-1): seq.append(seq[i]+seq[i+1])
return seq
>>> check(7)
[2, 1, 3, 4, 7]
>>> check(81)
[3, 2, 5, 7, 12, 19, 31, 50, 81]
>>> check(179)
[11, 7, 18, 25, 43, 68, 111, 179]
>>> check(102334154)
[9349, 9349, 18698, 28047, 46745, 74792, 121537, 196329, 317866,
514195, 832061, 1346256, 2178317, 3524573, 5702890, 9227463,
14930353, 24157816, 39088169, 63245985, 102334154]
>>> check(102334155)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393,
196418, 317811, 514229, 832040, 1346269, 2178309, 3524578,
5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155]
If 0 were allowed, the sequence starting with 9349, 9349, ..., could be rewritten as starting with 9349, 0, 9349, 9349, ..., easily adding two extra sequence entries! :D