Solution

Answer: 21417

We need to compute $E(10000)$ when the integers $1 \le n \le 100000$ are sorted by:

Increasing $\operatorname{rad}(n)$,
Breaking ties by increasing $n$.

The radical is defined as the product of the distinct prime factors of $n$.

For example:

$504 = 2^3 \cdot 3^2 \cdot 7$,
so

$$\operatorname{rad}(504)=2\cdot3\cdot7=42.$$

Mathematical analysis

The direct definition suggests two tasks:

Compute $\operatorname{rad}(n)$ efficiently for all $n \le 100000$,
Sort pairs $(\operatorname{rad}(n), n)$.

A naïve factorization of every number individually would work, but we can do much better with a sieve-like approach.

Key observation

If $p$ is prime, then every multiple of $p$ has $p$ as a distinct prime factor.

So we can initialize:

$$\operatorname{rad}(n)=1$$

for all $n$, and then for every prime $p$:

multiply $\operatorname{rad}(k)$ by $p$ for every multiple $k$ of $p$.

This is analogous to the Sieve of Eratosthenes.

Example

Start with:

$$\operatorname{rad}(1)=\operatorname{rad}(2)=\cdots=1.$$

Process prime $2$:

multiply all multiples of 2 by 2.

Now:

$$\operatorname{rad}(2)=2,\quad \operatorname{rad}(4)=2,\quad \operatorname{rad}(6)=2,\dots$$

Process prime $3$:

multiply all multiples of 3 by 3.

Then:

$$\operatorname{rad}(6)=2\cdot3=6,$$

$$\operatorname{rad}(9)=3.$$

And so on.

The complexity is essentially:

$$O(n \log\log n),$$

which is extremely fast for $100000$.

Python implementation

LIMIT = 100000

# rad[n] will store rad(n)
rad = [1] * (LIMIT + 1)

# Sieve to compute radicals
for p in range(2, LIMIT + 1):
    # If rad[p] is still 1, then p is prime
    if rad[p] == 1:
        # Multiply p into every multiple of p
        for multiple in range(p, LIMIT + 1, p):
            rad[multiple] *= p

# Build list of (rad(n), n)
values = [(rad[n], n) for n in range(1, LIMIT + 1)]

# Sort by rad(n), then by n automatically
values.sort()

# E(10000) is the 10000th element (1-indexed)
answer = values[9999][1]

print(answer)

Code walkthrough

Step 1: Initialize radicals

rad = [1] * (LIMIT + 1)

We begin with every radical equal to 1 because we will multiply in distinct prime factors as we discover them.

Step 2: Detect primes

if rad[p] == 1:

Initially only primes retain value 1 when reached:

composite numbers have already had smaller prime factors multiplied into them,
primes have not.

Thus this acts as a primality test.

Step 3: Multiply prime into all multiples

for multiple in range(p, LIMIT + 1, p):
    rad[multiple] *= p

Each prime contributes exactly once to every multiple, which is precisely the definition of the radical.

Example:

when $p=2$, $12$ gets multiplied by 2,
when $p=3$, $12$ gets multiplied by 3,
no further multiplication occurs for repeated powers.

Hence:

$$\operatorname{rad}(12)=2\cdot3=6.$$

Step 4: Build sortable pairs

values = [(rad[n], n) for n in range(1, LIMIT + 1)]

Python tuple sorting is lexicographic, so:

values.sort()

sorts first by $\operatorname{rad}(n)$, then by $n$.

Exactly what the problem requires.

Step 5: Extract the 10000th element

Because Python uses 0-based indexing:

values[9999]

is the 10000th entry.

The second component is $n$.

Small-example verification

For $1 \le n \le 10$, the code produces:

$$(1,1), (2,2), (2,4), (2,8), (3,3), (3,9), (5,5), (6,6), (7,7), (10,10)$$

Thus:

$E(4)=8$,
$E(6)=9$,

matching the problem statement.

So the method is correct.

Final verification

The result should:

be between $1$ and $100000$,
correspond to a relatively small radical ordering,
and the sieve computation is exact and deterministic.

Running the algorithm gives:

$$E(10000)=21417.$$

Answer: 21417

Project Euler Problem 124