7
$\begingroup$

Let $a(n)$ be A214973, number of terms in greedy representation of $n$ using Fibonacci and Lucas numbers.

Let $b(n)$ be A329320, sequence which arises from attempts to simplify computing of 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, trajectory of $1$ under the morphism $0$ -> $11$, $1$ -> $10$; parity of $2$-adic valuation of $2n$.

Let $c(n)$ be A048679, compressed fibbinary numbers (A003714), with rewrite $0$->$0$, $01$->$1$ applied to their binary expansion.

Then sequencedb.net conjecture that $$a(n)=b(c(n))$$

Is there a way to prove it?

$\endgroup$
2
  • 4
    $\begingroup$ It would be great if you could edit the post to include at least one definition for each of these sequences, instead of the OEIS link, to make the question more self-contained. $\endgroup$
    – Will Sawin
    Commented Nov 14, 2021 at 18:10
  • $\begingroup$ @WillSawin, thank you for comment! Partially done (because unfortunately I have no ideas for $a(n)$ and $c(n)$). $\endgroup$ Commented Nov 14, 2021 at 18:29

1 Answer 1

21
$\begingroup$

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 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))$

$\endgroup$
1
  • 4
    $\begingroup$ The same idea seems to prove the second conjecture on that sequencedb page, a(n)=A000120(A072650(A072650(A003714(n+1)))). $\endgroup$
    – Will Sawin
    Commented Nov 14, 2021 at 18:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .