How long is the Zeckendorf Representation of a given number? 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
 A: 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$.
A: 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.
