Detailed mathematical approach

Problem Summary

Project Euler 372 defines \(R(M,N)\) as the number of lattice points \((x,y)\) such that \(M \lt x \le N\), \(M \lt y \le N\), and

$\left\lfloor \frac{y^2}{x^2} \right\rfloor$

is odd. The implementation uses the parameter names m and n, so below we write \(R(m,n)\) and set \(\ell=m+1\). We must therefore count all integer pairs

$\ell \le x \le n,\qquad \ell \le y \le n,$

for which the squared slope \((y/x)^2\) falls into an odd strip \([k,k+1)\).

Mathematical Approach

Step 1: Split the plane by the odd floor value

For every odd integer \(k \ge 1\), define

$A_k=\left\{(x,y)\in \mathbb{Z}^2:\ell \le x,y \le n,\ k \le \frac{y^2}{x^2} \lt k+1\right\}.$

The sets \(A_k\) are disjoint, and every admissible lattice point belongs to exactly one such set because the floor value is unique. Therefore

$R(m,n)=\sum_{\substack{k \ge 1\\k\text{ odd}}} |A_k|.$

Since \(x \ge \ell\) and \(y \le n\), we have

$\frac{y^2}{x^2}\le \frac{n^2}{\ell^2},$

so only odd \(k\) up to

$K_{\max}=\left\lfloor\frac{n^2}{\ell^2}\right\rfloor$

can contribute. This is the outer loop in all three solution files.

Step 2: Count valid \(y\) for fixed \(x\) and odd \(k\)

Fix an odd \(k\) and an \(x\). The condition

$k \le \frac{y^2}{x^2} \lt k+1$

is equivalent to

$x\sqrt{k}\le y \lt x\sqrt{k+1}.$

Because \(y\) is an integer and we also need \(y \le n\), the number of admissible \(y\)-values is

$C_k(x)=\max\!\left(0,\ \min\!\bigl(n+1,\lceil x\sqrt{k+1}\rceil\bigr)-\lceil x\sqrt{k}\rceil\right).$

The form with \(n+1\) is convenient because the count of integers in a half-open interval \([a,b)\cap \mathbb{Z}\) is \(\lceil b\rceil-\lceil a\rceil\), and truncating at \(y \le n\) means replacing the upper endpoint by \(n+1\).

Step 3: Determine the two relevant \(x\)-ranges

The lower bound \(y \ge \lceil x\sqrt{k}\rceil\) is impossible once \(x\sqrt{k} \gt n\). Therefore define

$u_k=\left\lfloor\frac{n}{\sqrt{k}}\right\rfloor.$

Only \(x \le u_k\) can contribute.

The upper endpoint changes behavior when \(x\sqrt{k+1}\) crosses \(n+1\). Define

$v_k=\left\lfloor\frac{n+1}{\sqrt{k+1}}\right\rfloor.$

Then we have two cases:

$C_k(x)=\lceil x\sqrt{k+1}\rceil-\lceil x\sqrt{k}\rceil \qquad (\ell \le x \le \min(u_k,v_k)),$

$C_k(x)=(n+1)-\lceil x\sqrt{k}\rceil \qquad (\max(\ell,v_k+1)\le x \le u_k).$

This is exactly why the code splits each odd \(k\) into the intervals \([\ell,\min(u_k,v_k)]\) and \([\max(\ell,v_k+1),u_k]\).

Step 4: Reduce everything to interval sums of \(\lceil x\sqrt{d}\rceil\)

Let

$T_d(a,b)=\sum_{x=a}^{b}\lceil x\sqrt{d}\rceil.$

For one odd \(k\), set

$x_1=\min(u_k,v_k),\qquad x_2=\max(\ell,v_k+1).$

Then the full contribution of \(k\) is

$\sum_{x=\ell}^{x_1}\bigl(\lceil x\sqrt{k+1}\rceil-\lceil x\sqrt{k}\rceil\bigr) +\sum_{x=x_2}^{u_k}\bigl((n+1)-\lceil x\sqrt{k}\rceil\bigr),$

that is,

$T_{k+1}(\ell,x_1)-T_k(\ell,x_1)+(u_k-x_2+1)(n+1)-T_k(x_2,u_k).$

So the geometric lattice-point problem has been converted into fast evaluation of interval sums of the form \(T_d(a,b)\).

Step 5: Compute \(T_d(a,b)\) with a Beatty-type floor-sum recursion

If \(d=s^2\) is a perfect square, then \(\lceil x\sqrt{d}\rceil=sx\), so

$T_d(a,b)=s\sum_{x=a}^{b}x=s\frac{(a+b)(b-a+1)}{2}.$

The non-square case is the interesting one. Define the prefix sum

$F_d(N)=\sum_{x=1}^{N}\lfloor x\sqrt{d}\rfloor.$

