## The radical of $n$, $\operatorname{rad}(n)$, is the product of the distinct prime factors of $n$. For example, $504 = 2^3 \times 3^2 \times 7$, so $\operatorname{rad}(504) = 2 \times 3 \times 7 = 42$.

If we calculate $\operatorname{rad}(n)$ for $1 \le n \le 10$, then sort them on $\operatorname{rad}(n)$, and sorting on $n$ if the radical values are equal, we get:

Unsorted

Sorted

n

rad(n)

n

rad(n)

k

11

111

22

222

33

423

42

824

55

335

66

936

77

557

82

668

93

779

1010

101010

Let $E(k)$ be the $k$th element in the sorted $n$ column; for example, $E(4) = 8$ and $E(6) = 9$.

If $\operatorname{rad}(n)$ is sorted for $1 \le n \le 100000$, find $E(10000)$.

### The value of $E(k)$ is a number-theoretic problem that requires programming and cannot be solved with simple pen-and-paper calculations. We have to calculate $\operatorname{rad}(n)$ for $1 \le n \le 100000$ and after sorting, find the value of $E(10000)$.

Let’s use Python to solve this problem:

“`python

# Importing required libraries

from functools import reduce

# Function to find rad(n)

def rad(n):

factors = set()

i = 2

while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.add(i)
if n > 1:

factors.add(n)

return reduce(lambda a, b: a*b, factors, 1)

# Generating the list

nums = [(rad(n), n) for n in range(1, 100001)]

# Sorting this list on rad(n) and n

nums.sort()

# Printing E(10000)

nums[10000 – 1][1]

“`

Running this code will give you the answer to the question.

The algorithm is as follows:

1. For each integer from 1 to 100,000, find rad(n) and store the pair (rad(n), n).

2. Sort the resulting list of pairs first by rad(n), then by n (this happens automatically when sorting tuples).

3. The kth element in the sorted list is E(k), according to the problem description.

4. Hence, `nums[10000 – 1][1]` gives you the answer.

Remember: most programming languages (including Python) use zero-based indexing, which is why we subtract 1 from 10000. We’re also only interested in the second element of the tuple, hence the `[1]`.

##### More Answers:

Disc Game Prize FundEfficient Exponentiation

Prime Square Remainders