Detailed mathematical approach

Problem Summary

Problem 883 asks for the value \(T(R_2)\) for remarkable triangles at \(R_2=2{,}000{,}000\). The implementations reduce the geometry to counting points in the triangular lattice, where a vector written in basis coordinates \((u,v)\) has squared length

$Q(u,v)=u^2+uv+v^2.$

The final answer is not obtained by one direct geometric count: it is a weighted sum over many scaled lattice counts, with Möbius inversion removing non-primitive overcounting.

Mathematical Approach

The triangular-lattice geometry behind remarkable triangles is encoded by the quadratic form \(Q(u,v)=u^2+uv+v^2\). The problem therefore becomes an arithmetic-geometric counting problem built from this norm form.

Step 1: Convert the Geometry into Lattice Counts

For a threshold \(M\), define

$A(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M\},$

$A_{\equiv}(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M,\ u\equiv v\pmod{3}\}.$

The unrestricted count \(A(M)\) measures all admissible lattice vectors up to squared length \(M\). The restricted count \(A_{\equiv}(M)\) keeps only the congruence class needed when a factor of \(3\) has to be absorbed separately. The implementation evaluates these two families for many values of

$M=\left\lfloor\frac{R_2^2}{t^2}\right\rfloor.$

Step 2: Count Integer Pairs Efficiently for One Threshold

The key identity is

$4Q(u,v)=(2v+u)^2+3u^2.$

After fixing \(u\), the condition \(Q(u,v)\le M\) becomes

$ (2v+u)^2\le 4M-3u^2. $

So \(u\) only needs to range over

$0\le u\le \left\lfloor\sqrt{\frac{4M}{3}}\right\rfloor.$

If we set

$s=\left\lfloor\sqrt{4M-3u^2}\right\rfloor,$

then the admissible integers \(v\) satisfy

$\left\lceil\frac{-u-s}{2}\right\rceil \le v \le \left\lfloor\frac{-u+s}{2}\right\rfloor.$

The interval length gives the number of points for this \(u\). Because replacing \((u,v)\) by \((-u,-v)\) preserves \(Q\), the implementation loops over \(u\ge0\) and doubles the contribution whenever \(u>0\).

Step 3: Explain the Special Congruence Channel

The restricted counter comes from the identity

$Q(u,v)=u^2+uv+v^2=(u-v)^2+3uv,$

which implies

$Q(u,v)\equiv (u-v)^2 \pmod{3}.$

Therefore

$3\mid Q(u,v)\iff u\equiv v\pmod{3}.$

This is why the second channel counts only those values of \(v\) in the interval above that satisfy \(v\equiv u\pmod{3}\). In Eisenstein-lattice language, the prime \(3\) is ramified, so multiples of \(3\) must be handled by a separate congruence condition rather than by the ordinary channel.

Step 4: Build the Arithmetic Weights from Prime Factorization

Let

$n=3^{e_3}\prod_{p\equiv1\pmod{3}}p^{\alpha_p}\prod_{q\equiv2\pmod{3}}q^{\beta_q}.$

The arithmetic part of the solution distinguishes the three Eisenstein prime types: split primes \(p\equiv1\pmod{3}\), inert primes \(q\equiv2\pmod{3}\), and the ramified prime \(3\). Define

$\tau_2(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1)\prod_{q\equiv2\pmod{3}}(2\beta_q+1),$

$P_1(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1),\qquad \chi(n)=(-1)^{\sum_{q\equiv2\pmod{3}}\beta_q}.$

The raw multiplicative weight used by the implementation is

$f(n)= \begin{cases} \tau_2(n)\,(2e_3-1), & e_3\ge 1,\\[4pt] \dfrac{\tau_2(n)+\chi(n)P_1(n)}{2}, & e_3=0. \end{cases}$

This formula comes directly from how the relevant similarity classes split according to the behavior of primes modulo \(3\). The factor \(3\) contributes differently from the other primes, which is why it is peeled off first.

Step 5: Use Möbius Inversion to Keep Only Primitive Objects

The raw weight \(f(n)\) still counts configurations that share a nontrivial common divisor in the Eisenstein sense. To isolate the primitive contribution, the implementation applies Möbius inversion:

$h(n)=(f*\mu)(n)=\sum_{d\mid n} f(d)\,\mu\!\left(\frac{n}{d}\right).$

