Ruud H.G. van Tol on Sun, 11 Jan 2026 17:45:47 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

fibint(n), fibbinary(n)



I'm looking for an effective (discrete, loop-less) way to derive the n-th fibbinary number (Zeckendorf representation).
For definitions, see https://oeis.org/A003714.

[ n | n<-[0..100], !bitand(n,n>>1) ]
[0,
1,
2,
4, 5,
8, 9, 10,
16, 17, 18, 20, 21,
32, 33, 34, 36, 37, 40, 41, 42,
64, 65, 66, 68, 69, 72, 73, 74, 80, 81, 82, 84, 85
]

- - - - - -

While on that path, I'm currently also looking for a discrete implementation of "fibint", and rather without loop.
I think that fibint(n) should return the index of the fibonacci number <= n.
Or call it fib-floor-index?


? [ fibint(2^n) |n<-[0..20] ]
[1, 3, 4, 6, 7, 8, 10, 11, 13, 14, 16, 17, 18, 20, 21, 23, 24, 26, 27, 29, 30]

? [ [2^n, fibonacci(fibint(2^n))] |n<-[0..12]]
[[1, 1], [2, 2], [4, 3], [8, 8], [16, 13], [32, 21], [64, 55], [128, 89], [256, 233], ...]


Examples that work, but that are not good enough:

fibint0(n)= my(i=0); while(fibonacci(i++)<=n,); i-1;

fibint1(n)= my(sqrt_5=2*quadgen(5)-1); log(sqrt_5*n+1.5) / log((1+sqrt_5)/2) \1; \\ after A130233


See also A062005, Floor of arithmetic-geometric mean of n and 2n,
which partly works for 2^n:

? [ [2^n, fibonacci(agm(n+1, 2*n+2)\1)] |n<-[0..12] ]
[[1, 1], [2, 1], [4, 3], [8, 5], [16, 13], [32, 21], [64, 55], [128, 89], [256, 233], ...]

- - - - - -

So my Quest 1 is to come up with a good fibint.
And my Quest 2 is to find some nice "a(n)" implementation for A003714.

Any help to push me in the right direction, on either Quest, is welcome.

-- Ruud