Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #44 Jan 22 2020 23:30:58
%S 0,1,100,101,10010,10000,10001,10100,10101,1001010,1001000,1001001,
%T 1000010,1000000,1000001,1000100,1000101,1010010,1010000,1010001,
%U 1010100,1010101,100101010,100101000,100101001,100100010,100100000,100100001,100100100,100100101,100001010
%N NegaFibonacci representation code for n.
%C 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.
%C 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.
%C Then a(n) is the concatenation c_r ... c_3 c_2 c_1.
%D Donald E. Knuth, The Art of Computer Programming, Volume 4A, Combinatorial algorithms, Part 1, Addison-Wesley, 2011, pp. 168-171.
%H Amiram Eldar, <a href="/A215022/b215022.txt">Table of n, a(n) for n = 0..10000</a>
%H M. W. Bunder, <a href="https://www.fq.math.ca/Scanned/30-2/bunder.pdf">Zeckendorf representations using negative Fibonacci numbers</a>, The Fibonacci Quarterly, Vol. 30, No. 2 (1992), pp. 111-115.
%H Donald E. Knuth, <a href="http://www.cs.utsa.edu/~wagner/knuth/fasc1a.pdf">The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams</a>, a pre-publication draft of section 7.1.3, 2009, pp. 36-39.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/NegaFibonacci_coding">NegaFibonacci coding</a>.
%e 4 = 5 - 1 = F_{-5} + F_{-2}, so a(4) = 10010.
%t 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 *)
%o (PARI) a(n)=if(n<2,return(n));my(s=1,k=1,v);while(s<n, s+=fibonacci(k+=2));v=binary(2^k/2);n-=fibonacci(k);forstep(i=k-2,1,-1,if(abs(n-fibonacci(-i))<abs(n),n-=fibonacci(-i);v[#v+1-i]=1;i--));subst(Pol(v),x,10) \\ _Charles R Greathouse IV_, Aug 03 2012 [Caution: returns wrong values for some values of n > 15. _Amiram Eldar_, Oct 15 2019]
%Y Cf. A039834, A215023, A215024, A000045, A014417, A003714.
%K nonn,base
%O 0,3
%A _N. J. A. Sloane_, Aug 03 2012
%E a(16) inserted and 1 term added by _Amiram Eldar_, Oct 11 2019