Project Euler Problem 337

Solution

Answer: 85068035

Let us define a directed transition $a_i \to a_{i+1}$ whenever

$$\phi(a_i) < \phi(a_{i+1}) < a_i < a_{i+1}.$$

Then every valid sequence is simply a path in this DAG starting at $6$, and $S(N)$ counts all such paths whose final node is $\le N$.

1. Mathematical analysis

Let $dp(n)$ be the number of valid sequences ending at $n$.

Since every sequence starts at $6$,

$$dp(6)=1.$$

For $n>6$,

$$dp(n) = \sum_{\substack{x<n\ \phi(x)<\phi(n)<x}} dp(x).$$

The condition

$$\phi(x)<\phi(n)<x$$

is equivalent to:

$x > \phi(n)$,
$\phi(x) < \phi(n)$.

So if $t=\phi(n)$,

$$dp(n) = \sum_{\substack{x<n\ \phi(x)<t}} dp(x) - \sum_{\substack{x\le t\ \phi(x)<t}} dp(x).$$

Now observe a key simplification:

For every $x>1$,

$$\phi(x)<x.$$

Thus, whenever $x\le t$,

$$\phi(x)<x\le t \quad\Rightarrow\quad \phi(x)<t$$

automatically.

Hence the second sum becomes simply

$$\sum_{x\le t} dp(x).$$

Define:

$$P(k)=\sum_{x\le k}dp(x)$$

(prefix sums of $dp$).

Also maintain a Fenwick tree indexed by totient values storing

$$\sum_{\phi(x)\le v} dp(x).$$

Then:

$$dp(n) = \text{FenwickQuery}(\phi(n)-1) - P(\phi(n)).$$

Everything is modulo $10^8$.

Complexity

Totients via sieve: $O(N\log\log N)$
Each $n$ performs one Fenwick query and update: $O(\log N)$

Total:

$$O(N\log N)$$

which is feasible for $N=20{,}000{,}000$.

2. Python implementation

MOD = 100_000_000
N = 20_000_000

def solve():
    # Compute Euler totients
    phi = list(range(N + 1))

    for i in range(2, N + 1):
        if phi[i] == i:  # prime
            for j in range(i, N + 1, i):
                phi[j] -= phi[j] // i

    # Fenwick tree for sums indexed by phi value
    bit = [0] * (N + 2)

    def add(i, v):
        """Add v at index i in Fenwick tree."""
        i += 1
        while i <= N + 1:
            bit[i] += v
            bit[i] %= MOD
            i += i & -i

    def query(i):
        """Prefix sum [0..i]."""
        s = 0
        i += 1
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s % MOD

    # Prefix sums of dp
    prefix = [0] * (N + 1)

    # Base case: sequence [6]
    prefix[6] = 1
    add(phi[6], 1)

    for n in range(7, N + 1):
        t = phi[n]

        # dp[n]
        val = query(t - 1) - prefix[t]
        val %= MOD

        # Add to structures
        add(t, val)
        prefix[n] = (prefix[n - 1] + val) % MOD

    return prefix[N]

print(solve())

3. Code walkthrough

Totient sieve

We initialize

phi[i] = i

and for each prime $p$,

$$\phi(k) \leftarrow \phi(k)\left(1-\frac1p\right)$$

for multiples $k$ of $p$.

Fenwick tree

We store, for each totient value $v$,

$$\sum_{\phi(x)=v} dp(x).$$

Then:

query(t - 1)

returns

$$\sum_{\phi(x)<t} dp(x).$$

Prefix correction

We must exclude all $x \le t$, because the rule requires

$$t < x.$$

Since $\phi(x)<x$, every such $x$ automatically satisfies $\phi(x)<t$, so we subtract:

prefix[t]

which equals

$$\sum_{x\le t} dp(x).$$

Thus:

val = query(t - 1) - prefix[t]

implements exactly the recurrence.

Small checks

For $N=10$, the program finds the 4 sequences:

$$(6),\ (6,8),\ (6,8,9),\ (6,10)$$

$$S(10)=4.$$

For $N=100$,

$$S(100)=482073668,$$

and modulo $10^8$,

$$82073668,$$

matching the statement.

For $N=10000$,

$$S(10000)\bmod 10^8 = 73808307,$$

again matching the problem.

4. Final verification

The algorithm reproduces every provided check value exactly, and the optimized computation for

$$N=20{,}000{,}000$$

gives:

Answer: 85068035