Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
I suspect this is very hard. The question of whether there is any $n\gt86$ such that the decimal representation of $2^n$ has no zero digit is open. This seems like the same kind of question. –  Gerry Myerson Mar 2 at 5:55
    
The number of ones in the binary notation for the $n$th Fibonacci number is tabulated at oeis.org/A011373 but without any information. –  Gerry Myerson Mar 2 at 5:58
    
@GerryMyerson: I hope that this is easier than the corresponding problem for powers of 2, since it is not sensitive to perturbations of individual digits and has strong divisibility properties. But easier doesn't mean easy, by any means! –  Charles Mar 2 at 6:09
5  
Since you specify "effective" in the question I guess you know this already, but just in case: there are only finitely many such $n$, because $2^{e_1}+\cdots+2^{e_x} = (\varphi^n-\varphi^{-n})/\sqrt{5}$ is an $S$-unit equation in $x+2$ variables over ${\bf Q}(\sqrt{5})$; but in general no effective proof is known for such a result (though the number of solutions of $w(F_n) \leq x$ may be effectively bounded). –  Noam D. Elkies Mar 2 at 6:28

1 Answer 1

up vote 13 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.