SOLUZIONI SOLUZIONI

2001

I NUMERI PERFETTI

Il primo problema del mese

> La soluzione di Luca Terreni

> La soluzione di Matteo Tognela

x=2^n*[2^(n+1)-1]
supp. [2^(n+1)-1] primo
chiamo S la somma dei divisori di x e utilizzo la proprietà che
2^0+2^1+...+2^n=2^(n+1)-1
S=[2^0+2^1+...+2^n] + [2^(n+1)-1][2^0+2^1+...+2^(n-1)]
=2^(n+1)-1 + (2^(n+1)-1)(2^n-1)=
=2^n*(2^(n+1)-1)=x
CVD

> La soluzione di Rocco Lupoi

Nelle ipotesi che p sia primo, i divisori di N sono:

1, 2, 2^1, 2^2, ..., 2^n, (2^(n+1) - 1), 2(2^(n+1) - 1), 2^2(2^(n+1) - 1), ..., 2^(n-1)( 2^(n+1) - 1).

Essendo, per ogni k, 1+2+2^1+2^2+ ...+2^k=2^(k+1) -1 , la somma dei divisori di N vale:

SdN = 2^(n+1) -1 + (2^n - 1)( 2^(n+1) - 1) = (1 + 2^n - 1) (2^(n+1) - 1) = N.

> La soluzione di Sergio Natale

Indico con S(x) la funzione di x intero positivo che è la somma dei divisori di
x.
Pertanto, ad esempio:
S(1)=1
S(2)=3
S(3)=4
S(4)=7
Per dimostrare che k=2^n.[2^(n+1)-1] è un numero perfetto basta dimostrare che
S(k)=2.k
Indico con P il numero primo 2^(n+1)-1
Osservo che S(k) =S(2^n).S[2^(n+1)-1] =S(2^n).S(P)
Ma S(P) =P+1= 2^(n+1)
S(2^n)= 2^(n+1)-1
Infatti:
S(2^2) =S(4) =7 =2^3-1
S(2^3) =S(8) =15=2^4-1
Pertanto:
S(k) =[2(n+1)-1].2^(n+1) =2.2^n.[2^(n+1)-1] =2.k
CVD

> La soluzione di Lorenzo Grandi

> La soluzione di Jacopo Viti

> La soluzione di Andrea Bortolotti

> La soluzione di Giovanni Tocci

Giovanni segnala alcuni  link (in inglese) sui numeri perfetti:

- un po' di storia sui numeri perfetti:
http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Perfect_numbers.html

- qui c'e' anche un teorema molto simile al problema del mese che
  collega i numeri perfetti con i "numeri di Mersenne"
http://www.utm.edu/research/primes/mersenne.shtml

- contiene il piu' grande numero perfetto conosciuto: attenzione e' una
  pagina molto grande perche' contiene tutte le 1,819,050 cifre del numero
http://calendarhome.com/prime/perfect4.html

> La soluzione di Luigi Bernardini

Se 2ⁿ⁺¹-1 è primo, i divisori di N sono solo e soltanto:

    a) divisori di 2ⁿ, che sono le potenze di 2 da 2⁰ a 2ⁿ, e la cui somma è 2ⁿ⁺¹-1

    b) i prodotti del tipo (2ⁿ⁺¹-1) 2^k per k da 0 a n -1 , e la cui somma è (2ⁿ⁺¹-1)( 2ⁿ-1)

La somma dei divisori di N è pertanto:

2ⁿ⁺¹-1+(2ⁿ⁺¹-1)( 2ⁿ-1) = (2ⁿ⁺¹-1)(1+2ⁿ-1) = 2ⁿ(2ⁿ⁺¹-1) = N

N risulta quindi essere un numero perfetto, C.D.D.

> La soluzione di Maurizio Castellan

Se n=0    2^(n+1) -1= 1  non è primo e m = 1 non è perfetto.

Se n>0    m > 1  , e  se 2^(n+1) -1 è primo,  2^n· (2^(n+1) -1)  è la sua scomposizione in fattori primi.

I suoi divisori sono quindi del tipo:

2^k   oppure del tipo   2^k· (2^(n+1) -1)     dove  k = 0, 1, ... n.

Essendo 2^(n+1) -1 dispari, i divisori del primo e del secondo tipo sono tutti diversi.

Ne segue che la somma di tutti i divisori di m è:

(2^0+2^1+....+2^n)+[2^0 * (2^(n+1) -1) +2^1* (2^(n+1) -1)+...  +2^n* (2^(n+1) -1)] =

= (2^0+2^1+....+2^n) + (2^(n+1) -1) * (2^0+2^1+....+2^n) =

= 2^(n+1) * (2^0+2^1+....+2^n)  = 2^(n+1) * [ 2^(n+1) -1 ] = 2 * 2^n * [ 2^(n+1) -1 ] = 2 * m

cioè m è un numero perfetto.

> La soluzione di Pier Luigi Zezza

Trovare il quinto numero perfetto.

Si tratta del numero   33550336 (indicato da Bernardini e Zezza)

Quali sono i primi otto numeri perfetti?

> Bernardini li trova con il programma in Visual Basic che alleghiamo sotto:

> Zezza indica i primi dieci trovati con Maple VI

Quanti sono i numeri perfetti attualmente conosciuti?

Qual è il più grande numero perfetto attualmente conosciuto? A quando risale la sua scoperta?

Scrive Bernardini:

Il più grande numero perfetto oggi noto è 2^6972592(2^6972593-1)

