[HACK] Numeros primos

[David A. Pérez]

Se nota cuando a jcea le gusta algo... o no...

Gracias por la respuesta.

Ya que esta la lista parada, vamos a darle marcha aunque sea con
matematicas...


> > El otro dia me di cuenta que en base dos podemos saber si un numero es
> > no primo con una probabilidad del 50%. Los numeros binarios que acaban
> > en 0 son no primos, y los que acaban en 1 pueden serlo.
>
> Eso no determina si un número es primo o no con probabilidad del 50%.
> Dirás que con ese test eliminas la mitad de los números, que sabes que
> no son primos. Pero no sabes nada sobre la otra mitad.

A eso me referia. Pero que mal me expreso!

>
> > En base diez, la probabilidad aumenta al 60% (no primos los acabados
> > en 0, 2, 4, 5, 6 y 8).
>
> 10 es 2*5. Ese test elimina cualquier número múltiplo de 2 y de 5.
>
> Si trabajases con base 2*3*5*7 = 210, eliminarías aún más números.

Efectivamente... lo cual hecha por terra mi teoria, de que a mayor base,
mayor el porcentaje de numeros no primos eliminados. No depende de la base
sino del numero de factores primos que tenga la base.

> Si te interesa la teoría de números, que es un tema apasionante, hay
> muchísimo material en Internet, incluyendo libros universitarios y tesis
> doctorales, todo gratis.

Ya..., pero es mas facil que te digan por donde tirar que andar buscando...

En cualquier caso, he hecho ciertos calculos.

Si p es la sucesion de numeros primos de tal modo que p0=2, p1=3, p2=4...

y b es una base del productorio desde i=0 hasta n de la sucesion p

el numero de no primos eliminados (llamemosle a0) por p0 es b/p0

el numero de no primos no eliminados (llamemosle a1) por p1 es b/p1 menos
los que ya habian sido elimiandos por a0 y que son multiplos de p1...

a0 = b/p0
a1 = (b-a0)/p1
a2 = (b-a0-a1)/p2
an = (b-(sumatorio desde i=0 hasta n-1 de ai))/pn

Y la suma de todos los a dividido entre la base es el procentaje de numeros
que pueden ser primos.

Me he pasado 3 horas haciendo dibujitos en hojas de papel en blanco, asi que
no es facil de explicar en un correo.

La conclusion a la que he llegado despues de pasar mis calculos a C son:

Biggest Prime: 2
         Base: 2
   Percentage: 50

Biggest Prime: 3
         Base: 6
   Percentage: 33.3333333333333

Biggest Prime: 5
         Base: 30
   Percentage: 20

Biggest Prime: 7
         Base: 210
   Percentage: 14.2857142857143

Biggest Prime: 11
         Base: 2310
   Percentage: 9.09090909090909

Biggest Prime: 13
         Base: 30030
   Percentage: 7.69230769230769

Biggest Prime: 17
         Base: 510510
   Percentage: 5.88235294117647

Biggest Prime: 19
         Base: 9699690
   Percentage: 5.26315789473684

Biggest Prime: 23
         Base: 223092870
   Percentage: 4.34782608695652

[...]

Biggest Prime: 739
         Base: 3.90817700074735E+306
   Percentage: 0.135317997293642

Por encima del 739 esta el 743, pero ya no puedo seguir haciendo tests con
el codigo actual (Overflow).

La conclusion es que el numero de primos no es superior al 0.135%

Habria alguna forma de hallar este limite con una demostracion???

(Supongo que si se puediera hallar no tendria ningun resultado practico,
pero tampoco lo tiene el saber el porcentaje de materia oscura del universo
y no por ello deja de interesarnos ;)

Salu2,

David A. Pérez

                              http://www.kamborio.com/
 _                       _                   _
| | __  __ _  _ __ ___  | |__    ___   _ __ (_)  ___
| |/ / / _` || '_ ` _ \ | '_ \  / _ \ | '__|| | / _ \
|   < | (_| || | | | | || |_) || (_) || |   | || (_) |
|_|\_\ \__,_||_| |_| |_||_.__/  \___/ |_|   |_| \___/
      El perdón es la venganza de los buenos (anónimo)