Prove arithmetic formula for the number of bits in $j=2^k-1$

There exist integers $m,r$ such that $$k=5m+r,\qquad 0\le m\le 30,\qquad 0\le r\le 4$$

Since we have $$j=2^k-1=2^{5m+r}-1=(2^5)^m\cdot 2^r-1\equiv 1^m\cdot 2^r-1\equiv 2^r-1\pmod{31}$$ there exists an integer $a$ such that $2^{5m+r}-1=31a+2^r-1$ which can be written as $$a=2^r(2^{5-r}a+1-2^{5m})$$ This implies that $a$ is divisible by $2^r$, so there exists an integer $b$ such that $j=2^{5m+r}-1=31\cdot 2^rb+2^r-1$.

We have $j\bmod 31=2^r-1$ and $$b\bmod 31=\frac{32^m-1}{31}\bmod 31=(32^{m-1}+32^{m-2}+\cdots +32+1)\bmod 31=m$$ Using these, we get $$\begin{align}&5\left(\left\lfloor \frac{j}{31((j \bmod 31)+1)}\right\rfloor \bmod 31\right)-\left\lfloor\frac{12}{(j \bmod 31)+3}\right\rfloor+4 \\\\&=5\left(\left\lfloor \frac{31\cdot 2^rb+2^r-1}{31\cdot 2^r}\right\rfloor \bmod 31\right)\underbrace{-\left\lfloor\frac{12}{2^r+2}\right\rfloor+4}_{=\ r} \\\\&=5\left(\left\lfloor b+\frac{2^r-1}{31\cdot 2^r}\right\rfloor \bmod 31\right)+r \\\\&=5\left(b \bmod 31\right)+r \\\\&=5m+r \\\\&=k\end{align}$$

Looking into the binary representation, and starting from $j=({\underbrace{111\ldots 1}_k})_2$, notice that $j$ can be split (from the left) into groups of five $1$'s, with less than five $1$'s remaining at the right end. So, let's write $k=5q+r$ where $0\le r \lt 5$, and look at:

$$j=(\underbrace{11111,11111,11111,\ldots,11111}_q,\underbrace{11\ldots 1}_r)_2$$

(commas added for clarity). Notice also that $(11111)_2=31$ so $j\bmod{31}=(\underbrace{11\ldots 1}_r)_2$ as the rest of the number is obviously divisible by $31$.

First part of the formula

For the first part of the formula, let's try to calculate $\left\lfloor\frac{j}{31((j\bmod{31})+1)}\right\rfloor$ first. In fact, we want to first divide $j$ by $(j\bmod{31})+1$, which is $(1\underbrace{00\ldots 0}_r)_2$, and then divide by $31$ - but when shall we take the floor function? We will use a helping Lemma below:

Lemma: Let $a\in\mathbb R$ and $b,c\in\mathbb N\setminus\{0\}$. Then $\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\right\rfloor$.

Proof: See here: https://math.stackexchange.com/a/6793/700480 . $\blacksquare$

Back to division: to calculate $\left\lfloor\frac{j}{31((j\bmod{31}+1)}\right\rfloor$, we will take the "floor" function twice (as per above Lemma) - first after division by $(j\bmod{31})+1$, which is just the right shift by $r$ places, and then after division by $31$, which already produces the whole number $(\underbrace{1,00001,00001,\ldots,00001}_{q\text{ }1\text{'s}})_2$. (Each group of binary digits $11111$ turns into $00001$.)

Now, this is a sum of numbers of the form $2^{5i}=(2^5)^i=32^i\equiv 1^i=1\pmod{31}$, so $\bmod{31}$ every single one of those $1$'s (at its place value) is equivalent to just $1$, and so the whole number is equivalent to $q$. Now, assuming the total number $k$ of "ones" to start with was $<155$, we have $q<31$ and therefore the whole number $\bmod{31}$ is $q$.

Altogether, this means $5\left(\left\lfloor \frac{j}{31((j \bmod 31)+1)}\right\rfloor \bmod 31\right)=5q$. This explains the first part of the formula.

Second part of the formula

The second part of the formula: $4-\left\lfloor\frac{12}{(j \bmod 31)+3}\right\rfloor$ is easily explainable, because $j\bmod{31}=(\underbrace{11\ldots 1}_r)_2$ and so it depends only on the remainder $r, 0\le r\lt 5$ rather than on the "whole" $j$. We can do the legwork and check the cases $r=0,1,2,3,4$ and in every case verify that $4-\left\lfloor\frac{12}{(j \bmod 31)+3}\right\rfloor=r$. It just so happens that, when $12$ is divided by numbers $0+3,1+3,3+3,7+3,15+3$, you get $4,3,2,1\frac{1}{5},\frac{2}{3}$, the integral part of those numbers are $4,3,2,1,0$, respectively, so subtracting them from $4$ produces the number $r$ we started from.

Adding it all together

One can now easily verify that $(\text{the first part})+(\text{the second part})=5q+r=k$, as expected.

The formula with $255$'s

I have not looked in detail, but this second formula looks just like the first one, where $31=(11111)_2$ is replaced by $255=(11111111)_2$. One could expect that $j=2^k-1$ would be broken up into blocks of eight $1$'s, that the proof for the first part would go as previously, while, for the second part, the number $86$ was a lucky choice and plays the same role as $12$ played above. (Numbers $0+12, 1+12, 3+12, 7+12, 15+12, 31+12, 63+12, 127+12$, when $86$ is divided by them and then truncated, yield $7, 6, 5, 4, 3, 2, 1, 0$ and subtracting them from $7$ recovers the remainder (of $k$ divided by $8$, this time).

The formula with three terms

Your two-term formula does not work for $k\ge 155$ because, when $k\ge 155$, $q\ge 31$ and instead of $k=5q+r$ you get $5(q\bmod 31)+r$.

To patch that, the third term is added:

• The additional term is based on breaking up the number into groups of $30$ "ones", while the number of those groups should be less than $2^{30}-1$. Thus, it will work for $k<30(2^{30}-1)\approx 3.2212\cdot 10^{10}$.
• The remaining part has up to $30$ "ones", which is less than $155$, so the original formula finishes it off.