Visualizzazione post con etichetta divisori. Mostra tutti i post
Visualizzazione post con etichetta divisori. Mostra tutti i post

martedì 22 agosto 2017

I numeri intoccabili

Oggi vi voglio parlare di una particolare classe di numeri interi positivi: i numeri intoccabili. Anni fa mi occupai di questi numeri e in particolare di una loro sottoclasse: i numeri intoccabili unitari. A quel tempo nessuno conosceva la sequenza di tali numeri e dopo averli studiati fui in grado di stabilire quali degli interi tra 1 e 1000 appartenevano a tale sottoclasse. Tutto cio’ e’ stato documentato dal matematico Richard Guy nel suo famossisimo libro: Unsolved Problems in Number Theory, e dal matematico Hee-Sung Yang nella sua tesi discussa presso il Dartmouth College d’Inghilterra nel 2012.







Ma procediamo con ordine e vediamo di cosa stiamo parlando. Prima di tutto perche’ intoccabili? Semplicemente perche’ vengono evitati da tutti gli altri numeri che non vogliono avere nulla a che fare con loro nel senso che non li vogliono fra i loro divisori. Ma cosa sono i divisori? In matematica un divisore di un intero N, anche chiamato un suo fattore, e’ un intero M che moltiplicato per qualche altro intero K ritorna N. In questo caso si dice anche che N e’ un multiplo di M. Un intero N e’ divisibile per un altro intero M se M e’ un divisore di N; questo implica che dividendo N per M non lascia nessun resto. Infatti se N=K*M allora N/M=K cioe’ il rapporto e’ un numero intero. Introduciamo adesso alcune funzioni molto importanti in Teoria dei Numeri, la branca della matematica che studia le proprieta’ dei numeri interi: la funzione divisori e la funzione divisori unitari. La prima e’ una funzione aritmetica legata ai divisori di un intero e compare in un numero elevato di relazioni. Essa fu studiata da Ramanujan che determino’ alcune sue importanti proprieta’. In generale questa funzione viene definita come:



dove x e’ un qualsiasi numero reale o complesso e

d|n

indica che d divide n. In altri termini questa funzione e’ la somma delle potenze x-esime dei divisori positivi di n. Per quello che interessa a noi analizzeremo il caso x=0 e x=1:

σ0(n), e’ il numero di divisori del numero n
σ1(n) e’ la somma dei divisori di n

Un’altra funzione legata ai divisori e’ la cosiddetta somma aliquota (aliquot sum) di n che e’ la somma dei divisori propri di n cioe’ la somma di tutti i divisori di n escluso n stesso, cioe’ s(n)=σ1(n) – n.
Qui di seguito il grafico della funzione σ0(n) e σ1(n) per n fino a 250.





Facciamo un esempio. Consideriamo n=12. In questo caso avremo:




mentre la somma di tutti i divisori sara’:



e la somma aliquota, cioe’ la somma dei divisori propri:



Qui una tabella riassuntiva dei primi 16 numeri interi:




Adesso possiamo introdurre la definizione di numeri intoccabili. Si chiamano “intoccabili” i numeri interi positivi che non sono la somma dei divisori propri di alcun numero. In altri termini, sono quei numeri n per cui non esiste alcun intero k  per il quale valga:

n = σ1(k) – k=s(k)

Il numero 4, per esempio non puo’ essere intoccabile in quanto esiste un valore k=9 tale che n=4. Il numero 5 invece e’ intoccabile in quanto non esiste alcun numero intero k per cui n puo’ essere scritto come σ1(k) – k, cioe’ 5 non e’ la somma dei divisori propri di nessuno degli interi positivi. In parole semplici, immaginate di avere a disposizione una tabella come quella di sopra per tutti i numeri interi n; i numeri intoccabili sono gli interi che non compaiono mai nell’ultima colonna della tabella.
I primi numeri intoccabili sono:

2, 5, 52, 88, 96, 120, 124, 146, 162, 188, 206, 210, 216, 238, 246, 248,262, 268, 276, 288, 290, 292, 304, 306, 322, 324, 326, 336, 342, 372, 406, 408, 426, 430, 448, 472, 474, 498, ... (sequenza A005114 nell’enciclopedia degli interi on line OEIS)

