// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 124 Solution

Project Euler 124 Solution

Project Euler 124: Find the kth element in a sorted list of radicals


Problem Description

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

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

pe124

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).

Analysis

This solution uses sieving to determine primes and apply them as factors to calculate the integer radical of n.
An array is set up as a simple structure to track the radicals and later sort them to find out kth element.

The first column represents the rad(n) and is initially set to 1. The second column is n and the number we factor into discrete primes that get multiplied into the first column. That is why the first column is set to 1.

Ignore the first element of our array, [1,0], it’s there to base our array from 1 instead of 0.

[[1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 10]]

After we sieve our primes and produce a radical for each n the array will look as follows:

[[1, 0], [1, 1], [2, 2], [3, 3], [2, 4], [5, 5], [6, 6], [7, 7], [2, 8], [3, 9], [10, 10]]

Lastly, we sort our array by the first column and, in the case of ‘ties,’ by the second column. Python does this inherently. Ignoring the first cell, count 6 cells from left to right and you get the example’s answer of [3,9].

[[1, 0], [1, 1], [2, 2], [2, 4], [2, 8], [3, 3], [3, 9], [5, 5], [6, 6], [7, 7], [10, 10]]

Python will sort the 2D array by the first index and then by the second.

Project Euler 124 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 124 Solution Python 2.7 source.

Afterthoughts

    No afterthoughts yet.
Project Euler 124 Solution last updated

Discussion

No comments yet.

Post a comment