cp's OEIS Frontend

A367816 Number of terms in a shortest sequence of Lucas numbers that sum to n, allowing Lucas numbers with negative indices.

%I A367816 #8 Dec 31 2023 00:47:26
%S A367816 0,1,1,1,1,2,2,1,2,2,2,1,2,2,2,2,3,2,1,2,2,2,2,3,3,2,3,3,2,1,2,2,2,2,
%T A367816 3,3,2,3,3,3,2,3,3,2,3,3,2,1,2,2,2,2,3,3,2,3,3,3,2,3,3,3,3,4,3,2,3,3,
%U A367816 3,3,4,3,2,3,3,2,1,2,2,2
%N A367816 Number of terms in a shortest sequence of Lucas numbers that sum to n, allowing Lucas numbers with negative indices.
%F A367816 a(0) = 0; a(A000032(n)) = 1.
%F A367816 For n > 0, a(n) = 1+min(a(n-Lucas(k))) where k ranges over Z.
%e A367816 For n = 0, the empty sequence sums to 0, so a(0) = 0.
%e A367816 For n = 1, 2, 3, 4, 7, 11, 18, each n is a Lucas number, so a(n) = 1.
%e A367816 The first n needing a negative-index Lucas number is 17 = 18 + -1; a(17) = 2.
%o A367816 (Python)
%o A367816 from itertools import count
%o A367816 def  a(n) :
%o A367816   """For integer n, the least number of Lucas terms required to sum to n."""
%o A367816   f = [2,1];    # Lucas numbers, starting with Lucas(0)
%o A367816   while f[-1] <= (n or 1) :
%o A367816     f.append(f[-2]+f[-1]);
%o A367816   a = [0 for _ in range(f[-1]+1)];
%o A367816   for i in f :
%o A367816     a[i] = 1;
%o A367816   for c in count(2) :
%o A367816     if not all(a[4:]) :
%o A367816       for i in range(4,f[-1]) :
%o A367816         if not a[i] :
%o A367816           for j in f :
%o A367816             if j >= i :
%o A367816               break;
%o A367816             if a[i-j] == c-1 :
%o A367816               a[i] = c;
%o A367816               break;
%o A367816           if not a[i]:
%o A367816             for j in f[1::2] :
%o A367816               if i+j >= len(a) :
%o A367816                 break;
%o A367816               if a[i+j] == c-1 :
%o A367816                 a[i] = c;
%o A367816                 break;
%o A367816     else :
%o A367816       break;
%o A367816   return a[n];
%Y A367816 Cf. A000032 Lucas numbers; A061084 negative index Lucas numbers.
%Y A367816 A116543 is the similar sequence where negative index Lucas numbers are not allowed.
%Y A367816 a(A365907(n)) is the first occurrence of n.
%K A367816 nonn,easy
%O A367816 0,6
%A A367816 _Mike Speciner_, Dec 01 2023