Il famoso matematico Erdos, nel 1973 dimostro’ che i numeri intoccabili sono infiniti e si pensa che il numero primo 5 sia l’unico intoccabile dispari. Al momento si tratta solo di una congettura che aspetta una dimostrazione. Essa comunque sembra ragionevole in quanto segue dalla congettura forte di Goldbach che stabilisce che ogni numero pari maggiore di 6 puo’ essere scritto come la somma di due primi distinti cioe’ 2n=p+q con p e q numeri primi. Consideriamo un numero dispari 2n+1 maggiore di 7. Se la congettura di Goldbach e’ vera allora possiamo scrivere 2n=p+q da cui abbiamo 2n+1=p+q+1. Ma p+q+1 altro non e’ che la somma dei divisori propri del numero intero p*q e quindi 2n+1= s(p*q) il che significa che 2n+1>7 non e’ intoccabile. Quindi non esiste nessun numero intoccabile dispari maggiore di 7. Essendo inoltre 1, 3 e 7 tutti non intoccabili come si puo’ vedere dalla tabella riportata sopra questo significa che 5 dovrebbe essere l’unico numero intoccabile dispari. Dovrebbe perche’ al momento anche quella di Goldbach e’ solo una congettura.
Tutti i numeri intoccabili, tranne 2 e 5, sono numeri composti (cioe’ un numero che ha almeno un altro divisore oltre a 1 e se stesso) e nessun numero perfetto (un numero n per cui la somma dei suoi divisori propri e’ uguale al numero stesso n) può essere un intoccabile (come esempio vedi il caso del numero perfetto 6 nella tabella riportata sopra). Se i numeri perfetti sono al primo posto nella “scala sociale” dei numeri, gli intoccabili sono all’ultimo. Allo stesso modo nessuno dei numeri amichevoli e socievoli puo’ essere intoccabile. Nel 2011 i cinesi Y-G Chen e Q-Q Zhao hanno dimostrato che la densita’ dei numeri intoccabili, cioe’ il rapporto tra il numero di intoccabili fino a N ed N stesso e’ almeno il 6% anche se non e’ noto se tende a un limite. Dal grafico della densita’ in funzione di N si puo’ congetturare che il limite esista e’ che e’ prossimo al 16%. Ma come sempre in matematica serve una dimostrazione e non una semplice congettura.



Ancora qualche altra proprieta’ dei numeri intoccabili. Se con p indichiamo un qualsiasi numero primo allora i numeri p+1 e p+3 di sicuro non sono intoccabili. Vediamo perche’. Consideriamo il numero k=p2 . La somma dei suoi divisori e’ data da σ1(p2)=1+p+p2 essendo p un numero primo (provate ad usare p=3 per verificare che la somma dei divisori di 9 e’ proprio 1+3+9).
Portando p2 al primo membro otteniamo σ1(p2)-p2=1+p, e quindi esiste un numero k=p2 per cui la somma dei suoi divisori propri e uguale a 1+p e quindi tale numero non puo’ essere intoccabile. Analogamente per il numero p+3. In questo caso esiste un numero k=2p tale che la somma dei suoi divisori propri e’ ugule a p+3. Infatti σ1(2p)=1+2+p+2p (pensate per esempio al caso p=5) da cui si ottiene σ1(2p)-2p=3+p. Il caso 1+p puo’ essere facilmente generalizzato al numero 1+p+p2+p3+….+pn-1 con n un intero positivo, che non puo’ essere intoccabile in quanto σ1(pn)=1+p+p2+p3+…+pn da cui deriva: σ1(pn)-pn=1+p+p2+p3+…..pn-1. Allo stesso modo ci si puo’ divertire a mostrare quali altri numeri sono di sicuro non intoccabili. Osserviamo per esempio, che la somma dei divisori del numero pn*q con p e q due primi ed n un numero naturale qualsiasi e’ data da:

σ1(pn)=1+p+p2+p3+…..pn+q+pq+p2q+…+pnq

da cui otteniamo:

σ1(pn)-pnq=1+p+p2+p3+….+pn+q+pq+p2q+…+pn-1q

e quindi di sicuro il numero:

1+p+p2+p3+….+pn+q+pq+p2q+…+pn-1q

non e’ intoccabile. Provate a sostituire p=2, n=3 e q=3 per convicervi che e’ cosi.
Diamo adesso un’occhiata a quella che in Teoria dei numeri si chiama gap, cioe’ la distanza tra termini successivi di una qualsiasi sequenza numerica. Qui di seguito le distanze tra i primi 30 numeri intoccabili (vedi colonna gap). Ad un primo sguardo sembra che non emerga nessun tipo di pattern particolare. Ma guardando attentamente possiamo vedere che ogni tanto compaiono dei numeri intoccabili a distanza di 2 (ricordare che non e’ possibile avere numeri consecutivi intoccabili, cioe’ a distanza 1 se viene provato che 5 e’ l’unico numero intoccabile dispari) e che a volte questi 2 formano delle doppiette, triplette, quadriplette e cosi via. Per esempio 246 e 248 e’ la doppietta piu’ piccola di numeri intoccabili. 288, 290 e 292 la tripletta piu’ piccola e cosi via. Esistono tutte le n-plette da 2 all’infinito? Al momento nessuno conosce la risposta. Se non sono infinite quale’ allora il suo limite superiore?



