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
Keywords
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
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.
Comments