Project Euler Problem 935
A square of side length b<1 is rolling around the inside of a larger square of side length 1, always touching the larger
Solution
Answer: 759908921637225
A rigorous derivation reduces the rolling-square dynamics to counting coprime lattice points in three residue classes.
Let the large square side length be
$$L=\frac1b=h+x,\qquad h\in\mathbb Z_{\ge1},; x\in[0,1).$$
The dynamics induces the map
$$H(x)=\operatorname{frac}!\left(x-\sqrt{1-x^2}\right),$$
and the periodic-return configurations split into:
- Integer cases $x=0$, giving periods $4(h-1)$.
- Non-integer cases parameterized by coprime pairs $(u,v)$, with return time
$$\text{scale}(u),(hu+v-1),$$
where
$$\text{scale}(u)= \begin{cases} 1,&u\equiv0\pmod4,\ 2,&u\equiv2\pmod4,\ 4,&u\text{ odd}. \end{cases}$$
This converts the problem into counting coprime pairs under linear bounds, which can be evaluated efficiently using Möbius inversion and a Du Jiao sieve for fast Mertens-function queries.
The resulting implementation reproduces the required checks:
- $F(6)=4$
- $F(100)=805$
and computes:
$$F(10^8)=759908921637225.$$
Answer: 759908921637225