Задача 124
Упорядоченные радикалы

Радикалом числа n, rad(n), является произведение уникальных простых множителей числа n. К примеру, 504 = 2^(3) × 3^(2) × 7, таким образом, rad(504) = 2 × 3 × 7 = 42.

Если подсчитать rad(n) для 1n ≤ 10 и упорядочить их по rad(n), а затем по n для одинаковых значений радикалов, получим

Неупорядоченная функция
 
Упорядоченная функция

n

rad(n)


n

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

Пусть E(k) – k-ый элемент в упорядоченной колонне n; к примеру, E(4) = 8, а E(6) = 9.

Найдите E(10000), если функция rad(n) упорядочена для 1 ≤ n ≤ 100000.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net