Detailed mathematical approach

Problem Summary

For each positive integer \(N\), the problem considers the circle through \((0,0)\), \((N,0)\), \((0,N)\), and \((N,N)\), and defines \(f(N)\) as the number of lattice points on that circle. The goal is to compute

$S(10^{11})=\sum_{\substack{N\le 10^{11}\\f(N)=420}} N.$

A direct scan up to \(10^{11}\) is impossible. The successful route is to convert the geometry into a sum-of-two-squares counting problem, extract an exact multiplicative formula for \(f(N)\), and then classify all admissible prime-exponent patterns.

Mathematical Approach

The central observation is that the original circle can be rewritten so that its lattice points are counted by representations of \(N^2\) as a sum of two squares.

From the original circle to \(a^2+b^2=N^2\)

The circle through the four corners of the \(N\times N\) square has center \((N/2,N/2)\) and radius \(N/\sqrt2\), so its equation is

$\left(x-\frac N2\right)^2+\left(y-\frac N2\right)^2=\frac{N^2}{2}.$

Introduce the linear change of variables

$a=x+y-N,\qquad b=x-y.$

Substituting and simplifying gives

$a^2+b^2=N^2.$

This transformation is bijective on lattice points: from \(a\) and \(b\) we recover

$x=\frac{N+a+b}{2},\qquad y=\frac{N+a-b}{2},$

and the parity condition is automatically satisfied whenever \(a^2+b^2=N^2\). Therefore \(f(N)\) is exactly the number of integer pairs \((a,b)\) satisfying that equation. In standard notation,

$f(N)=r_2(N^2),$

where \(r_2(m)\) counts representations of \(m\) as a sum of two squares with order and sign included.

Prime factorization and the formula for \(f(N)\)

Write the factorization of \(N\) as

$N=2^\alpha\prod_i p_i^{e_i}\prod_j q_j^{f_j},$

where every \(p_i\equiv 1\pmod 4\) and every \(q_j\equiv 3\pmod 4\). Then

$N^2=2^{2\alpha}\prod_i p_i^{2e_i}\prod_j q_j^{2f_j}.$

The sum-of-two-squares theorem implies that primes \(q_j\equiv 3\pmod 4\) do not affect the count here, because they appear with even exponents in \(N^2\). Only the \(1\bmod 4\) primes contribute, and the count becomes

$f(N)=r_2(N^2)=4\prod_i(2e_i+1).$

This is the exact arithmetic object computed by the implementations, and it is also why the geometry can be cross-checked by factoring \(N\) instead of drawing the circle.

Solving \(f(N)=420\)

The target condition is

$4\prod_i(2e_i+1)=420,$

so we must solve

$\prod_i(2e_i+1)=105=3\cdot5\cdot7.$

Each factor \(2e_i+1\) is an odd integer at least \(3\). That leaves only five possible exponent patterns:

$105 \Rightarrow e=52,$

$35\cdot3 \Rightarrow (e_1,e_2)=(17,1),$

$21\cdot5 \Rightarrow (e_1,e_2)=(10,2),$

$15\cdot7 \Rightarrow (e_1,e_2)=(7,3),$

$3\cdot5\cdot7 \Rightarrow (e_1,e_2,e_3)=(1,2,3).$

So any valid \(N\) must have its \(1\bmod4\) prime exponents equal to one permutation of

$[52],\ [17,1],\ [10,2],\ [7,3],\ [3,2,1].$

Core numbers and allowed multipliers

Separate every valid \(N\) into

$N=c\cdot m.$

The core \(c\) contains all primes \(p\equiv1\pmod4\) with one of the admissible exponent patterns above. The multiplier \(m\) contains only the prime \(2\) and primes \(q\equiv3\pmod4\). This decomposition is unique because the two prime families are disjoint.

The crucial invariance is that

$f(c\,m)=f(c)$

whenever every prime factor of \(m\) is \(2\) or \(3\bmod4\). So once a core is fixed, all allowed multipliers below the remaining limit generate further valid values of \(N\).

If \(\mathcal M(X)\) denotes the set of allowed multipliers not exceeding \(X\), then

$A(X)=\sum_{m\in\mathcal M(X)} m.$

then the required sum is

$S(10^{11})=\sum_{c\in\mathcal C} c\cdot A\!\left(\left\lfloor\frac{10^{11}}{c}\right\rfloor\right),$

where \(\mathcal C\) is the set of distinct core numbers generated from the five exponent patterns.

Worked example

Consider

$N=5^3\cdot13^2\cdot17=359125.$

All three primes are \(1\bmod4\), and their exponents are \(3\), \(2\), and \(1\). Therefore

$f(N)=4(2\cdot3+1)(2\cdot2+1)(2\cdot1+1)=4\cdot7\cdot5\cdot3=420.$

Now multiply by \(2^4\cdot3\cdot7\). The new number

$N'=2^4\cdot3\cdot7\cdot5^3\cdot13^2\cdot17$

has the same exponents on its \(1\bmod4\) primes, so it still satisfies \(f(N')=420\). This is exactly the “core plus neutral multiplier” structure exploited by the algorithm.

How the Code Works

Enumerating admissible cores

The C++, Python, and Java implementations first sieve the primes \(p\equiv1\pmod4\) up to a safe bound, then generate every core number compatible with the five exponent patterns. Exponents are assigned to strictly increasing \(1\bmod4\) primes so that each factorization is produced once. If a partial product already exceeds the limit, or even the smallest possible completion would exceed the limit, that branch is pruned immediately.

Building the allowed-multiplier prefix sums

Once the smallest core is known, the maximum useful multiplier is \(\lfloor 10^{11}/c_{\min}\rfloor\). The implementation builds a smallest-prime-factor table up to that bound and marks exactly those integers whose prime divisors are all \(2\) or \(3\bmod4\). A prefix array then stores \(A(X)\), the sum of all allowed multipliers up to \(X\), for every relevant \(X\).

Adding the contributions

For each core \(c\), the algorithm computes \(X=\lfloor 10^{11}/c\rfloor\) and adds \(c\cdot A(X)\). That single lookup accounts for every valid number of the form \(c\,m\) without iterating over all such multiples individually. The C++ and Java implementations split this final sweep across several worker threads, while the Python implementation performs the same summation either serially or with process-level parallel work.

The C++ implementation also includes three consistency checks: it verifies the sample value \(f(10000)=36\), compares the arithmetic formula against direct geometric counting for small \(N\), and confirms that the fast summation matches a brute-force summation on a smaller limit.

Complexity Analysis

Let \(C\) be the number of distinct core numbers and let \(M=\lfloor 10^{11}/c_{\min}\rfloor\), where \(c_{\min}=5^3\cdot13^2\cdot17\) is the smallest valid core. Core generation is very small compared with the original search space, because only five exponent patterns exist and the recursive search is heavily pruned by monotonic growth of prime powers.

The sieve, validity table, and prefix sums over multipliers cost \(O(M)\) time and \(O(M)\) memory. The final accumulation over cores costs \(O(C)\). The method therefore replaces an impossible \(O(10^{11})\) search with a modest prime sieve, a compact enumeration of core numbers, and a linear preprocessing pass over the multiplier range.

Footnotes and References

1. Problem page: Project Euler 233 - Lattice Points on a Circle
2. Sum of two squares theorem: Fermat's theorem on sums of two squares
3. Representation count \(r_2(n)\): Sum of two squares function
4. Gaussian integers: Gaussian integer
5. Prime sieving background: Sieve of Eratosthenes