Qui di seguito l’istogramma del gap dei primi 8153 numeri intoccabili. La maggior parte degli intoccabili amano stare ad una distanza 2 uno dall’altro, seguito poi da 4, 6 8 e cosi via secondo una legge esponenziale. E’ possibile quindi congetturare che tra i numeri intoccabili esistano tutte le distanze pari (gap) da 2 all’infinito.



Prima di passare ai numeri intoccabili unitari dobbiamo parlare dei divisori unitari. In matematica, un numero intero m e’ un divisore unitario di un numero n se m e’ un divisore di n e se m e il rapporto n/m sono coprimi, cioe’ non hanno alcun fattore comune altro che 1. Il numero 5, per esempio e’ un divisore unitario di 60, perche’ 5 e 60/5 hanno solo 1 come fattore comune. Al contrario 6 e’ un divisore di 60 ma non e’ unitario in quanto 6 e 60/6 hanno come fattori comuni 2 e 3. Il numero 1 e’ il divisore unitario di ogni numero naturale. Per ogni numero n, il numero di divisori unitari e’ pari a 2k dove k e’ il numero di fattori primi distinti di n. Per esempio se n=10, avremo 2 distinti fattori 2 e 5 e quindi il numero di divisori unitari e’ 4. Nel caso invece di n=8 in questo caso il numero di fattori primi distinti e’ 1 essendo 8=2x2x2 e quindi il numero di divisori unitari di 8 e’ 2. Una proprieta’ molto importante per tali divisori e’ quella che stabilisce che tutti i divisori di un numero n sono unitari se e solo se n e’ square-free cioe’ se tra i sui fattori primi non ci sono quadrati perfetti. Prendiamo il numero 10. I suoi fattori primi sono 2 e 5 e quindi si tratta di divisori unitari. Consideriamo adesso 18. I suoi fattori primi sono 32 e 2 e quindi in questo caso essendo n non square-free non tutti i suoi divisori sono unitari (come per esempio il fattore 3). Un’altra proprieta’ facilmente dimostrabile e’ che un qualsiasi numero naturale M=pn con p un primo ed n un intero positivo ha come divisori unitari solo 1 ed M stesso. I divisori di M infatti, sono 1, p, p2, p3,…..pn e nessuno di questi ad eccezione di 1 ed M formano una coppia coprima (pk, pn/pk) essendo p un fattore comune per k compreso tra 1 ed n. Come fatto con i divisori, anche per i divisori unitari possiamo costruire una funzione somma che indichiamo sempre con la lettera greca sigma ma apponendo un asterisco come apice.



In questo caso essendo i divisori del numero n unitari, significa che d e n/d non hanno fattori comuni il che si puo’ esprimere come gcd(d,n/d)=1. Gcd indica il massimo comun divisore tra due numeri. Per esempio gcd(12,90)=6. I divisori di 90 infatti sono:

1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90

e quelli di 12:

1, 2, 3, 4, 6, 12

e quindi i fattori comuni tra i due numeri sono 1, 2, 3 e 6 di cui 6 e’ il massimo.
Se l’unico divisore comune e’ 1 allora i due numeri sono coprimi o anche relativamente primi. Analogamente alla definizione di numeri intoccabili, gli unitari intoccabili sono quei numeri interi positivi che non sono la somma dei divisori unitari propri di alcun numero. In altri termini, sono i numeri n per cui non esiste alcun intero k per il quale valga:

n = σ*1(k) – k=s*(k).

Qui di seguito gli intoccabili unitari minori di 10000

2, 3, 4, 5, 7, 374, 702, 758, 998, 1542, 1598, 1778, 1808, 1830, 1974, 2378, 2430, 2910, 3164, 3182, 3188, 3216, 3506, 3540, 3666, 3698, 3818, 3846, 3986, 4196, 4230, 4574, 4718, 4782, 5126, 5324, 5610, 5738, 5918, 5952, 6002, 6174, 6270, 6404, 6450, 6510, 6758, 6822, 6870, 6884, 7110, 7178, 7332, 7406, 7518, 7842, 7902, 8258, 8400, 8622, 8670, 8790, 8850, 8862, 8916, 8930, 8982, 9116, 9518, 9522, 9558, 9570, 9582, 9642, 9930 (sequenza A063948 in OEIS)

