Project Euler Problem 733

Solution

Answer: 574368578

Let

$$a_i = 153^i \bmod 10000019.$$

We must sum the values of all increasing subsequences of length $4$ among the first $10^6$ terms.

A standard dynamic-programming approach works:

Let $C_k(x)$ = number of increasing subsequences of length $k$ ending at value $x$.
Let $S_k(x)$ = total contribution sum of those subsequences.

Using Fenwick trees (BITs) over the value domain $1 \dots 10000018$, we can process each term in

$$O(\log 10000019)$$

time.

For each new value $v$:

$$\begin{aligned} c_1 &= 1, & s_1 &= v,\ c_k &= \sum_{u<v} c_{k-1}(u),\ s_k &= \sum_{u<v} s_{k-1}(u) + v \cdot c_k. \end{aligned}$$

Accumulating all $s_4$ gives $S(n)$.

The implementation was verified against the problem’s checks:

Running the optimized computation for $n=10^6$ gives:

$$S(10^6)\bmod 1,000,000,007 = 574368578.$$

Answer: 574368578