Il numero, che ha 4.197.919 cifre, è stato trovato nel giugno 1999 da Hajratwala, Woltman, Kurowski.

Si ritiene sia il 38° numero perfetto, in quanto non è stato ancora verificato se esistano altri perfetti tra l'ultimo perfetto accertato, il 37°, e il numero in questione.

L'informazione è tratta dal sito Internet dell' Università del Tennessee www.utm.edu/research/primes

Il secondo problema del mese

> La soluzione di Andrea Bortolotti

Program Numeri_Perfetti (input, output);

Il programma seguente trova i primi perfetti cercandoli tra i numeri della forma N = 2ⁿ (2ⁿ⁺¹-1) quindi, come dimostrato dai matematici, trova tutti quelli minori di un eventuale numero perfetto dispari di almeno 300 cifre.

Program Numeri_Perfetti_2 (input, output);

END. (*Numeri_Perfetti_2*)

> La soluzione di Luigi Bernardini

La ricerca di numeri perfetti (pari) si identifica con la ricerca di numeri primi della forma 2^k+1-1 A ciascun di essi corrisponde il numero perfetto 2^k(2^k+1-1).

Un noto teorema afferma inoltre che se 2^k+1-1 è primo, anche k+1 è primo.

Il seguente programma, in Visual Basic, partendo dai valori di k più bassi, ricerca e visualizza i primi 8 numeri perfetti. Il limite di 8 è dato dalla possibilità di Visual Basic di gestire interi con un numero maggiore di cifre.

Public Sub Principale()

For k = 1 To 30

If VerificaPrimo(k + 1) = True Then

h = 2 ^ (k + 1) - 1

If VerificaPrimo(h) = True Then

Print 2 ^ k * h

End If

End If

Next k

End Sub

Public Static Function VerificaPrimo(w)

VerificaPrimo = False

If w = 2 Then

VerificaPrimo = True

Exit Function

End If

For t = 2 To Int(Sqr(w)) + 1

If w - Int(w / t) * t = 0 Then

Exit Function

x = DoEvents

End If

Next t

VerificaPrimo = True

End Function

Per ricercare i numeri perfetti compresi tra N1 e N2 occorrerebbe completare il programma di cui sopra facendo precedere una routine che calcoli i valori interi k1 e k2 per cui 2^k1(2^k1+1-1) = N1 e 2^k2(2^k2+1-1) = N2 , e fare variare k tra k1 e k2.

K1 e k2 risultano essere

k1=Int(Log(Sqr(8*N1+1)+1)/Ln(2)-2) e k2= Int(Log(Sqr(8*N2+1)+1)/Ln(2)-2)

> La soluzione di Maurizio Castellan

Program Numeri_perfetti;
uses
WinCrt; 
var
min,max,n,S,d:longint; 
begin
Writeln('Test numeri perfetti per n appartenente all','''intervallo [min,max]');
Writeln('(overflow per n>2147483647) ');
Writeln;
Writeln('inserisci min');
readln(min);
Writeln('inserisci max ');
readln(max);
Writeln;
for n:= min to max do
begin
if n<>0 then (* altrimenti il programma riconosce zero come perfetto *)
begin
S:=0;
for d:=1 to (n Div 2) do (* i divisori propri non superano la metà del numero *)
begin
if n mod d=0 then
S:=S+d;
end;
if n=S then
Writeln(n,' è un numero perfetto ');
if n=max then 
Writeln('tra ',min,' e ',max,' non ci sono altri numeri perfetti '); 
end;
end;

> La soluzione di Matteo Tognela

Un semplice algoritmo per la generazione dei numeri perfetti potrebbe essere questo:

read(a);
read(b);
for i=a to b do
begin
j=2;
s=1;
repeat
if i/j=int(i/j) then s=s+j;
j=j+1;
until s>1 or j>int(i/2);
if s=i then write(s);
end;

compatto,ma molto "manuale".Sono comunque costretto ad utilizzarlo per i perfetti dispari (convertito in un ciclio repeat...until)
non essendoci a monte una teoria completa. Per quanto riguarda i pari, è utile ricordare che [2^(n+1)-1] primo implica n+1 primo; essendo gli n in questione molto minori rispetto ai termini del tipo 2^n*... conviene svolgere un controllo sul fatto
che n+1 sia primo, ed effetture la verifica sulla perferzione solo per tali valori di n.


Program perfect;

Var
i,j,a,b,s:integer;

Begin {PARTE PER I DISPARI}
read(a);
read(b);
i=2*int(a/2)+1; {primo dispari >=a}
repeat
j=3;
s=1;
repeat
if i/j=int(i/j) then s=s+j;
j=j+2;
until s>i or j>int(i/3)
if s=i then write i;
i=i+2;
until i=2* int(b-1/2)+3 {ultimo dispari<=b}
                {PARTE PER I PARI}
i=int(ln(a-2)-1); {Buona approssimazione per difetto del primo n utile}
while 2^i*(2^(i+2)-1)<a do i=i+1;
repeat
j=2;
while j<int((i+1)/2) and (i+1)/j<>int(i+1)/j do j=j+1;
if j=int((i+1)/2) then {ossia,se i+1 è primo...}
begin
s=2^(i+1)-1;
j=3;
while j<int(s/2) and int(s/j)<>s/j do j=j+1;
s=2^i*(2^(i+1)-1);
if j=int(s/2) then write(s);
end;
i=i+2;
s=2^i*(2^(i+1)-1);
until s>b
End.

Una segnalazione particolare merita Pier Luigi Zezza, che propone l'utilizzo di Maple VI, un potente sistema di algebra simbolica.