cp's OEIS Frontend

A309076 The Zeckendorf representation of n read as a NegaFibonacci representation.

%I A309076 #26 Aug 22 2019 04:51:16
%S A309076 0,1,-1,2,3,-3,-2,-4,5,6,4,7,8,-8,-7,-9,-6,-5,-11,-10,-12,13,14,12,15,
%T A309076 16,10,11,9,18,19,17,20,21,-21,-20,-22,-19,-18,-24,-23,-25,-16,-15,
%U A309076 -17,-14,-13,-29,-28,-30,-27,-26,-32,-31,-33
%N A309076 The Zeckendorf representation of n read as a NegaFibonacci representation.
%C A309076 Every nonnegative integer has a unique Zeckendorf representation (A014417) as a sum of nonconsecutive Fibonacci numbers F_{k}, with k>1. Likewise, every integer has a unique NegaFibonacci representation as a sum of nonconsecutive F_{-k}, with k>0 (A215022 for the positive integers, A215023 for the negative). So the F_{k} summing to n are transformed to F_{-k+1} and summed. Since the representations are unique and mapped one-to-one, every integer appears exactly once in the sequence.
%C A309076 a(n) changes sign at each Fibonacci number, since NegaFibonacci representations with an odd number of fibits are positive and those with an even number are negative.
%D A309076 D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.3, p. 169.
%D A309076 E. Zeckendorf, Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.
%H A309076 Garth A. T. Rose, <a href="/A309076/b309076.txt">Table of n, a(n) for n = 0..1000</a>
%H A309076 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a309/A309076.java">Java program</a> (github)
%H A309076 Wikipedia, <a href="https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem">Zeckendorf's theorem</a>
%e A309076 10 is 8 + 2, or F_6 + F_3. a(10) is then F_{-5} + F_{-2} = 5 + (-1) = 4.
%o A309076 (Sage)
%o A309076 def a309076(n):
%o A309076     result = 0
%o A309076     lnphi = ln((1+sqrt(5))/2)
%o A309076     while n > 0:
%o A309076         k = floor(ln(n*sqrt(5)+1/2)/lnphi)
%o A309076         n = n - fibonacci(k)
%o A309076         result = result + fibonacci(1 - k)
%o A309076     return result
%Y A309076 Cf. A000045, A014417, A215022, A215023.
%K A309076 base,sign
%O A309076 0,4
%A A309076 _Garth A. T. Rose_, Jul 10 2019