Detailed mathematical approach

Problem Summary

For each positive integer \(n\), define

$\operatorname{rad}(n)=\prod_{p\mid n} p,$

the product of the distinct prime divisors of \(n\), with \(\operatorname{rad}(1)=1\). The problem orders all integers \(1 \le n \le 100{,}000\) by the pair \((\operatorname{rad}(n),n)\): smaller radical first, and if two numbers have the same radical, the smaller integer comes first. If \(E(k)\) denotes the \(k\)-th term of that ordered list, the goal is to determine \(E(10000)\).

The only real computational issue is that the order depends on all \(100{,}000\) radical values. The implementations avoid factoring each number separately. Instead, they compute every radical in one sieve-like pass and then perform a single sort using the exact order required by the statement.

Mathematical Approach

The structure of the problem is simple but very specific: compute \(\operatorname{rad}(n)\) for every \(n\), sort the resulting pairs, and read one position. The mathematical content lies in finding the right way to build the whole radical table efficiently.

The ordering that defines \(E(k)\)

Write

$a \prec b \quad\Longleftrightarrow\quad \bigl(\operatorname{rad}(a),a\bigr) \lt \bigl(\operatorname{rad}(b),b\bigr)$

in lexicographic order. Then \(E(1),E(2),\dots,E(100000)\) is just the list of integers \(1,2,\dots,100000\) sorted by \(\prec\). This formulation matters because ties are not arbitrary: if \(\operatorname{rad}(a)=\operatorname{rad}(b)\), then the smaller of \(a\) and \(b\) must appear first.

Radicals discard exponents

If

$n=\prod_{i=1}^{r} p_i^{e_i},$

then

$\operatorname{rad}(n)=\prod_{i=1}^{r} p_i.$

So the radical remembers which primes divide \(n\), but forgets how many times they occur. For example, \(2\), \(4\), \(8\), and \(16\) all have radical \(2\); likewise \(3\) and \(9\) both have radical \(3\). This is why powers of small primes move forward in the ordered list even when the numbers themselves are larger. It also gives the standard inequality

$\operatorname{rad}(n)\le n,$

with equality exactly when \(n\) is squarefree.

A sieve that multiplies each prime exactly once

The key observation is that the radical of \(m\) is obtained by multiplying together the distinct primes dividing \(m\). Therefore one may initialize an array \(R\) by \(R[n]=1\) for all \(n\), and then for each prime \(p \le N\) multiply \(p\) into every multiple of \(p\):

$R[m]\leftarrow R[m]\cdot p \qquad \text{for } m=p,2p,3p,\dots.$

Because the loop advances in steps of \(p\), each multiple receives the factor \(p\) exactly once, no matter whether \(p\) divides it once or many times. After all primes have been processed, every distinct prime divisor of \(m\) has contributed one factor, so

$R[m]=\prod_{p\mid m} p=\operatorname{rad}(m).$

The primality test used by the implementations is also sieve-based: a boolean array marks composites as soon as they appear as nontrivial multiples of a smaller prime. When the outer loop reaches an unmarked value, that value is prime and should be propagated through its multiples.

Why the sieve is correct

An easy invariant proves correctness. After finishing all primes up to some threshold \(q\), the current value \(R[n]\) equals the product of those prime divisors of \(n\) that are at most \(q\). Initially this is true with an empty product. When the next prime \(p\) is processed, exactly the multiples of \(p\) are updated, so each such number gains the missing factor \(p\), and all other numbers remain correct. By induction, after the final prime the full radical has been built for every \(n\).

Worked example: the range \(1\) through \(10\)

For the first ten integers, the radicals are

$\operatorname{rad}(1)=1,\ \operatorname{rad}(2)=2,\ \operatorname{rad}(3)=3,\ \operatorname{rad}(4)=2,\ \operatorname{rad}(5)=5,$

$\operatorname{rad}(6)=6,\ \operatorname{rad}(7)=7,\ \operatorname{rad}(8)=2,\ \operatorname{rad}(9)=3,\ \operatorname{rad}(10)=10.$

Sorting the pairs \((\operatorname{rad}(n),n)\) gives

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

Hence

$E(4)=8.$

This example shows both parts of the ordering: \(4\) and \(8\) move ahead because their radical is only \(2\), and ties among equal radicals are broken by the ordinary size of the integers.

From the sorted list to the requested term

Once all radicals are known, the rest of the problem is purely an ordering step. Build the sortable collection, order it lexicographically by \((\operatorname{rad}(n),n)\), and take the \(10000\)-th entry. There is no hidden recurrence or deeper search after the sieve; the whole solution is exactly this radical table plus one sort.

How the Code Works

The C++, Python, and Java implementations all follow the same three-stage algorithm.

Building the radical table

An array of length \(N+1\) is initialized with \(1\). A second boolean array is used to recognize primes during the sweep from \(2\) to \(N\). Whenever the current value is still unmarked, it is prime, so the implementation multiplies that prime into every multiple and marks the nontrivial multiples as composite for later iterations.

Sorting by the exact problem key

After the sieve, the implementation creates a collection representing all integers \(1\) through \(100{,}000\) together with their radicals, or equivalently sorts the integers directly by the key \((\operatorname{rad}(n),n)\). The secondary key is essential; without it, equal-radical groups would not match the required definition of \(E(k)\).

Reading the target position

The final answer is the element in position \(10000\) under 1-based counting, which is array index \(9999\) under 0-based storage. One of the implementations also checks the miniature example above to confirm that the ordering rule produces \(E(4)=8\) when the limit is \(10\).

Complexity Analysis

Let \(N=100{,}000\). The sieve phase visits each multiple of each prime once, so its running time is

$\sum_{p\le N}\left\lfloor \frac{N}{p}\right\rfloor = O\!\left(N\sum_{p\le N}\frac{1}{p}\right)=O(N\log\log N).$

Sorting \(N\) items by \((\operatorname{rad}(n),n)\) costs \(O(N\log N)\), which is the dominant term here. The memory usage is \(O(N)\): one array for radical values, one boolean array for the sieve state, and one sortable collection containing the integers or the corresponding pairs.

Footnotes and References

1. Project Euler Problem 124: https://projecteuler.net/problem=124
2. Radical of an integer: Wikipedia - Radical of an integer
3. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes
4. Square-free integer: Wikipedia - Square-free integer
5. Lexicographic order: Wikipedia - Lexicographic order