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 è.:

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

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

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

Quindi, perché n sia un numero altamente composto:

• i k numeri primi ${\displaystyle 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 ${\displaystyle 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:

${\displaystyle (\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 

Note

1. ^ (EN) Sequenza A002182, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
2. ^ (EN) Sequenza A002183, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
3. ^ (EN) Sequenza A005179, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.

Voci correlate

• Numero composto
• Tavola dei divisori
• Numero altamente cototiente

Collegamenti esterni

• (EN) Eric W. Weisstein, Highly Composite Number, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica