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

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, 16, 10, 11, 9, 18, 19, 17, 20, 21, -21, -20, -22, -19, -18, -24, -23, -25, -16, -15, -17, -14, -13, -29, -28, -30, -27, -26, -32, -31, -33

Offset: 0

Author

Garth A. T. Rose, Jul 10 2019

Keywords

• base
• sign

Comments

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.

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.

Examples

			10 is 8 + 2, or F_6 + F_3. a(10) is then F_{-5} + F_{-2} = 5 + (-1) = 4.
		

References

• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.3, p. 169.
• 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.

Links

• Garth A. T. Rose, Table of n, a(n) for n = 0..1000
• Sean A. Irvine, Java program (github)
• Wikipedia, Zeckendorf's theorem

Crossrefs

Cf. A000045, A014417, A215022, A215023.

Programs

Sage

def a309076(n):
    result = 0
    lnphi = ln((1+sqrt(5))/2)
    while n > 0:
        k = floor(ln(n*sqrt(5)+1/2)/lnphi)
        n = n - fibonacci(k)
        result = result + fibonacci(1 - k)
    return result