Nombre hautement totient

Un nombre hautement totient (hightly totient en anglais), ou hautement indicateur n est un entier positif qui possède plus de solutions pour l'équation φ(x) = n, où φ est l'indicatrice d'Euler (ou fonction totient), que n'importe quel entier positif inférieur à lui. Les douze premiers nombres hautement totients sont 1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432 et 480 (suite A097942 de l'OEIS), avec comme solutions respectives 1, 3, 4, 5, 6, 10, 11, 17, 21, 31, 34 et 37.

Le concept est quelque peu analogue à celui de nombre hautement composé et, de même que 1 est le seul nombre hautement composé impair, il est le seul nombre hautement totient impair (et même le seul nombre impair à ne pas être un nontotient). De même qu'il existe une infinité de nombres hautement composés, il existe aussi une infinité de nombre hautement totients, bien que les nombres hautement totients deviennent de plus en plus difficiles à trouver à mesure qu'il grandissent, puisque le calcul de φ(x) implique la décomposition en produit de facteurs premiers qui est un problème NP-complet.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Highly totient number » (voir la liste des auteurs).

Voir aussi

• Nombre nontotient
• Nombre noncototient