Project Euler Problem 611
Peter moves in a hallway with N + 1 doors consecutively numbered from 0 through N.
Solution
Answer: 49283233900
Let an action be determined by two integers $a,b$ with
$$1 \le a < b,\qquad a^2+b^2\le N.$$
That action toggles door
$$n=a^2+b^2.$$
Hence the number of times door $n$ is toggled is exactly the number of representations
$$n=a^2+b^2,\qquad 1\le a<b.$$
Therefore $F(N)$ is the count of integers $n\le N$ for which this number of representations is odd.
For the classical sum-of-two-squares function $r_2(n)$ (ordered signed representations),
$$r_2(n)=4\bigl(d_1(n)-d_3(n)\bigr),$$
where $d_1,d_3$ count divisors congruent to $1,3\pmod4$.
If
$$n=\prod p_i^{e_i}\prod q_j^{2f_j},$$
with $p_i\equiv1\pmod4$ and $q_j\equiv3\pmod4$, then
$$d_1(n)-d_3(n)=\prod (e_i+1).$$
After removing the exceptional cases coming from $0^2+n^2$ and $a^2+a^2$, one finds that the parity of the number of representations with $1\le a<b$ is determined entirely by the exponents of the $1\bmod4$ primes:
- either exactly one exponent is $1\pmod4$ and all others are $0\pmod4$,
- or an odd number of exponents are $2\pmod4$ and the rest are $0\pmod4$.
Using this characterization, one can build an efficient multiplicative counting algorithm (with recursive generation of admissible exponent patterns and segmented counting up to $10^{12}$).
The computation reproduces the given checks:
$$F(5)=1,\qquad F(100)=27,\qquad F(1000)=233,\qquad F(10^6)=112168.$$
Carrying the same computation through to $10^{12}$ gives:
Answer: 297235289158