Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
I am a third-year computer science student. I am interested, why doesn't the number of ones in the binary representation of Fibonacci numbers grow linearly? I would expect it to grow linearly all the time (because the Fibonacci numbers grow exponentially with the index, and the number of binary ones is proportional to the logarithm, so the exponential growth and logarithmic growth should cancel each other out into the linear growth), but apparently it grows linearly up to around the 45th Fibonacci number... and then it stops growing. How is that possible?
$\begingroup$Similarly, every sum of positive reals converges when computing with floating reals on computers, addition and multiplication fail to be associatif (rounding errors) and $\sum_{i=1}^N 1/i$ is strictly smaller than $\sum_{i=0}^{N-1}1/(N-i)$ when working with floating numbers for $N\sim 10^9$.$\endgroup$
You are hitting overflow with 32 bit "integers" at the point where things stop off in your calculations. In other words, your graph stops being accurate because you are using machine numeric types which only store 32 bits, not the full number.
$\begingroup$This seems to be it: the least Fibonacci number more than $2^{32}$ is $F_{48}$. The sequence of binary weights is [0,1,1,1,2,2,1,3,3,2,5,4,2,5,6,4,8,7,4,5,8,6,8,11,6,6,9,11,11,12,8,11,9,13,12,11,12,14,10,12,16,17,14,16,18,15,21,13,12,18,18,17,17,17,16,22,21,16,24,20,16,19,26,23,20,25,19,26,15,23,23,22,25,27,24,23,23,22,27,28,27,32,31,25,30,34,27,33,24,36,33,30,37,28,33,30,29,31,36,38,41,30,31,39,40,34,39,32,35,34,39,42,36,41,43,43,40,43,41,43,36,46,48,37,38,47,37,36,50,46,42,42,42,43,50,46,40,49,36,51,53,50,54,52,48,41,47,49,54,57,55,56,54,50,52,58,54,58,51,51,58,51,59,50,54,59,69,47,... ]$\endgroup$
$\begingroup$I correctly ran the calculation myself for the numbers in the range they have graphed. Their graph is wrong and it is wrong in the manner caused by only looking at 32 bits. A correct calculation shows the number of 1s grows roughly linearly in this range. I don't understand why you are taking issue with this.$\endgroup$
$\begingroup$@RedBanana "32-bit computers can only handle 32-bit numbers" is a bit like saying that "10-digit primates can only handle 10-digit numbers"... :-)$\endgroup$
