Project Euler Problem 124


The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23 x 32 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).


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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License