Detailed mathematical approach

Problem Summary

For integers \(R \gt r \gt 0\), the hypocycloid is defined by

$x(t)=(R-r)\cos t+r\cos\!\left(\frac{R-r}{r}t\right), \qquad y(t)=(R-r)\sin t-r\sin\!\left(\frac{R-r}{r}t\right).$

We only keep parameters \(t\) for which \(\sin t\) and \(\cos t\) are rational, and among those points we keep only the ones with integer coordinates. For a fixed pair \((R,r)\), let \(S(R,r)\) be the sum of \(|x|+|y|\) over the distinct lattice points obtained this way. The global target is

$T(N)=\sum_{3\le R\le N}\sum_{1\le r\lt R/2} S(R,r).$

The implementations verify the checkpoints \(S(3,1)=10\), \(T(10)=524\), \(T(100)=580442\), and \(T(1000)=583108600\).

Mathematical Approach

Step 1: Separate the Common Scale

Write

$R=gp,\qquad r=gq,\qquad \gcd(p,q)=1,\qquad e=p-q.$

The condition \(r\lt R/2\) becomes \(q \lt p/2\), so \(e \gt q\). Now set \(t=q\theta\) and define \(z=e^{i\theta}\). Then \(z^q=e^{it}\), and the hypocycloid coordinates combine into one complex expression:

$x+iy=g\left(ez^q+q\overline{z}^{\,e}\right).$

This identity is the key simplification. For each reduced pair \((p,q)\), the geometry is fixed, and changing \(g\) only scales the final lattice point linearly.

Step 2: Rational Points on the Unit Circle

Every rational point on the unit circle can be written as

$z=\frac{A+iB}{D},\qquad A^2+B^2=D^2,\qquad \gcd(A,B)=1.$

The trivial case \(D=1\) gives the four roots of unity \((\pm1,0)\) and \((0,\pm1)\). Every nontrivial rational point comes from a primitive Pythagorean triple, together with sign changes and swapping the two legs.

Substituting this parametrization into the complex form gives

$x+iy=\frac{g}{D^e}\left(e(A+iB)^qD^{e-q}+q(A-iB)^e\right).$

If we write

$U_x+iU_y=e(A+iB)^qD^{e-q}+q(A-iB)^e,$

then the entire arithmetic question becomes: after cancelling the common factors of \(D^e\), when does the remaining denominator divide \(g\)?

Step 3: Exact Integrality Criterion

Let

$g_0=\gcd(D^e,U_x,U_y),\qquad \delta=\frac{D^e}{g_0}.$

After reducing the fraction, the point becomes

$\left(x,y\right)=\frac{g}{\delta}\left(\frac{U_x}{g_0},\frac{U_y}{g_0}\right).$

Therefore the coordinates are integers if and only if

$\delta \mid g.$

If \(g=m\delta\), then this one geometric shape contributes

$m\left(\left|\frac{U_x}{g_0}\right|+\left|\frac{U_y}{g_0}\right|\right).$

Summing over all admissible multiples of \(\delta\) produces a triangular number:

$\sum_{m=1}^{m_{\max}} m=\frac{m_{\max}(m_{\max}+1)}{2},\qquad m_{\max}=\left\lfloor\frac{N/p}{\delta}\right\rfloor.$

This is why the global computation can be organized by reduced shapes instead of looping over all \((R,r)\) one by one.

Step 4: The \(D=1\) Case Produces the Main Term

When \(D=1\), the only rational unit-circle points are the four roots of unity. For a fixed reduced pair \((p,q)\) and a scale \(g\), their total Manhattan contribution is

$C_0(p,q,g)=g\begin{cases} 4p-2q,& p \text{ odd},\\ 4p,& 4\mid p,\\ 4p-4q,& p\equiv 2 \pmod 4. \end{cases}$

The parity of \(p\) determines whether one axis pair has norm \(p\) or \(p-2q\). A small example is \((R,r)=(3,1)\), where \((g,p,q,e)=(1,3,1,2)\). The four points are

