Ordered Radicals

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: