The Hamming weight $w(n)$ is the number of 1s in $n$ when written in binary. Is there some effective bound on Fibonacci numbers $F\_n$ with $w(F\_n)\le x$ for a given $x$?


Clearly only $F\_0=0$ has weight 0, and it's not hard to show (e.g. by Carmichael's theorem) that only $F\_1=F\_2=1, F\_3=2, F\_6=8$ have Hamming weight 1. (Pedantry: I'm ignoring negative indices.) It seems that only $F\_4=3, F\_5=5, F\_9=34, F\_{12}=144$ have weight 2, but I cannot even prove this.


It seems that the fact that $\varphi$ is a Pisot number, and in particular $F\_n=\varphi^n/\sqrt5+o(1)$, should/may be related.



Hamming weight of Fibonacci numbers
The case $x=2$ is still tractable. If $F\_n = 2^e + 2^f$ with $e<f$
then $e < 5$, else $F\_n \equiv 0 \bmod 2^5$, which happens **iff**
$n \equiv 0 \bmod 24$, and then $7 \mid 21 = F\_8 \mid F\_{24} \mid F\_n$,
which is impossible because $2^e + 2^f$ is never a multiple of $7$.
So we have only a few candidates for $e$, and we can deal with
each of them separately, possibly even by elementary means,
to show that $(n,e,f) = (12,4,7)$ is the last solution.


$\langle$ **EDIT** $\rangle$
Here's such an elementary proof.
For each $e$ (other than the trivial $e=2$), we choose some $f\_0 > e$,
try each $f$ with $e < f\_0 < f$, and then once $f \geq f\_0$ we use
the condition $F\_n = 2^e + 2^f \equiv 2^e \bmod 2^f$ to get a
congruence condition on $n$, and then reach a contradiction by considering
$F\_n$ modulo some odd prime (usually $3$, but with one much larger exception).


$e=0$: We take $f\_0 = 4$. Trying $f=1$ and $f=2$ yields
the Fibonacci numbers $F\_4=3$ and $F\_5=5$,
and $f=3$ yields the non-Fibonacci number $9$. Once $f \geq 4$
we have $F\_n \equiv 1 \bmod 16$. But $F\_n \bmod 16$ is periodic with
period $24$, and it turns out that the remainder is $1$ only for
$n \equiv 1, 2, 23 \bmod 24$. But $F\_n \bmod 3$ has period $8$,
which is a factor of $24$; and $F\_1 = F\_2 = F\_{-1} = 1$.
We deduce $F\_n \equiv 1 \bmod 3$.
Hence $2^f \equiv 0 \bmod 3$, which is impossible.


$e=1$: The Fibonacci numbers $F\_n$ congruent to $2 \bmod 4$
are those with $n \equiv 3 \bmod 6$, and these always turn out to be
$2 \bmod 32$. Thus $f \geq 5$, and $f=5$ yields the Fibonacci number
$34 = F\_9$. We claim that this is the only possibility, using $f\_0 = 6$.
Once $f \geq 6$ we have $F\_n \equiv 2 \bmod 64$, and then
$n \equiv \pm 3 \bmod 24$. But (again thanks to $8$-periodicity mod $3$)
this implies $F\_n \equiv 2 \bmod 3$, so once more we reach
a contradiction from the congruence $2^f \equiv 0 \bmod 3$.


$e=2$: impossible because $F\_n$ is never $2 \bmod 4$.


$e=3$: We take $f\_0=5$. Since $2^3 + 2^4 = 24$ is not a Fibonacci number,
we may assume $f \geq 5$, and then $F\_n \equiv 8 \bmod 32$. This is
equivalent to $n \equiv 6 \bmod 24$, which again yields a contradiction
mod $3$ since $2^f = F\_n - 2^e$ would have to be a multiple of $3$.


$e=4$: This is the hardest case:
because $f=7$ yields $144 = F\_{12}$, it is not enough to use
congruences that can be deduced from $F\_n \equiv 2 \bmod 2^7$,
and we must take $f\_0 > 7$. It turns out that $f\_0 = 9$ works.
Then $f=5,6,8$ yield the non-Fibonacci $48, 80, 272$.
Once $f \geq 9$ we must have $F\_n \equiv 16 \bmod 2^9$.
Now $F\_n \bmod 2^9$ has period $768$,
but the condition $F\_n \equiv 16 \bmod 2^9$ determines $n \bmod 384$
(half of $768$), and we compute $n \equiv -84 \bmod 384$.
Now $n \bmod 384$ determines $F\_n$ modulo the prime $4481$
(the period is $128$), and we find $F\_n \equiv 2284 \bmod 4481$,
whence $2^f = F\_n - 2^e \equiv 2284 - 16 = 2268 \bmod 4481$.
But this is impossible because $2$ is a fourth power (even an $8$th power)
mod $4481$, and $2268$ is not.


$\langle$ **/EDIT** $\rangle$


But I doubt that one can prove that such a technique can work for all $x$...


