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,5

Comments

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

Links

Table of n, a(n) for n=0..79.

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

Crossrefs

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

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

Cf. A001076.

Sequence in context: A215113 A058978 A105446 * A264998 A118916 A107800

Adjacent sequences: A367814 A367815 A367816 * A367818 A367819 A367820

Keyword

nonn,easy

Author

Mike Speciner, Dec 01 2023

Status

approved