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