Statement

The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 2³ x 3² x 7, so rad(504) = 2 x 3 x 7 = 42.

If we calculate rad(n) for 1 $\leq$ n $\leq$ 10, then sort them on rad(n), and sorting on n if the radical values are equal.

Let E(k) be the kth element in the sorted n column.

If rad(n) is sorted for 1 $\leq$ n $\leq$ 100000, find E(10000).

Solution

First get the primes below 100000, after that initialize the list of rads, for each position I store the rad and the n.

To fill in the rad list for each prime multiply the rad for all the positions of numbers that are divisible for that prime, which is pretty easy, start at the prime and make steps of size prime until the limit is reached.

After going through all the primes we have the rad list filled. We sort it and extract the position 10000 and the n is stored in the second position of the element.

from CommonFunctions import find_primes_less_than
 
LIMIT = 100000
 
if __name__ == '__main__':
    primes = find_primes_less_than(LIMIT)
 
    rads = [[1, i] for i in range(LIMIT+1)]
    for p in primes:
        for i in range(p, LIMIT+1, p):
            rads[i][0] *= p
    print("The result is:", sorted(rads)[10000][1])

The Python file is available for download here.