Problem Description

The radical of n, rad(n), is the product of 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 problem can be solved without sorting or a large list of primes by just calculating factors as we concatenate them to a group organized by rad(n). To find n, just concatenate the group together and print the index relative to zero in the array.

Solution

Runs < 1 second in Perl.

$limit = 100000;
$target=10000;
 
$rad[$_] = 1 for (2..$limit);
$buffer[1] = 1;
for ($n = 2; $n <= $limit; $n++){
  if ($rad[$n] == 1){
    for ($j = $n; $j <= $limit; $j += $n){
      $rad[$j] *= $n; }}
  $buffer[$rad[$n]].="$n "; }
 
$e = (map {split /s+/} @buffer)[$target-1];
 
print "Answer to PE124 = $e";

Comments