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

Links

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

Formula

a(0) = 0; a(A000032(n)) = 1.

For n > 0, a(n) = 1+min(a(n-Lucas(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, 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.

Prog

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

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.

Sequence in context: A037196 A368594 A169818 * A116543 A256911 A347562

Adjacent sequences: A367813 A367814 A367815 * A367817 A367818 A367819

Keyword

nonn,easy

Author

Mike Speciner, Dec 01 2023

Status

approved