miércoles, 20 de octubre de 2010

Nueva Formula Generadora de Primos

Jeffrey Shallit (Profesor de la Universidad de Waterloo) recientemente publicó en su blog una Fórmula recurrente o que muchos llamarían recursiva la cual fue desarrollada por Eric Rowland y que permite generar Números Primos.

La Fórmula es :
Se define como a(1)=7
Para n >=2, a(n)=a(n – 1) + M.C.D.(n, a(n – 1)).

Donde M.C.D. es Máximo común divisor.

Así por ejemplo : a(1) = 7, a(2) = a(1) + mcd(2, 7) = 7 + 1 = 8.

Los primeros valores de la secuencia son :
7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41,...

En tanto que las diferencias de los valores de la secuencia son :

1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, ...

Si se ignoran los unos de las diferencias , la fórmula de Rowland genera los primos 5, 3, 11, 3(otra vez) y 23. Continuando el proceso y eliminado los duplicados, la fórmula genera la siguiente secuencia :

5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559,15131, 53, 30323, . . .

Los cuales son números Primos...Sorprendente!

2 comentarios:

jedagravi1 dijo...

Hice la verificación de valores con excel y me parece fascinante... también estoy interesado en números primos...

JOSÉ CAMACHO MEDINA dijo...

saludos jedagravi1, si es muy interesante la formula recursiva de rowland, te invito a que nos unamos para la conquista de los numeros primos...un abrazo