Énoncé:
Le radical de $n$, $rad(n)$, est le produit des facteurs premiers distincts de $n$. Par exemple, $504 = 2^3 × 3^2 × 7$, donc $rad(504) = 2 × 3 × 7 = 42$.
Si on calcule $rad(n)$ pour $1 \le n \le 10$, puis qu'on les trie sur $rad(n)$, et en triant sur $n$ si les valeurs des radicaux sont égales, on obtient :
Non trié | Trié | |||
---|---|---|---|---|
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 |
Soit $E(k)$ le $k$ième élément de la colonne $n$ triée; par exemple, $E(4) = 8$ et $E(6) = 9$.
Si $rad(n)$ est trié pour $1 \le n \le 100000$, trouver $E(10000)$.
Lien du problème originel