124 : 順序付き根基

$n$の"根基"(radical)を$\textrm{rad}(n)$で書き、$n$の異なる素因数の積とする。例えば$504 = 2^3 × 3^2 × 7$なので$\textrm{rad}(504) = 2 × 3 × 7 = 42$である。

$1 ≤ n ≤ 10$に対して$\textrm{rad}(n)$を計算し,$\textrm{rad}(n)$を対象にソートし,$\textrm{rad}(n)$が同じ場合は$n$を対象にソートすると以下のようになる.

未ソート			ソート済み
$n$	$\textrm{rad}(n)$	$n$	$\textrm{rad}(n)$	$k$
1	1	1	1	1
2	2	2	2	2
3	3	4	2	3
4	2	8	2	4
5	5	3	3	5
6	6	9	3	6
7	7	5	5	7
8	2	6	6	8
9	3	7	7	9
10	10	10	10	10

ソートした表の$n$の列の$k$番目の要素を$E(k)$とする. 例えば$E(4) = 8, E(6) = 9$である.

$\textrm{rad}(n)$を$1 ≤ n ≤ 100000$でソートした場合,$E(10000)$を求めよ.