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^[1],

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^[2]. La sequenza dei numeri altamente composti è un sottoinsieme della sequenza dei più piccoli numeri k con esattamente n divisori^[3].

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:

i k numeri primi $p_{i}$ devono essere precisamente i primi k numeri primi (2, 3, 5, ...); altrimenti, possiamo sostituire uno dei primi dati con uno minore, e ottenere così un numero minore di n con lo stesso numero di fattori (ad esempio, 10 = 2 × 5. Il 5 potrebbe essere sostituito con il 3: 6 = 2 × 3, ed entrambi avrebbero 4 divisori);

la sequenza degli esponenti non deve essere crescente, vale a dire $c_{1}\geq c_{2}\geq \dots \geq c_{k}$ ; altrimenti, scambiando due esponenti non in ordine si può ottenere un numero minore di n con lo stesso numero di divisori (ad esempio 18 = 2¹×3² può essere trasformato in 12 = 2²×3¹, entrambi con 6 divisori).

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

Per quanto questo problema possa sembrare banale, esso 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.

Python

N=int(input("quanti numeri altamente altamentecomposti vuoi visualizzare "))
print(N)
cont=0
prec=0
x=1
while cont<N:
    cur=0
    for i in range(1,x,1):
        if x%i==0:
            cur=cur+1
    if cur > prec: 
        prec=cur
        cont = cont +1
        print(cont,"°",x)
    x=x+1