Project Euler Problem 375

Solution

Answer: 7435327983715286168

Let the sequence be

$S_{n+1}=S_n^2\bmod 50515093$

and define

$M(N)=\sum_{1\le i\le j\le N} \min(S_i,\dots,S_j)$

The key observation is that the sequence is eventually periodic immediately from $S_1$, with period

$$L = 6,308,948.$$

We compute the sum of subarray minimums using the standard monotonic-stack technique:

$P_i$: distance to the previous strictly smaller element,
$R_i$: distance to the next smaller-or-equal element.

Then each value contributes

$$S_i \times P_i \times R_i$$

to the total number of subarrays for which it is the minimum.

Because the sequence is periodic and $N=2\times 10^9$ is enormous, we aggregate contributions analytically across repetitions of the cycle instead of iterating over all $N$ terms.

The following Python program computes the exact value:

MOD = 50515093
L = 6308948

# Generate one full cycle: S1..SL
s = 290797
a = [0] * L
for i in range(L):
    s = (s * s) % MOD
    a[i] = s

# Duplicate array for circular processing
b = a + a

# P[i] = distance to previous strictly smaller element
# If none exists, store -1 (only happens for the global minimum)
P = [0] * L
stack = []

for idx, x in enumerate(b):
    while stack and b[stack[-1]] >= x:
        stack.pop()

    if idx >= L:
        P[idx - L] = idx - stack[-1] if stack else -1

    stack.append(idx)

# R[i] = distance to next smaller-or-equal element
R = [0] * L
stack = []

for idx in range(2 * L - 1, -1, -1):
    x = b[idx]

    while stack and b[stack[-1]] > x:
        stack.pop()

    if idx < L:
        R[idx] = stack[-1] - idx if stack else L

    stack.append(idx)

def compute_M(N):
    q, r = divmod(N, L)
    total = 0

    for i, x in enumerate(a):
        count = q + (i < r)

        if count == 0:
            continue

        p = P[i]
        rr = R[i]

        # Global minimum case (no previous smaller element)
        if p == -1:
            if count >= 2:
                m = count - 1
                total += x * rr * (
                    m * (i + 1)
                    + L * (m - 1) * m // 2
                )

            t = i + (count - 1) * L
            total += x * (t + 1) * (N - t)

        # Only one occurrence inside prefix
        elif count == 1:
            total += (
                x
                * min(p, i + 1)
                * min(rr, N - i)
            )

        # Multiple occurrences
        else:
            total += x * min(p, i + 1) * rr
            total += x * p * min(rr, N - (i + (count - 1) * L))
            total += x * (count - 2) * p * rr

    return total

print(compute_M(10))        # 432256955
print(compute_M(10000))     # 3264567774119
print(compute_M(2000000000))

The program reproduces the two values given in the problem statement:

$M(10)=432256955$
$M(10000)=3264567774119$

and finally computes:

Answer: 7435327983715286168