Solution

Answer: 475808650131120

Let

$$S_0=290797,\qquad S_{i+1}=S_i^2 \bmod 50515093$$

and define

$$P(n)={S_iS_j \mid 0\le i<j<n}.$$

There are

$$N=\binom n2$$

pairwise products. Since $N$ is odd for $n=1{,}000{,}003$, the median is the unique element with exactly $N//2$ products below it.

We are asked for

$$M(1{,}000{,}003).$$

1. Mathematical analysis

Step 1: Generate and sort the sequence

The pseudo-random generator produces positive integers less than $50515093$.

Let

$$A = \text{sorted}(S_0,S_1,\dots,S_{n-1}).$$

Sorting is crucial because it lets us count products efficiently.

Step 2: Convert the median problem into a counting problem

Define

$$f(x)=#{(i,j): i<j,\ A_iA_j\le x}.$$

Then $f(x)$ is monotone increasing.

If we can compute $f(x)$ quickly, then the median is the smallest $x$ such that

$$f(x)\ge \frac{N+1}{2}.$$

For

$$N=\binom{1{,}000{,}003}{2}=500002500003,$$

the target rank is

$$K=\frac{N+1}{2}=250001250002.$$

So we seek the smallest integer $x$ with

$$f(x)\ge K.$$

Step 3: Two-pointer counting

Because $A$ is sorted, we can count pairs in linear time.

Fix $i$. We want the largest $j>i$ satisfying

$$A_iA_j\le x.$$

As $i$ increases, this maximal $j$ never increases, so we use a decreasing pointer.

Algorithm:

Start $j=n-1$.
For each $i$:
While $A_iA_j>x$, decrement $j$.
Then all indices $i+1,\dots,j$ work.
Add $j-i$ to the count.

This computes $f(x)$ in $O(n)$.

Step 4: Binary search

Products range from

$$0 \le A_iA_j \le A_{n-1}A_{n-2}.$$

Since $f(x)$ is monotone, binary search finds the median in about 51 iterations because the search range is below $2^{52}$.

Total complexity:

Sorting: $O(n\log n)$
Each count: $O(n)$
Binary search: $O(n\log V)$

This is fast enough for $n=1{,}000{,}003$.

2. Python implementation

MOD = 50515093
N = 1_000_003

# ------------------------------------------------------------
# Generate the sequence
# ------------------------------------------------------------
S = [0] * N

x = 290797
for i in range(N):
    S[i] = x
    x = (x * x) % MOD

# ------------------------------------------------------------
# Sort values
# ------------------------------------------------------------
A = sorted(S)

# Number of pairwise products
total_pairs = N * (N - 1) // 2

# We want the lower/true median rank (1-based)
target = total_pairs // 2 + 1

# ------------------------------------------------------------
# Count how many pairs have product <= value
# ------------------------------------------------------------
def count_leq(value):
    count = 0
    j = N - 1

    for i, a in enumerate(A):

        while i < j and a * A[j] > value:
            j -= 1

        if j <= i:
            break

        count += (j - i)

    return count

# ------------------------------------------------------------
# Binary search for the median product
# ------------------------------------------------------------
lo = 0
hi = A[-1] * A[-2]

while lo < hi:
    mid = (lo + hi) // 2

    if count_leq(mid) >= target:
        hi = mid
    else:
        lo = mid + 1

print(lo)

3. Code walkthrough

Sequence generation

x = 290797
for i in range(N):
    S[i] = x
    x = (x * x) % MOD

This exactly follows the recurrence definition.

Sorting

A = sorted(S)

Sorted order enables monotone two-pointer counting.

Counting pairs

while i < j and a * A[j] > value:
    j -= 1

For each fixed $i$, move $j$ downward until the product constraint holds.

Then:

count += (j - i)

because every index between $i+1$ and $j$ works.

Overall runtime is linear because $j$ only decreases.

Binary search

if count_leq(mid) >= target:
    hi = mid
else:
    lo = mid + 1

This finds the smallest value whose rank is at least the median rank.

4. Verification on the given examples

For $n=3$, the algorithm returns:

$$3878983057768$$

matching the statement.

For $n=103$, it returns:

$$492700616748525$$

also matching the statement.

So the implementation is validated.

5. Final computation

Running the full computation for $n=1{,}000{,}003$ gives:

$$475808650131120$$

Answer: 475808650131120

Project Euler Problem 793