Project Euler Problem 866

Solution

Answer: 492401720

Let $E_N$ be the expected value of the product for a caterpillar of length $N$.

We are told:

The pieces $1,\dots,N$ are placed in a uniformly random order.
Whenever a piece is placed, it creates (or merges into) a segment of length $k$.
We multiply the $k$-th hexagonal number

$$H_k = k(2k-1)$$

for every placement.

We want $E_{100} \bmod 987654319$.

1. Mathematical analysis

Step 1: Reframe the process recursively

A key trick is to look at the last piece placed, not the first.

Suppose we are building a caterpillar of length $N$.

Let the last piece placed be at position $r$, where $1 \le r \le N$.

At the moment the last piece is placed:

all pieces to the left $(1,\dots,r-1)$ have already formed a completed segment,
all pieces to the right $(r+1,\dots,N)$ have already formed another completed segment,
inserting piece $r$ merges everything into one segment of length $N$.

So the final placement always contributes:

$$H_N = N(2N-1)$$

Meanwhile, the left and right sides evolve independently.

Thus:

$$E_N = H_N \cdot \frac1N \sum_{r=1}^{N} E_{r-1}E_{N-r}$$

because the final position $r$ is uniformly distributed.

Step 2: Simplify the recurrence

Substitute $H_N = N(2N-1)$:

$$E_N = N(2N-1)\cdot \frac1N \sum_{r=1}^{N} E_{r-1}E_{N-r}$$

The factor $N$ cancels:

$$E_N = (2N-1) \sum_{r=1}^{N} E_{r-1}E_{N-r}$$

Reindex with $k=r-1$:

$$\boxed{ E_N = (2N-1) \sum_{k=0}^{N-1} E_kE_{N-1-k} }$$

with base case

$$E_0=1.$$

This is a Catalan-style convolution recurrence.

Step 3: Verify the example $N=4$

Compute recursively:

$$E_0=1$$

$$E_1=(1)(1)=1$$

$$E_2=3(E_0E_1+E_1E_0)=3(2)=6$$

$$E_3=5(E_0E_2+E_1E_1+E_2E_0)$$

$$=5(6+1+6)=65$$

$$E_4=7(E_0E_3+E_1E_2+E_2E_1+E_3E_0)$$

$$=7(65+6+6+65)$$

$$=7\cdot142$$

$$=994$$

which matches the problem statement.

So the recurrence is correct.

2. Python implementation

MOD = 987654319
N = 100

# E[n] = expected product for caterpillar length n
E = [0] * (N + 1)
E[0] = 1

for n in range(1, N + 1):
    conv = 0

    # Catalan-style convolution
    for k in range(n):
        conv = (conv + E[k] * E[n - 1 - k]) % MOD

    E[n] = ((2 * n - 1) * conv) % MOD

print(E[100])

3. Code walkthrough

Initialization

E = [0] * (N + 1)
E[0] = 1

We define:

$$E_0=1$$

because an empty segment contributes multiplicative identity $1$.

Main recurrence

For each $n$:

for k in range(n):
    conv += E[k] * E[n - 1 - k]

This computes

$$\sum_{k=0}^{n-1} E_kE_{n-1-k}.$$

Then:

E[n] = ((2 * n - 1) * conv) % MOD

implements

$$E_n = (2n-1) \sum_{k=0}^{n-1} E_kE_{n-1-k}.$$

Everything is reduced modulo $987654319$.

Small-case verification

For $N=4$, the program produces:

$$E_4 = 994$$

matching the example exactly.

4. Final verification

The recurrence reproduces the sample $994$.
Every step stays integral because the $N$ in the hexagonal number cancels the $1/N$ averaging factor.
Complexity is only $O(N^2)$, trivial for $N=100$.

Evaluating the recurrence modulo $987654319$ gives:

Answer: 492401720