OFFSET
0,5
COMMENTS
a(A001076(n)) is the first occurrence of n.
FORMULA
a(0) = 0; a(A000045(n)) = 1 for n > 0.
For n > 0, a(n) = 1 + min(a(n-Fibonacci(k))) where k ranges over Z.
EXAMPLE
For n = 0, the empty sequence sums to 0, so a(0) = 0.
For n = 1, 2, 3, 5, 8, 13 each n is a Fibonacci number, so a(n) = 1.
The first n needing a negative-index Fibonacci number is 12 = 13 + -1; a(12) = 2.
PROG
(Python)
from itertools import count
def a(n) :
"""For integer n, the least number of Fibonacci terms required to sum to n."""
f = [1, 2]; # Fibonacci numbers, starting with Fibonacci(2)
while f[-1] <= n :
f.append(f[-2]+f[-1]);
a = [0 for _ in range(f[-1]+1)];
for i in f :
a[i] = 1;
for c in count(2) :
if not all(a[4:]) :
for i in range(4, f[-1]) :
if not a[i] :
for j in f :
if j >= i :
break;
if a[i-j] == c-1 :
a[i] = c;
break;
if not a[i]:
for j in f[::2] :
if i+j >= len(a) :
break;
if a[i+j] == c-1 :
a[i] = c;
break;
else :
break;
return a[n];
KEYWORD
nonn,easy
AUTHOR
Mike Speciner, Dec 01 2023
STATUS
approved