Given a number, how does one tell how many Fibonacci numbers will be involved in its Zeckendorf representations (i.e. how many "active" bits)?
In base 2, you simply take log-base2 of a number n to get the maximum amount of bits needed to store numbers up to n
How does one apply this to the Zeckendorf representation? Given a number n, how do I tell the maximum number of active bits in its Zeckendorf representation?
Thanks
Zeckendorf representations are quite unpredictable—in particular, the number of "active bits" is not monotonic, and so it's unlikely for there to be a closed-form formula.
But for the maximum number of active bits, $b$, given the size of $n$, we can answer the dual problem: given the number of active bits, $b$, what is the minimum size of $n$? That's easy: the smallest such number $n$ is $F_2 + F_4 + \cdots + F_{2b} = F_{2b+1}-1$. And this number $n$ is about $\frac1{\sqrt5} \phi^{2b+1} \approx 0.7236 \phi^{2b}$ in size. Solving for $b$ gives $b \approx 1.039\log n + 0.6723$ (where $\log$ denotes the natural logarithm). So this is the maximum number of "active bits" in the Zeckendorf representation of numbers of size $n$.
Since the Fibonacci numbers grow as $\phi^n$, you just take the base $\phi$ log to see how many numbers will be used. You can get this as $\frac {\log n}{\log \phi}\approx 2.078 \log n$. This gives the number of bits used, not the number of $1$s in the representation, which agrees with your use of $\log_2 n$ for base $2$, but is not what people would usually call active bits.
