cp's OEIS Frontend

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

%I A367817 #6 Dec 31 2023 00:47:37
%S A367817 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 A367817 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 A367817 2,3,3,3,4,3,4,3,2,3,3,3
%N A367817 Number of terms in a shortest sequence of Fibonacci numbers that sum to n, allowing Fibonacci numbers with negative indices.
%C A367817 a(A001076(n)) is the first occurrence of n.
%F A367817 a(0) = 0; a(A000045(n)) = 1 for n > 0.
%F A367817 For n > 0, a(n) = 1 + min(a(n-Fibonacci(k))) where k ranges over Z.
%e A367817 For n = 0, the empty sequence sums to 0, so a(0) = 0.
%e A367817 For n = 1, 2, 3, 5, 8, 13 each n is a Fibonacci number, so a(n) = 1.
%e A367817 The first n needing a negative-index Fibonacci number is 12 = 13 + -1; a(12) = 2.
%o A367817 (Python)
%o A367817 from itertools import count
%o A367817 def  a(n) :
%o A367817   """For integer n, the least number of Fibonacci terms required to sum to n."""
%o A367817   f = [1,2];    # Fibonacci numbers, starting with Fibonacci(2)
%o A367817   while f[-1] <= n :
%o A367817     f.append(f[-2]+f[-1]);
%o A367817   a = [0 for _ in range(f[-1]+1)];
%o A367817   for i in f :
%o A367817     a[i] = 1;
%o A367817   for c in count(2) :
%o A367817     if not all(a[4:]) :
%o A367817       for i in range(4,f[-1]) :
%o A367817         if not a[i] :
%o A367817           for j in f :
%o A367817             if j >= i :
%o A367817               break;
%o A367817             if a[i-j] == c-1 :
%o A367817               a[i] = c;
%o A367817               break;
%o A367817           if not a[i]:
%o A367817             for j in f[::2] :
%o A367817               if i+j >= len(a) :
%o A367817                 break;
%o A367817               if a[i+j] == c-1 :
%o A367817                 a[i] = c;
%o A367817                 break;
%o A367817     else :
%o A367817       break;
%o A367817   return a[n];
%Y A367817 Cf. A000045 (Fibonacci numbers), A039834 (negative index Fibonacci numbers).
%Y A367817 Cf. A007895 (similar but with negative index Fibonacci numbers not allowed).
%Y A367817 Cf. A001076.
%K A367817 nonn,easy
%O A367817 0,5
%A A367817 _Mike Speciner_, Dec 01 2023