A368594 Number of Lucas numbers needed to get n by addition and subtraction.

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

Offset

0,6

Comments

The definition does not require the Lucas numbers to be distinct, but it is easy to show that a(n) distinct Lucas numbers can get n by addition and subtraction, based on the identity 2*Lucas(n) = Lucas(n+1)+Lucas(n-2).

Links

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

Mike Speciner, graphic representation of this and 5 similar sequences

Mike Speciner, graphic representation of this and 5 similar sequences

Formula

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

a(n) = 1 + min_{k>=0} min(a(n-Lucas(k)), a(n+Lucas(k)), for n >= 1.

Example

a(0) = 0, as it is the empty sum of Lucas numbers.
a(1) = a(2) = a(3) = a(4) = 1, as they are all Lucas numbers.
a(5) = 2, since 5 = 1 + 4 = 2 + 3.
The first term requiring a subtraction is a(16): 16 = 18 - 2.

Prog

(Python)
from itertools import count
def a(n) :
  """For integer n, the least number of signed 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 :
              if i+j >= len(a) :
                if j != 2:
                  break
              elif a[i+j] == c-1 :
                a[i] = c
                break;
    else :
      break
  return a[n]

Crossrefs

Cf. A000032 (Lucas numbers).

Cf. A364754 (indices of record highs).

Cf. A367816, A116543 (where only addition is allowed).

Cf. A058978 (for Fibonacci numbers).

Sequence in context: A340456 A080757 A037196 * A169818 A367816 A116543

Adjacent sequences: A368591 A368592 A368593 * A368595 A368596 A368597

Keyword

nonn

Author

Mike Speciner, Dec 31 2023

Status

approved