cp's OEIS Frontend

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

%I A368594 #19 Mar 29 2025 00:23:22
%S A368594 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,
%T A368594 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,
%U A368594 3,2,3,3,2,2,2,2,1,2,2,2,2,3,3,2,3,3,3
%N A368594 Number of Lucas numbers needed to get n by addition and subtraction.
%C A368594 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).
%H A368594 Mike Speciner, <a href="/A368594/a368594.ps">graphic representation of this and 5 similar sequences</a>
%H A368594 Mike Speciner, <a href="/A368594/a368594.pdf">graphic representation of this and 5 similar sequences</a>
%F A368594 a(0) = 0; a(A000032(n)) = 1.
%F A368594 a(n) = 1 + min_{k>=0} min(a(n-Lucas(k)), a(n+Lucas(k))), for n >= 1.
%e A368594 a(0) = 0, as it is the empty sum of Lucas numbers.
%e A368594 a(1) = a(2) = a(3) = a(4) = 1, as they are all Lucas numbers.
%e A368594 a(5) = 2, since 5 = 1 + 4 = 2 + 3.
%e A368594 The first term requiring a subtraction is a(16): 16 = 18 - 2.
%o A368594 (Python)
%o A368594 from itertools import count
%o A368594 def a(n) :
%o A368594   """For integer n, the least number of signed Lucas terms required to sum to n."""
%o A368594   f = [2, 1];    # Lucas numbers, starting with Lucas(0)
%o A368594   while f[-1] <= (n or 1) :
%o A368594     f.append(f[-2]+f[-1])
%o A368594   a = [0 for _ in range(f[-1]+1)]
%o A368594   for i in f :
%o A368594     a[i] = 1
%o A368594   for c in count(2) :
%o A368594     if not all(a[4:]) :
%o A368594       for i in range(4, f[-1]) :
%o A368594         if not a[i] :
%o A368594           for j in f :
%o A368594             if j >= i :
%o A368594               break
%o A368594             if a[i-j] == c-1 :
%o A368594               a[i] = c
%o A368594               break
%o A368594           if not a[i]:
%o A368594             for j in f :
%o A368594               if i+j >= len(a) :
%o A368594                 if j != 2:
%o A368594                   break
%o A368594               elif a[i+j] == c-1 :
%o A368594                 a[i] = c
%o A368594                 break;
%o A368594     else :
%o A368594       break
%o A368594   return a[n]
%Y A368594 Cf. A000032 (Lucas numbers).
%Y A368594 Cf. A364754 (indices of record highs).
%Y A368594 Cf. A367816, A116543 (where only addition is allowed).
%Y A368594 Cf. A058978 (for Fibonacci numbers).
%K A368594 nonn
%O A368594 0,6
%A A368594 _Mike Speciner_, Dec 31 2023