Prove arithmetic formula for the number of bits in $j=2^k-1$ If $k$ is an integer with $0\le k<155$, and $j=2^k-1$, then it holds:
$$k\,=\,5\left(\left\lfloor\frac j{31((j\bmod31)+1)}\right\rfloor\bmod 31\right)-\left\lfloor\frac{12}{(j\bmod31)+3}\right\rfloor+4$$
Why does this equation hold for such a large interval of $k$? How can we prove that?

This is a shortened version of more complex formula# posted by Hallvard B. Furuseth in a comp.c post on 2003-11-03, which reportedly works to $k$ of at least $3\cdot10^{10}$.

Update (not part of the bountied question): per this source, the same author gave that formula working for $0\le k<2040$:
$$k\,=\,8\left(\left\lfloor\frac j{255((j\bmod255)+1)}\right\rfloor\bmod 255\right)-\left\lfloor\frac{86}{(j\bmod255)+12}\right\rfloor+7$$

Try it online with Python or with Wolfram Mathematica! The code computes the upper limits for both formulas.

# Full formula, for reference (not in the above code or part of the bountied question):
$$\begin{align}k\,=\,&30\left(\left\lfloor\frac j{((j\bmod(2^{30}-1))+1)\,(2^{30}-1)}\right\rfloor\bmod (2^{30}-1)\right)+\\&5\left(\left\lfloor\frac{j\bmod(2^{30}-1)}{31((j\bmod31)+1)}\right\rfloor\bmod 31\right)-\left\lfloor\frac{12}{(j\bmod31)+3}\right\rfloor+4\end{align}$$
 A: 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}$$
