Detailed mathematical approach

Problem Summary

For each integer \(k \ge 1\), consider the parabola \(y=\dfrac{x^2}{k}\). We choose three distinct integers \(a \lt b \lt c\) with \(|a|,|b|,|c|\le X\), form the points \(A=\left(a,\dfrac{a^2}{k}\right)\), \(B=\left(b,\dfrac{b^2}{k}\right)\), \(C=\left(c,\dfrac{c^2}{k}\right)\), and ask whether triangle \(ABC\) has at least one \(45^\circ\) angle. Let \(T_k(X)\) be that count for fixed \(k\). The program computes

$F(K,X)=\sum_{k=1}^{K} T_k(X).$

The key reduction is that chord slopes on this parabola depend only on pair sums such as \(a+b\), so the geometry becomes a divisor problem for \(2k^2\) plus interval counting for the remaining coordinate.

Mathematical Approach

Step 1: Replace Geometry by Pair Sums

Define

$x=a+b,\qquad y=a+c,\qquad z=b+c,$

so \(x \lt y \lt z\) because \(a \lt b \lt c\). The slope of a chord between two points on \(y=\dfrac{x^2}{k}\) is

$m_{uv}=\frac{v^2-u^2}{k(v-u)}=\frac{u+v}{k}.$

Therefore the three side slopes are exactly

$m_{AB}=\frac{x}{k},\qquad m_{AC}=\frac{y}{k},\qquad m_{BC}=\frac{z}{k}.$

This is the crucial simplification: once \((x,y,z)\) are known, the angle conditions no longer involve quadratic expressions in \(a,b,c\).

Step 2: Convert the \(45^\circ\) Condition into Diophantine Equations

At vertex \(A\), the two scaled direction vectors are proportional to \((k,x)\) and \((k,y)\). A \(45^\circ\) angle means that the cross-product magnitude equals the dot product:

$k(y-x)=k^2+xy.$

After rearranging, we obtain

$xy+kx-ky+k^2=0,$

hence

$\boxed{(x-k)(y+k)=-2k^2.}$

At vertex \(B\), the relevant scaled direction vectors are proportional to \((-k,-x)\) and \((k,z)\). The same \(45^\circ\) criterion gives

$k(z-x)=-(k^2+xz),$

so

$\boxed{(x+k)(z-k)=-2k^2.}$

At vertex \(C\), the symmetric computation yields

$\boxed{(y-k)(z+k)=-2k^2.}$

Thus every admissible triangle is encoded by one of three factor equations whose right-hand side is the fixed integer \(-2k^2\). No floating-point trigonometry is needed anywhere in the solver.

Step 3: Enumerate Candidate Pair Sums from Divisors of \(2k^2\)

Write \(pq=-2k^2\). The implementation enumerates every positive divisor \(d\mid 2k^2\), then uses the two signs \(p=\pm d\) and sets \(q=-2k^2/p\).

For the \(A\)- and \(C\)-families we solve \((u-k)(v+k)=-2k^2\), so

$u=p+k,\qquad v=q-k.$

For the \(B\)-family we solve \((u+k)(v-k)=-2k^2\), so

$u=p-k,\qquad v=q+k.$

Only pairs with \(u \lt v\) and \(|u|,|v|\le 2X\) can come from actual sums of numbers in \([-X,X]\), so the code filters to that range immediately, sorts the resulting lists, and removes duplicates. Different divisors and sign choices can generate the same \((u,v)\), so this deduplication is essential.

Step 4: Count the Missing Coordinate by Integer Intervals

Once a valid pair of sums is known, the third step is not another search; it is just an interval-length computation.

For an angle at \(A\), the pair is \((x,y)=(a+b,a+c)\). Then \(b=x-a\) and \(c=y-a\). Using \(-X\le a,b,c\le X\) and \(a \lt b \lt c\), the allowed values of \(a\) satisfy

$a\in\left[\max(-X,y-X),\ \min\!\left(X,x+X,\left\lfloor\frac{x-1}{2}\right\rfloor\right)\right].$

For an angle at \(B\), the pair is \((x,z)=(a+b,b+c)\), so \(a=x-b\), \(c=z-b\), and

$b\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{x}{2}\right\rfloor+1\right),\ \min\!\left(X,x+X,\left\lfloor\frac{z-1}{2}\right\rfloor\right)\right].$

For an angle at \(C\), the pair is \((y,z)=(a+c,b+c)\), so \(a=y-c\), \(b=z-c\), and

$c\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{z}{2}\right\rfloor+1\right),\ \min(X,y+X)\right].$

The helper functions count_angle_a_for_pair, count_angle_b_for_pair, and count_angle_c_for_pair implement exactly these formulas. Because sums can be negative, the C++ and Java versions use a custom floor_div instead of truncating division.

Step 5: Remove Double Counts by Reconstructing \((a,b,c)\)

A triangle can have two \(45^\circ\) angles, so inclusion-exclusion is needed:

$T_k(X)=N_A+N_B+N_C-N_{AB}-N_{AC}-N_{BC}.$

When two families agree on the shared sum, we recover the original integer parameters from the ordered sums \(x \lt y \lt z\):

$a=\frac{x+y-z}{2},\qquad b=\frac{x+z-y}{2},\qquad c=\frac{y+z-x}{2}.$

The function valid_triangle_from_sums checks exactly what this reconstruction requires: strict order, even parity of \(x+y+z\), and \(|a|,|b|,|c|\le X\). The overlaps are found by linear merges of sorted pair lists, so the correction step is \(O(n)\) after sorting.

Worked Example

Take \(k=1\) and \((a,b,c)=(-3,0,2)\). Then the points are \(A=(-3,9)\), \(B=(0,0)\), \(C=(2,4)\), and

$x=a+b=-3,\qquad z=b+c=2.$

The middle-angle equation becomes

$\left(x+1\right)\left(z-1\right)=(-2)(1)=-2=-2\cdot 1^2,$

so the code classifies this triangle in the \(B\)-family and counts it as a \(45^\circ\) triangle. At a larger checkpoint, the program verifies that

$F(1,10)=41,$

which is the same reference value hardcoded in the C++ solution.

How the Code Works

The C++ implementation builds an SPF table once up to the maximum required \(k\), factors each \(2k^2\) in factor_2k_squared, recursively generates all divisors, constructs the two candidate pair lists in build_pairs_for_k, evaluates the interval formulas, and subtracts overlaps with three sorted merge-scans. The C++ version can split the \(k\)-range across threads. The Python file is intentionally not a second mathematical implementation: it is a thin bridge that compiles and runs the C++ solver, then parses the final line. The Java file is a direct arithmetic port of the same method and parallelizes with LongStream.rangeClosed(...).parallel().

Complexity Analysis

Building the SPF sieve up to \(K\) costs \(O(K\log\log K)\) time and \(O(K)\) memory. For fixed \(k\), let \(D_k=d(2k^2)\) be the number of divisors of \(2k^2\). Divisor generation is \(O(D_k)\), interval accumulation is linear in the number of surviving pairs, and sorting/deduplication dominates at roughly \(O(D_k\log D_k)\). The three overlap corrections are linear merges after sorting. Therefore the overall complexity is

$O\!\left(K\log\log K+\sum_{k=1}^{K} D_k\log D_k\right),$

with \(O(K)\) global memory for the sieve and \(O(D_k)\) temporary memory per worker.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=397
2. Parabola and chord geometry: Wikipedia — Parabola
3. Angle between two lines: Wikipedia — Angle between two lines
4. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle
5. Sieve of Eratosthenes / smallest prime factors: Wikipedia — Sieve of Eratosthenes