Numero altamente composto
# Numero altamente composto

Un numero altamente composto è un intero positivo che ha più divisori di qualsiasi intero positivo minore. I primi ventuno numeri altamente composti sono:

    1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560, 10080,

con rispettivamente 1, 2, 3, 4, 6, 8, 9, 10, 12, 16, 18, 20, 24, 30, 32, 36, 40, 48, 60, 64 e 72 divisori positivi. La sequenza dei numeri altamente composti è un sottoinsieme della sequenza dei più piccoli numeri k con esattamente n divisori.

I numeri altamente composti sono infiniti. Per dimostrare questo, supponiamo che n sia un qualsiasi numero altamente composto. Allora 2n avrà più divisori di n (avrà infatti tutti i divisori di n più perlomeno 2n) e quindi un numero maggiore di n, ma non superiore a 2n, deve essere a sua volta altamente composto.

Parlando in generale, un numero altamente composto è facile che abbia fattori primi i più piccoli possibili, ma non troppi uguali. Dato un numero n la cui scomposizione in fattori primi è.:

    $n=p_{1}^{c_{1}}p_{2}^{c_{2}}\cdot \dots \cdot p_{k}^{c_{k}}$

Dove $p_{1}<p_{2}<\dots <p_{k}$ sono primi, e gli esponenti $c_{i}$ sono interi positivi, allora il numero di divisori di n è:

    $(c_{1}+1)(c_{2}+1)\cdot \dots \cdot (c_{k}+1)$.

Quindi, perché n sia un numero altamente composto:

Inoltre, ad eccezione dei casi n = 4 e n = 36, l'ultimo esponente $c_k$ deve essere uguale ad 1.

Dire che la sequenza degli esponenti è non crescente è equivalente a dire che un numero altamente composto è un prodotto di primoriali.

I numeri altamente composti maggiori di 6 sono anche numeri abbondanti. Per accertarsene basta guardare ai tre o quattro divisori più alti di un particolare numero altamente composto. Tutti i numeri altamente composti sono anche numeri di Harshad.

Se Q(x) è il numero di numeri altamente composti minori o uguali ad x, allora esistono due costanti a e b, entrambe maggiori di 1, tali che:

    $(\ln x)^{a}\leq Q(x)\leq (\ln x)^{b}$

La prima parte della disuguaglianza fu provata da Paul Erdős nel 1944 e la seconda da J.-L. Nicholas nel 1988.

## Informatica

Questo problema per quando possa sembrare banale rappresenta una sfida piuttosto ostica per i computer, provando a ricavare anche solo poche decine di numeri altamente composti si incappa in un'esecuzione del programma che può richiedere diversi minuti.

