Let $a(n)$ be [A214973](https://oeis.org/A214973), number of terms in greedy representation of $n$ using Fibonacci and Lucas numbers.


Let $b(n)$ be [A329320](https://oeis.org/A329320), sequence which arises from attempts to simplify computing of [A329319](https://oeis.org/A329319). Here
$$b(n)=b\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+1-f(n+1), b(0)=0$$
where $f(n)$ is [A035263](https://oeis.org/A035263), trajectory of $1$ under the morphism $0$ -> $11$, $1$ -> $10$; parity of $2$-adic valuation of $2n$.


Let $c(n)$ be [A048679](https://oeis.org/A048679), compressed fibbinary numbers ([A003714](https://oeis.org/A003714)), with rewrite $0$->$0$, $01$->$1$ applied to their binary expansion.


Then [sequencedb.net conjecture](http://sequencedb.net/s/A214973) that
$$a(n)=b(c(n))$$


Is there a way to prove it?



One conjecture by sequencedb.net
Sure. Start with the Zeckendorf representation of $n$, $$ n = \sum\_{ i} F\_{j\_i} $$ where $F\_j$ are the Fibonacci numbers and $j\_i \geq j\_{i-1} + 2$.


Then the fibbinary number associated to $n$ is $\sum\_i 2^{j\_i}$ and $c(n)$ is obtained from this by removing a zero in front of each $1$, i.e. $$c(n) = \sum\_i 2^{ j - (i-1)}$$


Now the $b(m)$ function is written in a confusing way. It's defined using the function 1-AO35263, where A035263(n) counts the number of trailing zeroes of $2n$, modulo $2$, so 1- A036263(n) simply counts the number of trailing zeroes of the binary expansion of $n$, modulo $2$. So $b(m)$ is the sum over $k$ of the number of trailing zeroes of $\lfloor \frac{m}{2^k} \rfloor+1$, mod 2. In other words, $b(m)$ is the sum over $k$ of the number of trailing ones of the binary expansion $ \lfloor \frac{m}{2^k} \rfloor$, mod $2$. If we break the binary expansion of $m$ into blocks of consecutive ones separated by zeroes, we see that each block of length $\ell$ produces one quotient with $\ell$ trailing ones, one with $\ell-1$ trailing ones, etc. down to one with $1$ trailing ones, for a total contribution of $\lceil \frac{\ell}{2} \rceil$.


So $b(m)$ is the sum over blocks of consecutive ones in the binary expansion of $m$ of half the number of ones in the block, rounded up.


Now we make the following observation. For $n = \sum\_{i=1}^k F\_{j\_i}$ in Zeckendorf representation, if $ i\_{k-1} = i\_k-2$ then the largest Fibonacci-Lucas number $\leq n$ is $F\_{i\_k} + F\_{i\_k-2} = L\_{i\_k-1}$ and otherwise the largest Fibonacci-Lucas number $\leq n$ is $F\_{i\_k}$.


This can be checked quickly by properties of Fibonacci and Lucas numbers. We have $F\_n \leq L\_{n-1} \leq F\_{n+1}$ so it suffices to prove in the first case that $F\_{i\_k+1} $ is too large and in the second case that $L\_{i\_k-1}$ is too large. In the first case, this claim follows from [the Lemma used in the proof of the Zeckendorf decomposition](https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem) and in the second case $L\_{i\_k-1} = F\_{i\_k} + F\_{i\_k-2}$ is too large by the same lemma after subtracting $F\_{i\_k}$ from both sides.


Using this and the definition of greedy algorithm, we can see that if $i\_{k-1} = i\_{k}-2$ then $a(n) = a(n- F\_{i\_k} - F\_{i\_k-2}) + 1$ and if $i\_{k-1}< i\_k-2$ then $a(n) = a(n-F\_{i\_k})-1$.


We can now prove $a(n) = b(c(n))$ by induction. In the first case, passing from $n$ to $n- F\_{i\_k} - F\_{i\_{k}-2}$ removes a leading $11$ from $c(n)$, and thus subtracts $1$ from $b(c(n))$ since it reduces the length of a block of ones by two, while in the second case, passing from $n$ to $n-F\_{i\_k}$ removes a leading $1$ followed by one or more $0$s from $c(n)$, and thus subtracts $1$ from $b(c(n))$ since it removes a block of ones of length one.


Since we passed to a lower number and shifted both $a(n)$ and $b(c(n))$ by the same amount, the two sequences are equal as long as they are equal in the base case $n=0$, which is automatic: $a(0) =0 = b(0 ) =b(c(0))$


