A367817 - OEIS

%I #6 Dec 31 2023 00:47:37

%S 0,1,1,1,2,1,2,2,1,2,2,2,2,1,2,2,2,3,2,3,2,1,2,2,2,3,2,3,3,2,3,2,3,2,

%T 1,2,2,2,3,2,3,3,2,3,3,3,3,2,3,3,3,3,2,3,2,1,2,2,2,3,2,3,3,2,3,3,3,3,

%U 2,3,3,3,4,3,4,3,2,3,3,3

%N Number of terms in a shortest sequence of Fibonacci numbers that sum to n, allowing Fibonacci numbers with negative indices.

%C a(A001076(n)) is the first occurrence of n.

%F a(0) = 0; a(A000045(n)) = 1 for n > 0.

%F For n > 0, a(n) = 1 + min(a(n-Fibonacci(k))) where k ranges over Z.

%e For n = 0, the empty sequence sums to 0, so a(0) = 0.

%e For n = 1, 2, 3, 5, 8, 13 each n is a Fibonacci number, so a(n) = 1.

%e The first n needing a negative-index Fibonacci number is 12 = 13 + -1; a(12) = 2.

%o (Python)

%o from itertools import count

%o def  a(n) :

%o   """For integer n, the least number of Fibonacci terms required to sum to n."""

%o   f = [1,2];    # Fibonacci numbers, starting with Fibonacci(2)

%o   while f[-1] <= n :

%o     f.append(f[-2]+f[-1]);

%o   a = [0 for _ in range(f[-1]+1)];

%o   for i in f :

%o     a[i] = 1;

%o   for c in count(2) :

%o     if not all(a[4:]) :

%o       for i in range(4,f[-1]) :

%o         if not a[i] :

%o           for j in f :

%o             if j >= i :

%o               break;

%o             if a[i-j] == c-1 :

%o               a[i] = c;

%o               break;

%o           if not a[i]:

%o             for j in f[::2] :

%o               if i+j >= len(a) :

%o                 break;

%o               if a[i+j] == c-1 :

%o                 a[i] = c;

%o                 break;

%o     else :

%o       break;

%o   return a[n];

%Y Cf. A000045 (Fibonacci numbers), A039834 (negative index Fibonacci numbers).

%Y Cf. A007895 (similar but with negative index Fibonacci numbers not allowed).

%Y Cf. A001076.

%K nonn,easy

%O 0,5

%A _Mike Speciner_, Dec 01 2023