Problem 124: Ordered Radicals

Mathematical Development

Definition 1. For a positive integer $n$ with prime factorization $n = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}$, the radical is $\operatorname{rad}(n) = p_1 p_2 \cdots p_m$. Equivalently, $\operatorname{rad}(n) = \prod_{p \mid n} p$.

Theorem 1 (Radical and squarefreeness). $\operatorname{rad}(n) = n$ if and only if $n$ is squarefree. For any prime power $p^k$ with $k \ge 1$, $\operatorname{rad}(p^k) = p$.

Proof. If $n = p_1 p_2 \cdots p_m$ is squarefree, then $\operatorname{rad}(n) = p_1 \cdots p_m = n$. Conversely, if some prime $p$ divides $n$ with exponent $e \ge 2$, then $n \ge p^2 \cdot \prod_{q \mid n, q \ne p} q > p \cdot \prod_{q \mid n, q \ne p} q = \operatorname{rad}(n)$. For $p^k$: the unique prime divisor is $p$, so $\operatorname{rad}(p^k) = p$. $\square$

Theorem 2 (Sieve computation of radicals). Initialize $\operatorname{rad}[n] = 1$ for all $1 \le n \le N$. For each prime $p \le N$ (identified during the sieve), multiply $\operatorname{rad}[m]$ by $p$ for every multiple $m$ of $p$ in $\{p, 2p, \ldots, N\}$. Upon completion, $\operatorname{rad}[n] = \prod_{p \mid n} p$ for all $n$.

Proof. Each prime $p$ dividing $n$ contributes exactly one factor of $p$ to $\operatorname{rad}[n]$, since $p$ is multiplied in when processing multiples of $p$, and this happens exactly once per prime (the sieve only processes primes, not composite numbers). No prime $q \nmid n$ contributes to $\operatorname{rad}[n]$, since $n$ is not a multiple of $q$. Primes are identified as those $p$ satisfying $\operatorname{rad}[p] = 1$ when $p$ is first reached (i.e., $p$ has no prime factor smaller than itself). $\square$

Lemma 1 (Total order). The lexicographic order on pairs $(\operatorname{rad}(n), n)$ is a total order on $\{1, \ldots, N\}$: for distinct $n_1 \ne n_2$, either $\operatorname{rad}(n_1) \ne \operatorname{rad}(n_2)$ (ordered by radical) or $\operatorname{rad}(n_1) = \operatorname{rad}(n_2)$ and the tiebreaker $n_1 \ne n_2$ is decisive.

Proof. Immediate from the definition of lexicographic order and the uniqueness of $n$. $\square$

Editorial

The expensive part is not the final selection but computing all radicals efficiently. A sieve handles that cleanly: each time a prime $p$ is discovered, multiply $p$ into the radical of every multiple of $p$. Because each prime contributes only once to each number, the resulting array is exactly $\operatorname{rad}(n)$ for every $1 \le n \le 100000$.

After that, the rest is a pure ordering problem. Form the pairs $(\operatorname{rad}(n), n)$, sort them lexicographically, and read off the entry in position 10000. The secondary key $n$ automatically resolves ties between equal radicals.

Pseudocode

Initialize every radical value to 1.

Sweep through the integers from 2 up to 100000.
Whenever the current integer is still marked with radical 1, treat it as prime and multiply it into the radical of each of its multiples.

Build the list of pairs (rad(n), n) for all n in the range.
Sort that list in lexicographic order and return the n-value in position 10000.

Complexity Analysis

• Time: $O(N \log \log N)$ for the sieve (each prime $p$ visits $\lfloor N/p \rfloor$ multiples; summing over primes $p \le N$ gives $\sum_{p \le N} N/p = O(N \log \log N)$ by Mertens’ theorem). Sorting requires $O(N \log N)$. Total: $O(N \log N)$.
• Space: $O(N)$ for the radical array and sorted pairs.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int N = 100000;
    const int K = 10000;

    vector<int> rad(N + 1, 1);
    for (int i = 2; i <= N; i++) {
        if (rad[i] == 1) {  // i is prime
            for (int j = i; j <= N; j += i)
                rad[j] *= i;
        }
    }

    vector<pair<int, int>> v;
    v.reserve(N);
    for (int i = 1; i <= N; i++)
        v.push_back({rad[i], i});
    sort(v.begin(), v.end());

    cout << v[K - 1].second << endl;
    return 0;
}

"""
Problem 124: Ordered Radicals

Compute rad(n) for 1 <= n <= 100000 via sieve, sort by (rad(n), n),
return E(10000).
"""

def solve():
    N = 100000
    K = 10000

    rad = [1] * (N + 1)
    for i in range(2, N + 1):
        if rad[i] == 1:  # i is prime
            for j in range(i, N + 1, i):
                rad[j] *= i

    sorted_list = sorted(range(1, N + 1), key=lambda n: (rad[n], n))
    print(sorted_list[K - 1])

solve()