How come Pisano periods develop this way for$\mod 2^m$?

Question

I came across this fun little math / programming problem.

The programming language is Java

Now, to shortcut a few things...

• The n1 = n0 + (n0 = n1)) line affects a Fibonacci sequence.
• The loop is flawed, because i never increments
• int in Java is a 32 bit number, and overflows gracefully, not resulting in any exception or program crash

Hence, we get a Fibonacci sequence that eventually loops, thus having a Pisano period. And the actual math problem is: how many unique numbers in the $-2^{31}$ to $+2^{31}-1$ range do we hit before we loop?

So, attacking the problem, I expanded the program to simply try this out, on the sequence...

• $x_0 = 0$
• $x_1 = 1$
• $x_n = (x_{n-1} + x_{n-2}) \mod 2^m$

...for $m = [2..30]$ (which is as far as I got before the program flaked out) and see how many unique numbers I hit.

And a very interesting trend showed itself...

Green is actual runs, yellow is extrapolation.

The columns are (from left to right):

• "Bit cap" is $m$, the number of bits used to represent $n_1$
• "Period" is the Pisano period when using $m$ bits to represent $n_1$
• "Unique" is the amount of unique numbers the sequence visits before looping back to $0, 1$ when using $m$ bits to represent $n_1$
• "Time (ms) is the execution time in milliseconds; how long it took for the program to go through one Pisano period
• "Period increase" is the relative increase compared to the line above; the ratio between the period on this line, and the period on the line above
• "Unique Increase" is the relative increase compared to the line above; the ratio between the amount of unique numbers on this line, and the amount on the line above

So, instantly it becomes obvious that there are patterns here.

• The Pisano period follows the sequence A003945, or $2^m * 3 / 2$

• The number of uniques, from $m \geq 5$, follows the sequence A175805, or $2^{m} * 21 / 32$, or $2^{m-5} * 21$

Question: why is this? Can this be proven? Does my extrapolation for $m = 31$ and $32$ hold?