Teoria dei numeri - Il problema di Riesel e di Sierpinski

Il problema di Riesel e il problema di Sierpinski

Nella teoria dei Numeri si definisce numero di Riesel un valore k dispari tale che, per ogni n,
il termine k*2^n-1 è un numero composto.

Nel 1956 Hans Riesel dimostrò che esistono infiniti numeri di Riesel, con una tecnica di "insieme ricoprente".

Un insieme ricoprente è un insieme di numeri primi piccoli tali che ogni termine di una successione sia
divisibile per uno di essi (da qui il nome di "ricoprente").

In base a tale tecnica Riesel mostrò che 509203 era un numero di Riesel.

Poichè finora non è stato trovato nessun insieme ricoprente per valori di k inferiori a 509203, si ipotizza
che esso sia il più piccolo numero di Riesel.

Il "problema di Riesel" è di determinare il più piccolo numero di Riesel.

Esempi
k=5 non può essere un numero di Riesel, perchè già con n=2 si ottiene che 5*2^2-1=19 è un numero primo.
k=509203 se lo si prova per 10 mila o 1 milione di valori di n non si ottiene un primo; ad esempio di fatti
con PARI/GP si possono scrivere due linee di comando del tipo:

a=509203
for(i=1,10000, b=a*2^i-1; if(isprime(b)==1,print("prime ",b," for n: ", i);); );

Il problema di Sierpinski
Tale problema è analogo a quello di Riesel. E' definito numero di Sierpinski un numero k dispari, che per ogni n, produce numeri composti k*2^n+1.

Qual è il più piccolo numero di Sierpinski? Nel 1962 John Selfridge propose come il più piccolo numero di Sierpinski 78557. Per dimostrare che esso è il più piccolo occorre dimostrare che i dispari precedenti non sono numeri di Sierpinski. Finora è stato dimostrato per tutti i numeri eccetto per diciassette di essi.


Ricerca algoritmica
Il progetto Riesel Sieve (analogo a Seventeen oppure Bust), progetto di calcolo distribuito, sta analizzando almeno 75 valori di k minori di 509203, che possono considerarsi PRN ("Probable Riesel's number").

Un interessante valore è il 659.

Un algoritmo proponibile in PARI/GP, per entrambi i problemi, che si può ulteriormente ottimizzare, è il seguente da me proposto.

/*
*  Riesel's Number Research
*  Sierpinski's Number Research
*
*  Author    : Rosario Turco
*  Date        : 16/04/2010
*  Revision    : 1.0         
*/

RSL(start=3, end=1001, s=1, n=1000, r=1)=local();{
 if( start%2 == 0, error("inserire uno start dispari"););
 i = start;
 while(i
       RSLR(i,s,n,r); 
       i = i+2;
 );
 print("start : ", start," end : ", end);
}

RSLR(val,s=1,n=1000,r=1)=local(out="",trovato=0); {
    for(j=s,n,
        if( r == 1,
            a = (val*2^j) - 1;
        );
        if( r == 0,
            a = (val*2^j) + 1;
        );
        if( isprime(a) == 1,
            trovato=1;
            print("Nok at n: ", j);
            j=n+1;
        );
     );

     if(trovato == 0,
        if( r == 1,
            out = concat( out, "Probable Riesel's number: k=");
        );
        if( r == 0,
            out = concat( out, "Probable Sierpinski's number: k=");
        );
        out = concat( out, val);
        out = concat( out, " on ");
        out = concat( out, n);
        out = concat( out, " values ...");
        print(out);
     );
}





Riferimenti
Wikipedia
http://www.seventeenorbust.com



Alla prox