Solution

Answer: 9936352

Let

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

After removing duplicates, these are the “stations”.

We want the longest path from $(0,0)$ to $(n,n)$ whose coordinates never decrease.

Equivalently, among all station points, we want the largest subset that can be ordered so that both coordinates are nondecreasing.

Key Mathematical Insight

Suppose we sort all distinct stations by increasing $x$-coordinate (and then by $y$-coordinate).

Then a valid uphill path corresponds exactly to a subsequence whose $y$-coordinates are nondecreasing.

Therefore:

$$S(n)=\text{length of the Longest Nondecreasing Subsequence (LNDS)}$$

of the $y$-values after sorting the stations by $x$.

So the problem becomes:

Generate all distinct points

$$(2^i \bmod n,; 3^i \bmod n).$$ 2. Sort them lexicographically. 3. Compute the LNDS of the $y$-coordinates.

The standard patience-sorting LIS algorithm computes this in $O(m\log m)$, where $m$ is the number of distinct stations.

Because equal $y$-values are allowed (nondecreasing, not strictly increasing), we must use upper_bound, not lower_bound.

Python Implementation

from bisect import bisect_right

def S(n):
    # Generate all distinct stations
    seen = set()
    points = []

    x = 1 % n
    y = 1 % n

    while (x, y) not in seen:
        seen.add((x, y))
        points.append((x, y))

        x = (2 * x) % n
        y = (3 * y) % n

    # Sort by x, then y
    points.sort()

    # Longest nondecreasing subsequence on y
    lis = []

    for _, yy in points:
        pos = bisect_right(lis, yy)

        if pos == len(lis):
            lis.append(yy)
        else:
            lis[pos] = yy

    return len(lis)

total = 0

for k in range(1, 31):
    total += S(k ** 5)

print(total)

Code Walkthrough

Generating the stations

x = 1 % n
y = 1 % n

These correspond to $i=0$:

$$(2^0 \bmod n,;3^0 \bmod n)=(1,1).$$

Each iteration multiplies by 2 and 3 modulo $n$:

x = (2 * x) % n
y = (3 * y) % n

We stop once a pair repeats, since the sequence is periodic.

Sorting the points

points.sort()

This sorts lexicographically by $x$, then $y$.

Any uphill path must respect this order.

Longest Nondecreasing Subsequence

We now only need the longest nondecreasing sequence of $y$-values.

The patience-sorting technique maintains:

lis[i]

= the smallest possible tail of a nondecreasing subsequence of length $i+1$.

We use:

bisect_right

because equal $y$-values are allowed.

Verification on the Given Examples

The program gives:

$$S(22)=5$$

matching the statement.

It also gives:

$$S(123)=14, \qquad S(10000)=48,$$

again matching the problem statement.

Final Computation

Evaluating

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

gives:

$$9936352$$

Answer: 9936352

Project Euler Problem 411