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

Author

Mike Speciner, Dec 31 2023

Keywords

• nonn

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).

Examples

			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.
		

Links

• Mike Speciner, graphic representation of this and 5 similar sequences
• Mike Speciner, graphic representation of this and 5 similar sequences

Crossrefs

Cf. A000032 (Lucas numbers).

Cf. A364754 (indices of record highs).

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

Cf. A058978 (for Fibonacci numbers).

Programs

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]

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.