Detailed mathematical approach

Problem Summary

For every pair of distinct positive squares \(a^2 \lt b^2\), Peter toggles door \(n=a^2+b^2\), provided \(n\le N\). After all actions, door \(n\) remains open exactly when the number of strict representations

$u(n)=\#\left\{(a,b)\in \mathbb{Z}_{>0}^2 : a \lt b,\ a^2+b^2=n\right\}$

is odd. Therefore

$F(N)=\#\left\{n\le N : u(n)\equiv 1 \pmod 2\right\}.$

The real input is \(N=10^{12}\), so enumerating all square pairs is far too slow. The implementation instead turns the problem into a classification of prime exponents.

Mathematical Approach

The central object is the classical sum-of-two-squares counting function over all signs and orders.

Step 1: Relate Door Toggles to the Classical Representation Count

Let

$r_2(n)=\#\left\{(x,y)\in \mathbb{Z}^2 : x^2+y^2=n\right\}.$

Every strict positive representation \(a \lt b\) generates eight ordered signed solutions: \((\pm a,\pm b)\) and \((\pm b,\pm a)\). Two degenerate situations contribute only four solutions:

$n=c^2 \quad \text{gives} \quad (\pm c,0),(0,\pm c),$

$n=2c^2 \quad \text{gives} \quad (\pm c,\pm c).$

So if we define

$s(n)= \begin{cases} 1,&\text{if } n \text{ is a square or twice a square},\\ 0,&\text{otherwise}, \end{cases}$

then

$r_2(n)=8u(n)+4s(n),$

hence

$\frac{r_2(n)}{4}=2u(n)+s(n).$

This identity is the bridge from door toggling to arithmetic parity.

Step 2: Use the Sum-of-Two-Squares Theorem

Write the factorization of \(n\) as

$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{\beta_q}.$

If any prime \(q\equiv 3 \pmod 4\) has odd exponent, then \(n\) is not representable as a sum of two squares at all, so \(r_2(n)=0\) and \(u(n)\) is even. The only interesting numbers are therefore

$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{2\gamma_q}.$

For such \(n\), the standard formula becomes

$r_2(n)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$

Define

$R(n)=\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$

Then the parity condition is simply

$R(n)=2u(n)+s(n).$

So the question becomes: for which exponent patterns is \((R(n)-s(n))/2\) odd?

Step 3: Family A, the Non-Degenerate Case

First assume \(s(n)=0\), meaning \(n\) is neither a square nor twice a square. Then \(u(n)\) is odd exactly when

$R(n)\equiv 2 \pmod 4.$

Because each factor \(\alpha_p+1\) is odd when \(\alpha_p\) is even and even when \(\alpha_p\) is odd, the product can be \(2 \pmod 4\) only when exactly one factor contributes a single power of \(2\) and every other factor remains odd. So there must be exactly one prime \(p\equiv 1 \pmod 4\) with odd exponent, and that exponent must satisfy

$\alpha_p+1\equiv 2 \pmod 4 \iff \alpha_p\equiv 1 \pmod 4.$

Therefore the non-degenerate doors that remain open are exactly those of the form

$n=p^{4t+1}m^2 \quad \text{or} \quad n=2p^{4t+1}m^2,$

where \(p\equiv 1 \pmod 4\) and \(p\nmid m\). This is the first family counted by the implementation.

Step 4: Family B, the Square / Twice-Square Correction

Now assume \(s(n)=1\). That means every exponent \(\alpha_p\) is even, so \(n\) is either a square or twice a square. We can write it uniquely as

$n=2^a m^2,\qquad m \text{ odd}.$

Since \(u(n)\) is odd exactly when

$R(n)\equiv 3 \pmod 4,$

we inspect each factor with \(\alpha_p=2\delta_p\). Then

$\alpha_p+1=2\delta_p+1\equiv \begin{cases} 1 \pmod 4,&\delta_p \text{ even},\\ 3 \pmod 4,&\delta_p \text{ odd}. \end{cases}$

So \(R(n)\equiv 3 \pmod 4\) exactly when an odd number of primes \(p\equiv 1 \pmod 4\) occur to odd exponent in the odd square root \(m\). That produces the second family:

$n=2^a m^2,\qquad m \text{ odd},$

with the parity filter “the number of primes \(p\equiv 1 \pmod 4\) occurring to odd exponent in \(m\) is odd.”

Step 5: Count Family A Efficiently

Let \(\pi_1(x)\) denote the number of primes \(p\le x\) with \(p\equiv 1 \pmod 4\). For the even-\(2\)-adic half of family A, we count numbers

$n=p^{4t+1}m^2,\qquad p\equiv 1 \pmod 4,\ p\nmid m,\ n\le N.$

For the first exponent layer \(p^1\), the contribution of one prime is

$\#\{m : p m^2\le N,\ p\nmid m\}=\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^3}}\right\rfloor.$

