Detailed mathematical approach

Problem Summary

In a hexagonal orchard of order \(n\), every tree lies in one of six congruent triangular sectors around the center. A tree is hidden if another tree lies on the same ray from the center and is closer to the origin. The solution does not compare every pair of trees. Instead it turns visibility into a coprimality condition and then reduces the whole problem to evaluating the summatory Euler totient function.

Mathematical Approach

Step 1: Reduce the Hexagon to One Sector

Because the orchard has sixfold rotational symmetry, it is enough to count hidden trees in one \(60^\circ\) sector and multiply by 6 at the end. In one sector, row \(r\) contains exactly \(r\) trees for \(r=1,2,\dots,n\). Therefore the total number of trees in one sector is the triangular number

$T(n)=\sum_{r=1}^{n} r=\frac{n(n+1)}{2}.$

The center itself is only the observation point, so it is not included in this count.

Step 2: Visibility Becomes a GCD Test

Index the trees on row \(r\) by positions \(x=1,2,\dots,r\). In the lattice underlying one hexagonal sector, the tree \((x,r)\) lies on the same ray as \((x/d,r/d)\) whenever \(d\) divides both \(x\) and \(r\). Hence

$\text{tree }(x,r)\text{ is visible from the center} \iff \gcd(x,r)=1.$

If \(\gcd(x,r)=d>1\), then \((x/d,r/d)\) is a nearer tree on the same line of sight, so \((x,r)\) is hidden. If \(\gcd(x,r)=1\), there is no intermediate orchard point on that ray. The number of visible trees on row \(r\) is therefore

$\varphi(r)=\#\{1\le x\le r:\gcd(x,r)=1\},$

which is Euler's totient function. The number of hidden trees on row \(r\) is then

$r-\varphi(r).$

Step 3: Sum Hidden Trees Row by Row

Summing over all rows of one sector gives

$H_{\mathrm{sector}}(n)=\sum_{r=1}^{n}\bigl(r-\varphi(r)\bigr)=\frac{n(n+1)}{2}-\sum_{r=1}^{n}\varphi(r).$

Introduce the summatory totient function

$\Phi(n)=\sum_{k=1}^{n}\varphi(k).$

Then the hidden-tree count for the entire orchard is

$\boxed{H(n)=6\,H_{\mathrm{sector}}(n)=6\left(\frac{n(n+1)}{2}-\Phi(n)\right).}$

This closed form is exactly what the C++, Python, and Java programs evaluate.

Step 4: Derive the Recursive Formula for \(\Phi(n)\)

The code does not build all totients up to \(n\) with a full sieve. Instead it uses the classical divisor identity

$\sum_{d\mid m}\varphi(d)=m.$

Summing this identity for \(m=1,2,\dots,n\) yields

$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d\mid m}\varphi(d)=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$

Since \(\sum_{m=1}^{n} m=\frac{n(n+1)}{2}\), we obtain

$\frac{n(n+1)}{2}=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$

Now rewrite the right-hand side by expanding each floor term as a count of prefixes:

$\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{k=1}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$

Separating the \(k=1\) term gives the recurrence used in all three implementations:

$\Phi(n)=\frac{n(n+1)}{2}-\sum_{k=2}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$

Step 5: Quotient Grouping and Memoization

The recurrence still appears to contain \(n-1\) terms, but many consecutive indices produce the same quotient \(q=\left\lfloor n/k\right\rfloor\). If a block starts at left, its last index is

$\text{right}=\left\lfloor\frac{n}{q}\right\rfloor.$

So the entire block

$k=\text{left},\text{left}+1,\dots,\text{right}$

contributes

$(\text{right}-\text{left}+1)\,\Phi(q).$

This is exactly why the code keeps left, computes quotient = n / left, derives right = n / quotient, subtracts one whole block, and then jumps directly to right + 1. Memoization stores previously computed values of \(\Phi\), so each distinct recursive argument is evaluated only once.

Worked Example: \(n=5\)

For the first five rows we have

$\varphi(1)=1,\quad \varphi(2)=1,\quad \varphi(3)=2,\quad \varphi(4)=2,\quad \varphi(5)=4,$

so

$\Phi(5)=1+1+2+2+4=10.$

Also

$T(5)=\frac{5\cdot 6}{2}=15,$

hence

$H_{\mathrm{sector}}(5)=15-10=5,\qquad H(5)=6\cdot 5=30.$

This matches the checkpoint in the C++ file. The same source also checks \(H(10)=138\) and \(H(1000)=1177848\), plus a brute-force cross-check at order 200.

How the Code Works

All three solution files implement the same formula. They initialize a memo table with \(\Phi(0)=0\) and \(\Phi(1)=1\), compute the summatory totient recursively, evaluate the triangular number \(\frac{n(n+1)}{2}\), subtract the visible count in one sector, and multiply the result by 6.

The C++ version encapsulates the recursion in a TotientSummatory class backed by std::unordered_map and uses unsigned __int128 for intermediate arithmetic safety. The Python version uses a nested function with a dictionary, and the Java version uses a static HashMap<Long, Long>. The mathematical logic is identical in all three languages.

Complexity Analysis

A naive method would examine every tree in every row and test visibility with repeated \(\gcd\) calls, which is quadratic in the orchard order. The implemented method avoids that completely. For a fixed argument \(m\), the floor-division grouping visits only the distinct quotients \(\left\lfloor m/k\right\rfloor\), and there are \(O(\sqrt{m})\) of them. If \(S\) is the set of distinct arguments reached by memoized recursion, then the total running time is

$O\left(\sum_{m\in S}\sqrt{m}\right),$

with memory usage \(O(|S|)\) for the memo table. In practice this is dramatically smaller than computing and storing every totient value up to \(10^8\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=351
2. Euler's totient function: Wikipedia — Euler's totient function
3. Summatory totient function: Wikipedia — Summatory totient function
4. Visible points and coprimality: Wikipedia — Visible point
5. Triangular numbers: Wikipedia — Triangular number