|
| |
|
|
A215022
|
|
NegaFibonacci representation code for n.
|
|
13
|
|
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,base
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
a(16) inserted and 1 term added by Amiram Eldar, Oct 11 2019
|
|
|
STATUS
|
approved
|
| |
|
|
