Detailed mathematical approach

Problem Summary

For a given \(n\), define the stations

$$P_i=\left(2^i \bmod n,\ 3^i \bmod n\right),\qquad 0 \le i \le 2n.$$

An uphill path from \((0,0)\) to \((n,n)\) uses only right and up moves, so the stations visited by such a path must appear in an order whose coordinates never decrease. Let \(S(n)\) be the maximum number of stations that can be visited by one uphill path. The program evaluates

$$\sum_{k=1}^{30} S(k^5).$$

Mathematical Approach

The implementation does not search over grid paths directly. Instead, it reduces the problem to a finite set of modular points and then solves an order problem on those points.

1) Reduce the Station Sequence to a Finite Prefix

Write

$$n = 2^{\alpha} 3^{\beta} m,\qquad \gcd(m,6)=1.$$

Consider the \(x\)-coordinate \(x_i = 2^i \bmod n\). For every \(i \ge \alpha\), the factor \(2^{\alpha}\) already divides \(2^i\), so modulo \(2^{\alpha}\) the value is fixed at \(0\). On the coprime part \(n / 2^{\alpha}\), the base \(2\) is invertible, hence the remaining behavior is purely periodic with period

$$T_2 = \operatorname{ord}_{n / 2^{\alpha}}(2),$$

with the harmless convention \(T_2=1\) when \(n / 2^{\alpha}=1\). Thus the \(x\)-coordinate is eventually periodic after \(\alpha\) steps.

Exactly the same argument applies to the \(y\)-coordinate \(y_i = 3^i \bmod n\). After \(\beta\) steps it is periodic with period

$$T_3 = \operatorname{ord}_{n / 3^{\beta}}(3),$$

again taking \(T_3=1\) when the modulus equals \(1\).

Therefore the pair sequence \((x_i,y_i)\) is periodic from

$$p = \max(\alpha,\beta)$$

onward, with common period

$$T = \operatorname{lcm}(T_2,T_3).$$

Every station with index \(i \ge p+T\) repeats one already seen in the block \(p, p+1, \dots, p+T-1\). Since the original problem only uses indices \(0 \le i \le 2n\), it is enough to generate

$$M = \min(2n+1,\ p+T)$$

points and then discard duplicates.

2) Convert Uphill Paths into a Longest Nondecreasing Subsequence

After deduplication, sort the distinct stations lexicographically by \(x\) and then by \(y\):

$$Q_1,\dots,Q_r,\qquad Q_j=(x_j,y_j),\qquad x_1 \le x_2 \le \cdots \le x_r.$$

If an uphill path visits stations \(Q_{j_1}, Q_{j_2}, \dots, Q_{j_t}\), then necessarily

$$x_{j_1} \le x_{j_2} \le \cdots \le x_{j_t},\qquad y_{j_1} \le y_{j_2} \le \cdots \le y_{j_t}.$$

Because the list is already sorted by \(x\), the first condition is automatic when we take an increasing index subsequence. So the entire problem becomes

$$S(n)=\operatorname{LNDS}(y_1,y_2,\dots,y_r),$$

where \(\operatorname{LNDS}\) denotes the length of the longest nondecreasing subsequence.

The word nondecreasing matters. Equal \(x\)-coordinates are allowed because a path can move vertically between two stations, and equal \(y\)-coordinates are allowed because it can move horizontally. That is why the implementation uses the patience-sorting variant based on the first tail strictly greater than the new \(y\)-value.

3) Worked Example: \(n=22\)

For \(n=22=2\cdot 11\), we have \(\alpha=1\) and \(\beta=0\). Hence

$$T_2=\operatorname{ord}_{11}(2)=10,\qquad T_3=\operatorname{ord}_{22}(3)=5,$$

so

$$p=1,\qquad T=\operatorname{lcm}(10,5)=10,\qquad M=\min(45,11)=11.$$

Thus all relevant stations already occur among the first \(11\) indices. After sorting and removing repeats, the \(y\)-sequence is

$$1,3,9,15,5,1,1,5,15,9,3.$$

Its longest nondecreasing subsequence has length \(5\), so

$$S(22)=5.$$

This matches the checkpoint used by the implementation. The same program also verifies \(S(123)=14\) and \(S(10000)=48\).

How the Code Works

The C++, Python, and Java implementations build a smallest-prime-factor table once up to \(30^5\). That table makes Euler's totient function and multiplicative orders fast to evaluate for every modulus \(n=k^5\).

For each \(k\in\{1,\dots,30\}\), the implementation forms \(n=k^5\), computes the preperiod length \(p\) and the common period \(T\), generates the first \(M\) stations, sorts and deduplicates them, and finally applies patience sorting with binary search to the \(y\)-coordinates. The Python entry point reuses the same compiled computation, while the Java version mirrors the same mathematics directly.

Complexity Analysis

For one modulus \(n\), let \(M=\min(2n+1,p+T)\), and let \(r\le M\) be the number of distinct stations after deduplication. Generating the modular points costs \(O(M)\). Sorting the distinct points costs \(O(r\log r)\), and the longest-nondecreasing-subsequence step also costs \(O(r\log r)\). Therefore one evaluation of \(S(n)\) runs in

$$O(r\log r)$$

time and uses \(O(r)\) memory.

Across all \(k \le 30\), the one-time prime-factor sieve up to \(30^5\) is near-linear and uses \(O(30^5)\) memory. After that precomputation, the point ordering work dominates.

References

1. Problem page: https://projecteuler.net/problem=411
2. Multiplicative order: Wikipedia — Multiplicative order
3. Euler's totient function: Wikipedia — Euler's totient function
4. Chinese remainder theorem: Wikipedia — Chinese remainder theorem
5. Longest increasing subsequence and patience sorting: Wikipedia — Longest increasing subsequence