# Euler Solution 124

### From ProgSoc Wiki

# Euler Problem 124

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

If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n), and sorting on n if the radical values are equal, we get (n, rad(n)):

(1,1), (2,2), (4,2), (8,2), (3,3), (9,3), (5,5), (7,7), (10,10)

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

If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).

# Solutions to Problem 124

## Python by Althalus

Runtime: 4.8 seconds

from primeFunctions import genPrimes, getFactors ps = genPrimes(100000) def rad(n): d = {} fs = getFactors(n,ps) for x in fs: d[x] = x fs = d.values() return reduce(lambda x,y: x*y, fs) list = [(1,1),] for x in range(2,100001): list.append((rad(x),x)) list.sort() print list[10000-1]

For reference, by genPrimes and getFactors functions are like so:

def genPrimes(n): #1 is not prime. if n < 2: return None #2 is the first prime. if n == 2: return [2] # Sieve of eratosthenes (sp?) # get a list of odd numbers (evens aren't prime cept for 2) (don't include 1 - it's not prime) candidates = range(3,n,2) for i in xrange(int(n**0.5)): p = candidates[i] if p > 0: j=i+p while j < len(candidates): candidates[j] = 0 j+=p return [2]+[x for x in candidates if x > 0]

def getFactors(n,primesList): i = 0 factors=[] while n != 1: while n%primesList[i] == 0: factors.append(primesList[i]) n=n/primesList[i] i+=1 return factors