Come gia’ riportato per gli intoccabili, se assumiamo la veridicita’ della congettura forte di Goldbach, allora gli unici numeri dispari intoccabili unitari saranno 3,5 e 7. E gli unici primi intoccabili unitari saranno 2, 3, 5, e 7.
Quanto sono frequenti i numeri intoccabili unitari tra i numeri naturali? Sembrerebbe non molto se guardiamo la seguente tabella che riporta il numero di intoccabili unitari minori o uguali a diverse potenze di 10. Tra o e 1 miliardo ci sono solo circa 11.000.000 di intoccabili unitari.



Cosa possiamo dire sulla loro densita’, cioe’ sul rapporto tra il numero di intoccabili unitari minori o uguali a N ed N stesso?



L’andamento di tale funzione ci permette di congetturare una convergenza asintotica ad un valore costante che potrebbe essere prossimo all’1%. Questo dovrebbe significare che man mano ci spostiamo verso i numeri naturali sempre piu’ grandi, avremo in media 1 numero intoccabile unitario ogni 100 numeri naturali. Proviamo adesso a vedere come si comporta la distribuzione asintotica dei numeri intoccabili unitari. Vogliamo studiare cioe’ il comportamento della funzione
Π(N) = numero di intoccabili unitari minori o uguali ad N
per N che tende all’inifinito.
Il grafico di tale funzione per il primo miliardo di numeri naturali ha un andamento chiaramente lineare dopo un plateau iniziale. Continuera’ sempre con questa pendenza fino all’infinito? Nessuno lo sa al momento. Possiamo solo pensare che sia cosi.



Un altro grafico che possiamo costruire e’ quello che riporta il rapporto N/Π(N) in funzione di N sempre per il primo miliardo di numeri naturali. Ovviamente questo andamento e’ speculare rispetto alla densita’ vista precedentemente.



Se proviamo a fare un fit non lineare di questi punti otteniamo una funzione del tipo
N/ Π(N)=a+b/(1+(N/c)d)
con le costanti a,b,c e d tutte positive ed un R2 maggiore del 98%. Visto che siamo interessati all’andamento asintotico, possiamo trascurare l’1 al denominatore essendo (N/c)d >> 1. Quindi:

N/ Π(N)=a+b/(N/c)d

da cui otteniamo:

Π(N)=N/(a+b’/Nd)

avendo indicato con b’>0 il prodotto bcd. Ma per valori di N sempre piu’ grandi il rapporto b’/Nd tendera’ a zero e in definitiva la funzione Π avra’ un comportamento lineare (con 1/a=a’):

Π(N)=N/a --> a’N

mentre la densita’ convergera’ ad un valore costante:

Π(N)/N -->1/a=a’

Come gia’ detto piu’ volte, questi risultati sono di tipo euristico e attendono una dimostrazione matematica rigorosa. Qualcuno vuole provarci?
Cosa possiamo dire invece sulle n-uplette di numeri intoccabili unitari positivi con piu’ di una cifra e con distanza 2 tra loro? Tra i primi 10000 intoccabili unitari la doppietta piu’ piccola e’ 30756, 30758.
Non e’ stata trovata invece nessuna tripletta. Resta quindi aperta l’individuazione della piu’ piccola tripletta di numeri intoccabili unitari. Esistono infinite n-uplette o queste sono finite? E in quest’ultimo caso quale e’ il limite superiore? Come fatto per gli intoccabili diamo un’occhiata alla distribuzione delle distanze tra i numeri intoccabili unitari. In questo caso la distribuzione non mostra la regolarita’ osservata pr quella dei numeri intoccabili. C’e’ una notevole frastagliatura con dei picchi che emergono qua e la. Si puo’ osservare, comunque una prevalenza di picchi per distanze pari a 12 o suoi multipli (verificato fino a 132). Non so se questo e’ stato gia’ osservato o studiato da qualcuno. Certo non sembra un pattern casuale e andrebbero aggiunti piu’ numeri ai 10000 che ho considerato io per stabilirne la reale presenza. Anche qui un altro quesito che al momento rimane aperto.



Chiudiamo il post riportando alcuni tipi di numeri che non possono essere intoccabili unitari:

1+p+q
1+p2+2n
1+q+p2
1+n+p

con p e q numeri primi ed n un qualsiasi numero intero positivo.
La dimostrazione e’ molto semplice. Per il primo caso esiste un numero k=pq tale che s*(k)=1+p+q. Per il secondo caso questo numero e’ k=2np, per il terzo k=p2q e per l’ultimo k=np.
Qui alcuni siti interessanti che parlano di classi di numeri, sequenze e teoria dei numeri per chi vuole approfondire.

http://www.bitman.name/home/      in italiano
http://oeis.org/
http://www.openproblemgarden.org/category/number_theory_0
http://math.ucalgary.ca/math_unitis/profiles/richard-guy 

http://www.wikio.it