This Dirichlet convolution removes the contributions that come from scaling up a smaller primitive configuration.

Step 6: Combine the Two Sampling Channels

For each \(n\le 3R_2\), the implementations attach a lattice count \(F_n\) to the weight \(h(n)\):

$F_n= \begin{cases} A\!\left(\left\lfloor\frac{R_2^2}{n^2}\right\rfloor\right)-1, & 3\nmid n,\\[6pt] A_{\equiv}\!\left(\left\lfloor\frac{R_2^2}{(n/3)^2}\right\rfloor\right)-1, & 3\mid n. \end{cases}$

The subtraction of \(1\) removes the origin. The main accumulated sum is

$S(R_2)=\sum_{n=1}^{3R_2} h(n)\,F_n.$

A final symmetry correction is then applied:

$E(R_2)=\frac{A(R_2^2)-1}{3},\qquad \boxed{T(R_2)=S(R_2)-2E(R_2).}$

The division by \(3\) is valid for the unrestricted nonzero lattice count and reflects the threefold rotational symmetry that would otherwise be counted too many times.

Worked Example: \(R_2=1\)

This is the smallest checkpoint used by the implementations, and it already shows every moving part. First, \(Q(u,v)\le1\) gives the origin plus the six unit directions, so

$A(1)=7,\qquad A_{\equiv}(1)=1.$

Hence

$F_1=A(1)-1=6,\qquad F_3=A_{\equiv}(1)-1=0.$

Next, compute the raw weights:

$f(1)=1,\qquad f(2)=\frac{3+(-1)\cdot1}{2}=1,\qquad f(3)=1.$

Using \(\mu(1)=1\), \(\mu(2)=-1\), and \(\mu(3)=-1\), Möbius inversion gives

$h(1)=1,\qquad h(2)=f(1)\mu(2)+f(2)\mu(1)=0,\qquad h(3)=f(1)\mu(3)+f(3)\mu(1)=0.$

Therefore only \(n=1\) contributes:

$S(1)=1\cdot 6=6,\qquad E(1)=\frac{7-1}{3}=2,$

so the final value is

$T(1)=6-2\cdot2=2,$

matching the validation output.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. They first build a smallest-prime-factor table and the Möbius function up to \(3R_2\). That data is enough to factor every integer \(n\), evaluate the multiplicative weight \(f(n)\), and then form the primitive weight \(h(n)\) by Dirichlet convolution.

Separately, the implementation precomputes the geometric tables for every \(1\le t\le R_2\): the unrestricted lattice count and the congruence-restricted lattice count at \(M=\left\lfloor R_2^2/t^2\right\rfloor\). The C++ version parallelizes this heavy phase; the Java version performs the same logic directly; the Python version delegates to the compiled computation so that the arithmetic and geometric steps stay identical. Once those tables exist, the program performs one final pass over \(n\le 3R_2\), chooses the correct channel according to divisibility by \(3\), accumulates \(h(n)F_n\), and finally applies the symmetry correction \(2E(R_2)\).

Complexity Analysis

For one threshold \(M\), the lattice counter runs through \(u=0,1,\dots,\left\lfloor\sqrt{4M/3}\right\rfloor\), so a single evaluation costs \(O(\sqrt{M})\) time and \(O(1)\) extra memory. Summed over all \(t\le R_2\), this becomes

$\sum_{t=1}^{R_2} O\!\left(\sqrt{\frac{R_2^2}{t^2}}\right)=\sum_{t=1}^{R_2} O\!\left(\frac{R_2}{t}\right)=O(R_2\log R_2).$

The sieve stage is linear or near-linear in \(3R_2\), and the Dirichlet-convolution pass costs \(O(R_2\log R_2)\) overall. Memory usage is \(O(R_2)\): the arithmetic arrays have length \(3R_2+1\), and the geometric tables have length \(R_2+1\). Parallel execution improves wall-clock time for the geometric phase but does not change the asymptotic bounds.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=883
2. Eisenstein integers: Wikipedia — Eisenstein integer
3. Triangular lattice: Wikipedia — Triangular lattice
4. Möbius inversion formula: Wikipedia — Möbius inversion formula
5. Dirichlet convolution: Wikipedia — Dirichlet convolution