viernes, 4 de septiembre de 2009

201 - Una nueva fórmula para generar números primos.

Algunas expresiones simples sorprendentemente pueden generar una gran cantidad de números primos. Es bien conocida la fórmula x2+x+41 que genera números primos cuando x toma los valores desde el cero hasta el 40. Otra fórmula simple es x2+x+17 que genera primos si x va desde 0 a 15. Sin embargo encontrar algún polinomio que genere primos para cualquier valor de x nunca dio frutos, inclusive los matemáticos ya probaron que no existe una expresión polinómica con coeficientes enteros que genere solo valores primos.

Jeffrey Shallit un profesor de la universidad de Waterloo y editor de "the Journal of Integer Sequences" publicó en su blog la fórmula recursiva del estudiante Eric Rowland para generar números primos.

La fórmula es la siguiente:
Se define como a(1)=7
Para los n mayores o iguales a 2, a(n)=a(n – 1) + mcd(n, a(n – 1)) donde mcd = Máximo
común divisor.
Así por ejemplo : a(1) = 7, a(2) = a(1) + mcd(2, 7) = 7 + 1 = 8.
El generador de primos es entonces a(n) – a(n – 1).
Los números resultantes son los llamados primeras diferencias de la secuencia original.

Los primeros 23 valores de la secuencia son :
7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69
En tanto que sus diferencias son :
1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23

Si se ignoran los unos, se ve que 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, . . .
Rowland describió su fórmula en el blog "A New Kind of Science", él explica que genero su fórmula en el colegio donde los participantes estaban desarrollando sistemas
computacionales que exhiban un comportamiento interesante.
Esta fórmula produce el primo p después de generar (p – 3)/2 1s. Por lo tanto le lleva mucho tiempo a esta fórmula generar primos grandes.
Recientemente un matemático francés Benoit Cloitre probó que poniendo b(1) = 1 y b(n) = b(n – 1) + mcm(n, b(n – 1)) para n mayor o igual a 2, b(n)/b(n – 1) – 1 es 1 o primo.


Sacado del blog "The mathematical Tourist"
Si lo quieres compartir o guardar
Share/Bookmark

24 comentarios:

  1. EDGAR Merchan garcias por sacar una formula matematica de como sacar numeros primos desde Macas morona Santiago Ecuador programando para el mundo the maigic alterno........

    ResponderEliminar
  2. no se entiende nada pueden hacerlo mas practico y sencillo

    ResponderEliminar
    Respuestas
    1. no pibe que te pensas que somos nosotros gil haceme un pete

      Eliminar
    2. esta de puta madre xD.
      si no lo entiendes vuelve a leer, pero creo que tu eres el del problema.

      Eliminar
    3. Bueno, Anonimos despues de todo `parece ser que no sirvio esa mierda .... ja,ja,ja.

      Eliminar
  3. si x=1 (primer número primo)

    NP = Número primo

    x+(x+1) = NP
    NP = (NP-1) / 2 = x

    ResponderEliminar
    Respuestas
    1. el 1 no es un número primo, simplemente porque no entra en la definición fundamental.

      Eliminar
  4. Chequen esta nueva fórmula, esta impresionante, wow!...

    http://misterionumerosprimos.blogspot.com

    ResponderEliminar
  5. cuanto pagan por una nueva y buena fórmula para encontrar números primos...

    ResponderEliminar
  6. Perdón pero el 1 no es primo es "coprimo"

    ResponderEliminar
    Respuestas
    1. no seas idiota, coprimo significa que si DOS numeros son coprimos entre si, su mcd es 1

      Eliminar
    2. Eres un imbecil, maldito idiota. El ultimo Anonimo tiene razon.

      Eliminar
  7. Ojala descubran una formula que no genere tanto 1 y que NO sea recursiva , ya que si quieres sabes cuanto es a(500)
    necesitas conocer a(499) y para ello a(498)
    y asi sucesivamente ...

    ResponderEliminar
    Respuestas
    1. y el algoritmo tardaría demasiado tiempo, años.

      Eliminar
  8. buff la verdad que tiene razon el del comentario de arriba ...
    ¿Se ha visto metodo mas ineficiente para generar numeros primos??
    :)

    ResponderEliminar
    Respuestas
    1. no hay fórmula matemática, lo que si hay son muchos algoritmos muy buenos. La mayoría siguen la misma estrategia: dado un número dividirlo por sus anteriores hasta el 2 y si todos los restos de la división son diferentes de cero, retorna el número que será un primo. Este algoritmo se puede optimizar si se evitan los números pares, múltiplos de 5, múltiplos de 3 y 9.

      Eliminar
    2. Ese metodo de probar desde el 2 en adelante todos los primos se llama division por tentativa y para determinar la primalidad o no de grandes cantidades es computacionalmente ininpracticable.

      Eliminar
  9. Los que critican, entonces busquen la formula por vosotros mismos, y si no callaros de una vez y dejen a los demas pensar. Por mediocres como vosotros no avanza la sociedad. Un saludo

    ResponderEliminar
  10. Les comparto una fórmula que desarrolle recientemente y que genera a los primeros
    221 números primos, es muy sencilla interesante, chequenla:

    http://misterionumerosprimos.blogspot.mx/2012/10/formula-que-genera-los-primeros-221.html

    ResponderEliminar
  11. El proceso más eficiente y veloz para listar primos es la criba primorial de Eratóstenes; ésta permite prescindir de los pares, múltiplos de 3, 5, 7, 11, 13, etc, a medida que crece el primorial.

    ResponderEliminar
  12. hasta ahora si lo piensas bien ; para hallar un numero primo entre 0 y 100 se podria aplicar esta formula: 2 + 3x ; siempre y cuando x no termine en 1 ----- adicionalemte si a un numero primo le sumas 2 te dara otro numero primo ... en ciertas ocaciones =)

    ResponderEliminar

Si quieres deja un comentario, si la entrada tiene mas de 15 dias deberás esperar a que la autorice y por favor si no tienes gmail deja tu nombre si no quedas como anónimo. Gracias!