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

0, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 2, 1, 2, 2, 2, 2, 3, 3, 2, 3, 3, 2, 1, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3, 3, 2, 1, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 1, 2, 2, 2

Offset: 0

Author

Mike Speciner, Dec 01 2023

Keywords

• nonn
• easy

Examples

			For n = 0, the empty sequence sums to 0, so a(0) = 0.
For n = 1, 2, 3, 4, 7, 11, 18, each n is a Lucas number, so a(n) = 1.
The first n needing a negative-index Lucas number is 17 = 18 + -1; a(17) = 2.
		

Crossrefs

Cf. A000032 Lucas numbers; A061084 negative index Lucas numbers.

A116543 is the similar sequence where negative index Lucas numbers are not allowed.

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

Programs

Python

from itertools import count
def  a(n) :
  """For integer n, the least number of Lucas terms required to sum to n."""
  f = [2,1];    # Lucas numbers, starting with Lucas(0)
  while f[-1] <= (n or 1) :
    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[1::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(A000032(n)) = 1.

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