The first term is grouped by equal square-root quotients:

$\sum_{p\equiv 1 \pmod 4}\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor =\sum_{t\ge 1} t\left(\pi_1\left(\left\lfloor\frac{N}{t^2}\right\rfloor\right)-\pi_1\left(\left\lfloor\frac{N}{(t+1)^2}\right\rfloor\right)\right).$

The subtraction by \(\left\lfloor\sqrt{N/p^3}\right\rfloor\) removes the forbidden choices where the square part already contains \(p\). Higher valid exponents \(p^5,p^9,\dots\) are sparse, so they are added directly through

$\left\lfloor\sqrt{\frac{N}{p^{4t+1}}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^{4t+3}}}\right\rfloor,\qquad t\ge 1.$

If \(v_2(n)\) is odd, then \(n\) belongs to the second variant \(2p^{4t+1}m^2\). Multiplying by \(2\) gives a bijection with the even-\(v_2\) case at bound \(N/2\), so the same routine can be reused with \(N\) replaced by \(N/2\).

Step 6: Count Family B Efficiently

For family B, every valid odd \(m\le \sqrt{N}\) contributes all numbers

$m^2,\ 2m^2,\ 4m^2,\ \dots,\ 2^a m^2\le N.$

The number of admissible powers of \(2\) is

$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1.$

So the remaining work is to know, for each odd \(m\), whether the count of primes \(p\equiv 1 \pmod 4\) appearing to odd exponent is odd or even.

Worked Example: \(N=100\)

The checkpoint \(F(100)=27\) follows cleanly from the classification.

Family A with even \(v_2\) gives

$5,13,17,20,29,37,41,45,52,53,61,68,73,80,89,97,$

so there are \(16\) such doors.

Family A with odd \(v_2\) is obtained by doubling the even-\(v_2\) doors up to \(50\), namely

$10,26,34,40,58,74,82,90,$

which contributes \(8\) more doors.

For family B, the odd candidates \(m\le 10\) are \(1,3,5,7,9\). Only \(m=5\) has an odd number of \(1 \pmod 4\) primes occurring to odd exponent, so it contributes

$25,\ 50,\ 100,$

hence \(3\) more doors. Therefore

$F(100)=16+8+3=27.$

How the Code Works

The C++, Python, and Java implementations all follow the same arithmetic decomposition. The Python entry point is only a thin wrapper around that same numerical strategy, so the mathematics is identical across languages.

The implementation first builds a prime-counting structure over the quotient values \(\lfloor N/i\rfloor\). It stores both the ordinary prime count \(\pi(x)\) and a weighted prime sum using the Dirichlet character

$\chi_4(n)= \begin{cases} 0,&n \text{ even},\\ 1,&n\equiv 1 \pmod 4,\\ -1,&n\equiv 3 \pmod 4. \end{cases}$

From these two tables it recovers

$\pi_1(x)=\frac{(\pi(x)-1)+\sum_{p\le x}\chi_4(p)}{2},$

which is exactly the count of primes \(p\le x\) with \(p\equiv 1 \pmod 4\).

With that tool in place, the implementation counts family A in three pieces: the grouped \(p^1\) layer, the correction that subtracts roots already divisible by the chosen prime, and the direct enumeration of the sparse higher layers \(p^5,p^9,\dots\). It then reuses the same routine at \(N/2\) to count the odd-\(v_2\) branch.

For family B, the implementation precomputes smallest prime factors up to \(\lfloor\sqrt{N}\rfloor\). Factoring each odd \(m\) reveals whether the number of primes \(p\equiv 1 \pmod 4\) occurring to odd exponent is odd. Whenever the parity condition holds, it adds

$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1$

to the answer.

Finally, the implementation adds the even-\(v_2\) branch of family A, the corresponding odd-\(v_2\) branch obtained from the \(N/2\) bijection, and the family-B contribution.

Complexity Analysis

Let \(M=\lfloor\sqrt{N}\rfloor\). The smallest-prime-factor sieve and the parity table for odd \(m\) cost \(O(M\log\log M)\) time and \(O(M)\) memory. The family-B scan is linear in \(M\). The higher-power part of family A is very small because \(p^5\) already grows quickly.

The dominant work is the quotient-class prime-counting structure used to answer many values of \(\pi_1(x)\) efficiently. It stores \(O(M)\) quotient values and keeps the overall method practical for \(N=10^{12}\). So the implementation uses \(O(M)\) memory, and the runtime is dominated by the prime-counting preprocessing plus the linear-in-\(M\) auxiliary passes.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=611
2. Fermat's theorem on sums of two squares: Wikipedia — Fermat's theorem on sums of two squares
3. Sum of two squares function: Wikipedia — Sum of two squares function
4. Dirichlet character: Wikipedia — Dirichlet character
5. Prime-counting function: Wikipedia — Prime-counting function