# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a367817 Showing 1-1 of 1 %I A367817 #6 Dec 31 2023 00:47:37 %S A367817 0,1,1,1,2,1,2,2,1,2,2,2,2,1,2,2,2,3,2,3,2,1,2,2,2,3,2,3,3,2,3,2,3,2, %T A367817 1,2,2,2,3,2,3,3,2,3,3,3,3,2,3,3,3,3,2,3,2,1,2,2,2,3,2,3,3,2,3,3,3,3, %U A367817 2,3,3,3,4,3,4,3,2,3,3,3 %N A367817 Number of terms in a shortest sequence of Fibonacci numbers that sum to n, allowing Fibonacci numbers with negative indices. %C A367817 a(A001076(n)) is the first occurrence of n. %F A367817 a(0) = 0; a(A000045(n)) = 1 for n > 0. %F A367817 For n > 0, a(n) = 1 + min(a(n-Fibonacci(k))) where k ranges over Z. %e A367817 For n = 0, the empty sequence sums to 0, so a(0) = 0. %e A367817 For n = 1, 2, 3, 5, 8, 13 each n is a Fibonacci number, so a(n) = 1. %e A367817 The first n needing a negative-index Fibonacci number is 12 = 13 + -1; a(12) = 2. %o A367817 (Python) %o A367817 from itertools import count %o A367817 def a(n) : %o A367817 """For integer n, the least number of Fibonacci terms required to sum to n.""" %o A367817 f = [1,2]; # Fibonacci numbers, starting with Fibonacci(2) %o A367817 while f[-1] <= n : %o A367817 f.append(f[-2]+f[-1]); %o A367817 a = [0 for _ in range(f[-1]+1)]; %o A367817 for i in f : %o A367817 a[i] = 1; %o A367817 for c in count(2) : %o A367817 if not all(a[4:]) : %o A367817 for i in range(4,f[-1]) : %o A367817 if not a[i] : %o A367817 for j in f : %o A367817 if j >= i : %o A367817 break; %o A367817 if a[i-j] == c-1 : %o A367817 a[i] = c; %o A367817 break; %o A367817 if not a[i]: %o A367817 for j in f[::2] : %o A367817 if i+j >= len(a) : %o A367817 break; %o A367817 if a[i+j] == c-1 : %o A367817 a[i] = c; %o A367817 break; %o A367817 else : %o A367817 break; %o A367817 return a[n]; %Y A367817 Cf. A000045 (Fibonacci numbers), A039834 (negative index Fibonacci numbers). %Y A367817 Cf. A007895 (similar but with negative index Fibonacci numbers not allowed). %Y A367817 Cf. A001076. %K A367817 nonn,easy %O A367817 0,5 %A A367817 _Mike Speciner_, Dec 01 2023 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE