login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A215022 NegaFibonacci representation code for n. 11
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

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.

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.

EXAMPLE

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

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 *)

PROG

(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]

CROSSREFS

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

Sequence in context: A085251 A178530 A063010 * A094027 A281149 A204582

Adjacent sequences:  A215019 A215020 A215021 * A215023 A215024 A215025

KEYWORD

nonn,base

AUTHOR

N. J. A. Sloane, Aug 03 2012

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 13 05:37 EDT 2021. Contains 344981 sequences. (Running on oeis4.)