$ (3,0),\quad (-1,0),\quad (-1,2),\quad (-1,-2), $

so

$S(3,1)=3+1+3+3=10.$

Step 5: Sum the Main Term with Totients and Möbius Inversion

For a fixed \(p\), define

$A(p)=\#\{1\le q \lt p/2:\gcd(p,q)=1\}=\frac{\varphi(p)}2,$

and

$Q(p)=\sum_{\substack{1\le q \lt p/2\\ \gcd(p,q)=1}} q.$

If \(M_p=\lfloor N/p\rfloor\), then the full \(D=1\) contribution is

$T_{\mathrm{main}}(N)=\sum_{p=3}^{N} C_{\mathrm{main}}(p)\frac{M_p(M_p+1)}{2},$

with

$C_{\mathrm{main}}(p)=\begin{cases} 4pA(p)-2Q(p),& p \text{ odd},\\ 4pA(p),& 4\mid p,\\ 4pA(p)-4Q(p),& p\equiv 2 \pmod 4. \end{cases}$

The nontrivial part is the coprime sum \(Q(p)\). Möbius inversion removes the gcd condition:

$Q(p)=\sum_{d\mid p}\mu(d)\,d\,\frac{m_d(m_d+1)}{2},\qquad m_d=\left\lfloor\frac{p-1}{2d}\right\rfloor.$

This is exactly the divisor sum accumulated by the implementation before the final outer summation over \(p\).

Step 6: Explicit Correction for \(D \gt 1\)

All remaining lattice points come from nontrivial rational points on the unit circle, so \(D \gt 1\). For each reduced pair \((p,q)\), each primitive Pythagorean triple, and each sign or coordinate-swap symmetry, Step 3 gives a required denominator \(\delta\). Whenever \(\delta\le M_p\), that one family contributes

$\left(\left|\frac{U_x}{g_0}\right|+\left|\frac{U_y}{g_0}\right|\right)\frac{m_{\max}(m_{\max}+1)}{2},\qquad m_{\max}=\left\lfloor\frac{M_p}{\delta}\right\rfloor.$

The direct single-pair routine removes coincident points explicitly before summing \(|x|+|y|\). For the bulk computation of \(T(N)\), the implementations combine the closed form for \(D=1\) with this explicit \(D \gt 1\) correction. At \(N=10^6\), the correction is validated to vanish for \(p \gt 12\), so the expensive branch can be truncated safely.

How the Code Works

The C++, Python, and Java implementations all follow the same plan. They first build tables for the Möbius function and Euler's totient function up to \(N\). Those tables are then used to accumulate the divisor sums needed for \(Q(p)\), which yields the dominant arithmetic contribution from the \(D=1\) case.

After that, the implementation enumerates primitive Pythagorean triples only for the nontrivial \(D \gt 1\) branch. For each admissible reduced pair and each rational unit-circle point generated from the triple symmetries, it computes the reduced denominator \(\delta\) and adds the corresponding triangular-scale contribution. A separate direct evaluator for one pair \((R,r)\) is used for checkpoint verification and deduplicates geometric coincidences explicitly.

Complexity Analysis

The sieve for \(\mu\) and \(\varphi\) is \(O(N)\) time and \(O(N)\) memory. The divisor accumulation that evaluates the Möbius formula for every \(p\le N\) is near-linear, with the usual \(O(N\log\log N)\) sieve-like behavior. The \(D \gt 1\) correction is much smaller in practice because only small reduced \(p\) values survive the validation cutoff and most primitive triples are eliminated immediately by the denominator test. Overall the method is dominated by arithmetic precomputation with \(O(N)\) storage.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=450
2. Hypocycloid: Wikipedia — Hypocycloid
3. Rational points on the unit circle and primitive triples: Wikipedia — Pythagorean triple
4. Möbius inversion: Wikipedia — Möbius inversion formula
5. Euler's totient function: Wikipedia — Euler's totient function