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 = 2³ × 3² × 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:

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

Afterthoughts

No afterthoughts yet.