A215022 NegaFibonacci representation code for n.

0, 1, 100, 101, 10010, 10000, 10001, 10100, 10101, 1001010, 1001000, 1001001, 1000010, 1000000, 1000001, 1000100, 1000101, 1010010, 1010000, 1010001, 1010100, 1010101, 100101010, 100101000, 100101001, 100100010, 100100000, 100100001, 100100100, 100100101, 100001010

Offset: 0

Author

N. J. A. Sloane, Aug 03 2012

Keywords

• nonn
• base

Comments

Let F_{-n} be the negative Fibonacci numbers (as defined in the first comment in A039834): F_{-1}=1, F_{-2}=-1, F_{-3}=2, F_{-4}=-3, F_{-5}=5, ..., F_{-n}=(-1)^(n-1)F_n.

Every integer has a unique representation as n = Sum_{k=1..r} c_k F_{-k} for some r, where the c_k are 0 or 1 and no two adjacent c's are 1.

Then a(n) is the concatenation c_r ... c_3 c_2 c_1.

Examples

			4 = 5 - 1 = F_{-5} + F_{-2}, so a(4) = 10010.
		

References

• Donald E. Knuth, The Art of Computer Programming, Volume 4A, Combinatorial algorithms, Part 1, Addison-Wesley, 2011, pp. 168-171.

Links

• Amiram Eldar, Table of n, a(n) for n = 0..10000
• M. W. Bunder, Zeckendorf representations using negative Fibonacci numbers, The Fibonacci Quarterly, Vol. 30, No. 2 (1992), pp. 111-115.
• Donald E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams, a pre-publication draft of section 7.1.3, 2009, pp. 36-39.
• Wikipedia, NegaFibonacci coding.

Crossrefs

Cf. A039834, A215023, A215024, A000045, A014417, A003714.

Programs

Mathematica

ind[n_] := Floor[Log[Abs[n]*Sqrt[5] + 1/2]/Log[GoldenRatio]]; f[1] = 1; f[n_] := If[n > 0, i = ind[n - 1]; If[EvenQ[i], i++]; i, i = ind[-n]; If[OddQ[i], i++]; i]; a[n_] := Module[{k = n, s = 0}, While[k != 0, i = f[k]; s += 10^(i - 1); k -= Fibonacci[-i]]; s]; Array[a, 100, 0] (* Amiram Eldar, Oct 15 2019 *)

PARI

a(n)=if(n<2,return(n));my(s=1,k=1,v);while(sCharles R Greathouse IV, Aug 03 2012 [Caution: returns wrong values for some values of n > 15. Amiram Eldar, Oct 15 2019]

Extensions

a(16) inserted and 1 term added by Amiram Eldar, Oct 11 2019