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

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, 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, 2, 3, 3, 3, 4, 3, 4, 3, 2, 3, 3, 3

Offset: 0

Author

Mike Speciner, Dec 01 2023

Keywords

• nonn
• easy

Comments

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

Examples

			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.
		

Crossrefs

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

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

Cf. A001076.

Programs

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];

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.