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
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
KEYWORD
nonn
AUTHOR
Mike Speciner, Dec 31 2023
STATUS
approved