For non-square \(d\), every \(x\sqrt{d}\) is irrational, hence \(\lceil x\sqrt{d}\rceil=\lfloor x\sqrt{d}\rfloor+1\), and therefore

$T_d(a,b)=F_d(b)-F_d(a-1)+(b-a+1).$

The helper class computes a more general quantity

$F_{d,p,q}(N)=\sum_{i=1}^{N}\left\lfloor i\frac{\sqrt{d}+p}{q}\right\rfloor,$

with the target value \(F_d(N)=F_{d,0,1}(N)\). Write

$\alpha=\frac{\sqrt{d}+p}{q}=a+\beta,\qquad a=\lfloor \alpha \rfloor,\qquad 0 \lt \beta \lt 1.$

The transformed parameters used by the code are

$p_1=aq-p,\qquad q_1=\frac{d-p_1^2}{q}.$

Then

$\beta=\frac{\sqrt{d}-p_1}{q},\qquad \frac{1}{\beta}=\frac{\sqrt{d}+p_1}{q_1}.$

If we set

$r=\left\lfloor N\beta \right\rfloor=\left\lfloor \frac{N\sqrt{d}-Np_1}{q}\right\rfloor,$

the complementary Beatty identity yields

$\sum_{i=1}^{N}\lfloor i\beta\rfloor = Nr - F_{d,p_1,q_1}(r).$

Since \(\lfloor i\alpha\rfloor = ai + \lfloor i\beta\rfloor\), we obtain the recurrence used verbatim by the implementation:

$\boxed{F_{d,p,q}(N)=a\frac{N(N+1)}{2}+Nr-F_{d,p_1,q_1}(r).}$

Memoization on the key \((d,p,q,N)\) makes repeated prefix queries cheap, which is essential because neighboring odd \(k\)-layers call the same surd sums again and again.

Worked Example: \(R(0,5)=7\)

Take \(m=0\), \(n=5\), so \(\ell=1\) and \(K_{\max}=\lfloor 25/1\rfloor=25\). In practice only \(k=1\) contributes. For \(k=1\),

$u_1=\left\lfloor\frac{5}{1}\right\rfloor=5,\qquad v_1=\left\lfloor\frac{6}{\sqrt{2}}\right\rfloor=4.$

So

$\sum_{x=1}^{4}\bigl(\lceil x\sqrt{2}\rceil-\lceil x\rceil\bigr) +\sum_{x=5}^{5}\bigl(6-\lceil x\rceil\bigr)$

becomes

$[(2-1)+(3-2)+(5-3)+(6-4)] + (6-5)=6+1=7.$

The valid points are \((1,1),(2,2),(3,3),(3,4),(4,4),(4,5),(5,5)\), confirming the decomposition.

How the Code Works

The C++, Python, and Java programs implement the same structure.

First, k_max = (n*n)/(l*l) bounds the odd layers. For each odd \(k\), the helpers floor_div_by_sqrt / floor_div_sqrt / isqrt((t*t)/d) compute \(\lfloor t/\sqrt{d}\rfloor\) exactly using integer square roots, avoiding floating-point boundary errors.

Next, sum_ceil_sqrt returns \(T_d(a,b)\). Perfect squares are handled by the closed arithmetic-series formula. Otherwise the program asks BeattySumSqrt for prefix floor sums and converts them into ceiling sums. The recursive helper starts from a floating estimate for \(\left\lfloor\frac{a\sqrt{d}+b}{c}\right\rfloor\), then corrects the estimate by exact integer comparisons, so the final result is mathematically exact.

Finally, the total contribution of each odd \(k\) is added to a big integer accumulator. The C++ version also checks the published checkpoints \(R(0,100)=3019\) and \(R(100,10000)=29750422\) before computing the final answer.

Complexity Analysis

Let \(K_{\max}=\lfloor n^2/\ell^2\rfloor\). The outer enumeration touches only the odd integers up to \(K_{\max}\), so there are \(O(K_{\max})\) main iterations. Each iteration performs a constant number of exact boundary computations and up to three interval sums \(T_d(a,b)\).

When \(d\) is a square, the interval sum is \(O(1)\). Otherwise it is evaluated by the memoized quadratic-irrational recurrence above; the recursion depth is small in practice and repeated states are reused aggressively. A safe way to summarize the implementation is

$O\!\bigl(K_{\max}\cdot T_{\mathrm{surd}}\bigr)\ \text{time},$

where \(T_{\mathrm{surd}}\) is the amortized cost of one memoized Beatty query, with memory proportional to the number of cached states. For the actual parameters \(m=2\cdot 10^6\) and \(n=10^9\), this is fast enough because \(K_{\max}\approx 2.5\cdot 10^5\), not \(10^{18}\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=372
2. Beatty sequence and complementary sequences: Wikipedia — Beatty sequence
3. Floor function and lattice strip counting: Wikipedia — Floor and ceiling functions
4. Integer square root: Wikipedia — Integer square root