

A368594


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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


LINKS



FORMULA

a(n) = 1 + min_{k>=0} min(a(nLucas(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[ij] == c1 :
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] == c1 :
a[i] = c
break;
else :
break
return a[n]


CROSSREFS

Cf. A364754 (indices of record highs).
Cf. A058978 (for Fibonacci numbers).


KEYWORD

nonn


AUTHOR



STATUS

approved



