Sucesion parcial o completa entre numeros primos.

Iniciado por Usuario887, 7 Febrero 2021, 18:07 PM

0 Miembros y 1 Visitante están viendo este tema.

Tachikomaia

Sería realmente difícil de hallar, pero hay ciertos patrones, como que se dan pares de números que se diferencian entre 2, lo cual sucede porque deben ser impares (salvo el 2).

2 y 3 (diferencia 1)
5 y 7 (diferencia con respecto a los anteriores: 2. Diferencia entre sí: 2)
11 y 13 (diferencia con respecto a los anteriores: 4. Diferencia entre sí: 2)
17 y 19 (diferencia con respecto a los anteriores: 4. Diferencia entre sí: 2)
23 y 29 (diferencia con respecto a los anteriores: 4. Diferencia entre sí: 6)

La cuestión sería entender cada cuanto y que tanto cambian.

kub0x

Cita de: Tachikomaia en  7 Febrero 2021, 22:06 PM
Sería realmente difícil de hallar, pero hay ciertos patrones, como que se dan pares de números que se diferencian entre 2, lo cual sucede porque deben ser impares (salvo el 2).

2 y 3 (diferencia 1)
5 y 7 (diferencia con respecto a los anteriores: 2. Diferencia entre sí: 2)
11 y 13 (diferencia con respecto a los anteriores: 4. Diferencia entre sí: 2)
17 y 19 (diferencia con respecto a los anteriores: 4. Diferencia entre sí: 2)
23 y 29 (diferencia con respecto a los anteriores: 4. Diferencia entre sí: 6)

La cuestión sería entender cada cuanto y que tanto cambian.

El teorema de los numeros primos (prime number theorem o PNT) nos da una cota (asintota) que indica la cantidad de nº primos entre los nº enteros. La funcion [latex]\pi(x)=\frac{x}{\ln(x)}[/latex] nos da una aproximación para los primos inferiores a x.

Pruébalo, por ejemplo, por debajo de 100 sabemos que hay 25, calculamos [latex]\pi(100)=\frac{100}{\ln(100)}=21.71472[/latex]. Como ves se aproxima. La teoría detrás está en https://en.wikipedia.org/wiki/Prime-counting_function

Sobre los patrones que comentas, realmente la diferencia dos se llama Twin prime, ya que [latex]p_2-p_1=2[/latex] y Sexy Primes cuando [latex]p_2-p_1=6[/latex]

Si resolvieras la Twin Prime Conjecture pues serías mundialmente reconocido. Encuentras más info aquí https://en.wikipedia.org/wiki/Schinzel%27s_hypothesis_H

https://en.wikipedia.org/wiki/Twin_prime
https://en.wikipedia.org/wiki/Sexy_prime

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate


nosoy

#12
No es muy difícil preparar un programa casero de cálculo de los números primos. Como se ha comentado se puede hacer con operaciones normales. Lo que sí pasa es que no hay una fórmula, sino un proceso o heurística; o lo que es lo mismo, se requiere un algoritmo y, por ello, para llevarlo a la práctica, un programa de cálculo numérico.

Aquí presento un algoritmo muy simple y de andar por casa. No es ni muy elegante ni muy eficiente en tiempo de cálculo, y creo que tampoco en exactitud para números grandes, por lo que luego explicaré. Pero creo que sí tiene la virtud de ser bastante inteligible por aproximarse a la definición académica de número primo.  Lo presento como simple curiosidad, experimento o material académico para quien le pudiera interesar.

La base es muy simple. Lo explico primero verbalmente. Se trata de partir de la definición de número primo. Si N es un número primo sólo será divisible entre 1 y N. El programa crea un bucle infinito donde va tratando sucesívamente números N, N+1, N+2... Y para cada número N realiza las sucesivas divisiones entre N/2, N/3,... N/N-1,  comprobando si alguna de esas divisiones es entera (no hay decimales). En cuanto detecta una sola división entera quiere decir que el número no es primo y pasa al siguiente. Si todas las divisiones con los divisores 2, 3, ... N-1 resultan con decimales (no enteras) quiere decir que el número en cuestión sólo es divisible por 1 y por N. En consecuencia es un número primo. Se imprime en pantalla y se se pasa al siguiente N+1, volviendo a repetir el cálculo. Y así va imprimiendo todos los números primos (los tres primeros 1,2 y 3 se imprimen a mano y se calcula a partir de 4).

Como ya ha dicho alguien por ahí, en realidad no hay porque calcularlos todos, pues hay hay una lista suficientemente grande de números primos calculados y si se necesitan para una aplicación basta con tomarlos de esas listas. Sólo tiene sentido calcular a partir del más grande que se haya calculado hasta ahora, y para éso hay muchos mejores algoritmos eficientes de profesionales matemáticos y programadores. Y programas expresos no en lenguaje de alto nivel que pueden usar un nº pequeño de bytes para almacenar números decimales, sino en ensamblador haciendo las operaciones directamente en sistema binario y empleando muchísimos más bytes para almacenar números que los que usan los lenguajes estándar. De forma que los cálculos sean más exactos y no se produzcan errores por redondeo u overflow.

Bueno, pues presento este pequeño divertimento académico, que ni siquiera puede llamarse aplicación. He preparado primero un diagrama de flujo -en imagen- para que se entienda mejor lo que pretendo hacer. Luego un script en pseudocódigo, para que se pueda adecuar a cada lenguaje concreto y, finalmente una implementación en BASIC256.

La variable que representa N la he llamado 'numero' y los sucesivos valores desde 2... hasta N-1 que toman los sucesivos divisores los he colocado en una variable 'divisor'.  Sin embargo se verá que, en principio, los tomo como float (o double según el lenguaje) y es por una razón. Los valores enteros como tales pueden, según el lenguaje y el tipo, oscilar entre 256 o 32768, y si se quieren calcular valores de primos muy altos no valdrán. Así que he colocado variables en doble precisión que aunque en principio estén pensados para números decimales, pueden usarse como enteros y hacer cálculos con números más grandes. De todas formas otro de los posibles defectos del algoritmo es que no sé como se comportará para números muy grandes por defectos de redondeo. Además se usa una bandera como valor booleano, que yo he llamado 'esprimo'. El valor true es 1 y el valor false es 0.

Tanto el pseudocódigo como el código BASIC256 no son nada elegantes, mucho IF y GOTO que puede despistar, y podrían resolverse con otro tipo de estructuras tipo FOR... NEXT, DO... WHILE, etc. Pero a cambio siguen fielmente el diagrama de flujo que creo que sí se entiende bastante bien. Además si se emplean otras estructuras de bucle (si alguien quiere programarlo de otra manera) habrá que tener cuidado de romper el bucle en cuanto se cumpla condición de no-primo. Tal y como yo lo he programado se parte de que el número a estudiar es en principio primo (esprimo = 1 = true) mientras no se demuestre lo contrario. Pero en cuanto se produce el cambio de bandera de 1 a 0, automáticamente se para el proceso, se incremente el valor de 'numero' (N) y no se sigue examinado. Si por ejemplo se usa un bucle for... next desde 2 hasta N-1, imagínese que se está estudiando el nº 1.600.000, haciendo sucesivas divisiones por 2, 3, 4... 1.599.599. Es una pérdida de tiempo, pues ya en la primera división por 2 se ve que el resto es 0, el número es no-primo y no hace falta seguir. Así que si se utilizan estructuras for... next o do... while habrá que prever su aborto para no perder tiempo. Por eso el método que yo he utilizado con if y goto, aunque sea poco elegante, prima la eficiencia, creo.

Por último comentar que el programa en BASIC256 lo he testado con
https://numeros.xyz/numeros-primos/
y me ha dado correcto hasta el 541 (no he seguido). Es cuestión de calcular más rato y molestarse en comprobar. También modificando el valor de inicio de la variable 'numero' que en el programa se inicializa en 4 se puede empezar a calcular a partir de valores mayores y testar con esa u otras páginas.

Bueno, pues sin más dejo el material. En el programa en BASIC256, al no hacer falta declarar variables, he sustituido por REM las mismas.



El pseudocódigo:
1. declarar numero como variable de doble precisión
2. declarar esprimo como variable booleana
3. declarar divisor como varable de doble precisión
4. imprimir 1
5. imprimir 2
6. imprimir 3
7. numero = 4
8. divisor = 2
9. esprimo = verdadero
10. si (numero / divisor) - parte_entera(numero / divisor) = 0 ir a 16
11. divisor = divisor + 1
12. si divisor < numero volver a 9
13. si esprimo = falso ir a 14.
14. imprimir numero
15. numero = numero + 1
16 volver a 8.
17. esprimo = falso
18. ir a 12.

El programa BASIC256:
Código (qbasic) [Seleccionar]
rem numero es el que se desea saber si es primo
rem esprimo es bandera  =1 es primo =0 no lo es
rem divisor sucesivos divisores de 2 hasta numero
print 1
print 2
print 3
numero = 4
etiq8: divisor = 2
etiq9: esprimo = 1
if (numero/divisor) - int(numero/divisor) = 0 then goto etiq17
divisor = divisor + 1
if divisor < numero then goto etiq9
if esprimo = 0 then goto etiq15
print numero
etiq15: numero = numero + 1
goto etiq8
etiq17: esprimo = 0
goto etiq15

AlbertoBSD

Por lo general quien busca trabajar con numeros primos, lo necesita con numeros extremandamente grandes, los programas que trabajan con variables de 32 y 64 bits se quedan MUY atras de las necesidades reales.

Ademas de ser rapidos y trabajar con numeros primos grandes se necesita cierta flexibilidad a la hora de calcularlos, he trabado de esta forma obteniendo muy buenos resultados para encontrar factores primos de numeros muy grandes utilizando la libreria libgmp para linux: ejemplo

$ ./test_factors
random number: 1283947691350704095109854943824966739
Factor 1 : 3
Factor 2 : 3
Factor 3 : 3
Factor 4 : 4177
Factor 5 : 22027
Factor 6 : 516849070416585562079175083


Saludos!
Donaciones
1Coffee1jV4gB5gaXfHgSHDz9xx9QSECVW

Usuario887

Cita de: nosoy en  8 Febrero 2021, 18:28 PM
Código (qbasic) [Seleccionar]
rem numero es el que se desea saber si es primo
rem esprimo es bandera  =1 es primo =0 no lo es
rem divisor sucesivos divisores de 2 hasta numero
print 1
print 2
print 3
numero = 4
etiq8: divisor = 2
etiq9: esprimo = 1
if (numero/divisor) - int(numero/divisor) = 0 then goto etiq17
divisor = divisor + 1
if divisor < numero then goto etiq9
if esprimo = 0 then goto etiq15
print numero
etiq15: numero = numero + 1
goto etiq8
etiq17: esprimo = 0
goto etiq15


Interesante que yo lo haya programado de la misma forma... aunque en tu programa sobra la linea 13, ¿No? No tiene sentido testear esprimo si en primer lugar segun la logica del algoritmo, la ejecucion no llegaria hasta ese punto si esprimo fuese 0, pues la unica forma de que esprimo sea 0 es que la ejecucion proviniese de la linea 17 la cual en seguida salta a la linea 15, que incrementa el contador y se devuelve al proceso inicial, pero en definitiva... yo creo que las operaciones matematicas asi como fueron imaginadas para facilitar la resolucion de problemas en el mundo "Real" no satisfacen la logica de lo que realmente significa que un numero sea primo porque, sabemos que lsa caracteristicas de un numero primo es que puede ser dividido solo entre 1 y el mismo (en terminos de cantidades naturales) pero nadie realmente sabe que significa que un numero sea primo.

Serapis

#15
Cita de: marax en 11 Febrero 2021, 12:37 PM
..no satisfacen la logica de lo que realmente significa que un numero sea primo porque, sabemos que lsa caracteristicas de un numero primo es que puede ser dividido solo entre 1 y el mismo (en terminos de cantidades naturales) pero nadie realmente sabe que significa que un numero sea primo.
Saber, sabemos lo que son, otra cosa es que no alcancemos a conocer toda su implicación y que el único modo de resolución conocido sea la fuerza bruta.
Te interesaría conocer la definición sobre lo que son problemas NP-Completos.

En cuanto al algoritmo que expone nosoy, es subóptimo, olvídalo. Incluso el diagrama lógico es subóptimo. Sabiendo que el único primo par es dos, es ridículo aumentar en 1 el número en cada iteración.

En algún hilo se abordó algoritmos óptimos para buscarlos...
Cita de: Serapis en 20 Diciembre 2017, 18:26 PM
....
... el bucle puede mejorarse toda vez que sabemos que si acaba en 5, no será primo, y también porque muchos impares son múltiplos de 3 (esto es cada 3 impares seguidos, solo 1 es múltiplo de 3):
11,13->15;  
17,19->21;
23,25->27;
29,31->33 (todos estos a la derecha deben evitarse al buscar primos)
Así de cada 20 números enteros (tras el 10) solo hace falta verificar 5-6 números

kub0x

Lo mejor es que empieces aprendiendo teoría de números, a tu ritmo. Entonces entederás los test de primalidad, pseudoprimes y proVable primes (sí con V de valencia, con la B significa lo mismo que pseudoprime).

Por ejemplo: https://en.wikipedia.org/wiki/Primality_test

En lo personal empezaría programando sieves o cribas de primos, después puedes pasar a comprender el Fermat's Little Theorem para los primos, así descartas más posibilidades. Luego ya AKS y Miller-Rabin para terminar. Hay muchos pero Miller-Rabin es el que más he utilizado, después de pasar los denominados filtros (tests con un time complexity muy eficiente).

Y por último, podrías estudiar la Conjetura de Riemann o la de Cramer https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture son interesantes y abordan el problema de la distribución de primos y el análisis de éstos.

Saludos.
Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate


Usuario887

#17
A mi lo que me parece interesante de los primos es que presenten "Patrones indeterminados." por asi llamarlos. Hice un programa que grafica en 2D la distribucion entre primos para ejemplificarlo:




Realmente, todo lo que sea verdad, siempre ha sido verdad; por esto no me gusta citar diccionarios, pero en este caso, acudo a la definicion de "Aleatorio" segun el diccionario de la RAE (DRAE):

Citaraleatorio -ria. 'Que depende del azar o no sigue una pauta definida'

Pauta:

Citar3. f. Instrumento o norma que sirve para gobernarse en la ejecución de algo.

No hace falta ser un aguila para notar que los primos se distribuyen de una forma definida. Creo que incluso podriamos "Pensar del modo contrario" (Think otherwise diria un angloparlante) y llegar a los primos a traves de los no-primos. ¿Que es realmente un numero compuesto?

Cita de: Serapis en 12 Febrero 2021, 17:15 PM
Saber, sabemos lo que son,

No. No sabemos. Sabemos que la velocidad es la distancia que se desarrolla en la unidad de algun tiempo. Esto encaja perfectamente con la definicion de division natural: Si pensamos en la division de forma imaginaria (¿De que otra forma se podria pensar?),

a/b

Significa, que es (el resultado), en terminos de a, cuando b es la unidad.

Cuestion de remplazar terminos, para deducir entonces cualquier ecuacion que haga uso de la division:

d/t

Significa, que es (la velocidad), en terminos de distancia, cuando el tiempo es la unidad.

De esta forma, podemos llevar la velocidad a una ecuacion por dos razones fundamentales:

1. Sabemos que es. (llamemosle a ese que es "Significado")

2. Existe una operacion en nuestro sistema cientifico cuyo significado, es el mismo que el que menciono en el fundamento 1.

Para el que sepa de historia, le va a sonar arrogante y muy de mal gusto que diga: Esto no lo digo yo, es natural. Pues varias veces se bastan de una justificacion trascendental los "Poetas" para predicar sus profesias; Sin embargo, ¿Existe acaso otra forma?

En el caso de los numeros primos, no sabemos, ni (1) que son, ni (2) existe una operacion siquiera minimamente cercana en terminos de lo que observamos a lo que manifiestan los numeros primos en terminos de distribucion. Es lo que intentaba decir.

Por mas que Riemann salga de la tumba a traernos una variacion del 0.00000000000000001% de diferencia entre su nuevo

Citartodo lo que sea verdad, siempre ha sido verdad;

descubrimiento y la distribucion real entre numeros primos...




Un pequeño apendice:

Una caracteristica de la velocidad es que el cuerpo en cuestion, cuando tiene velocidad, se encuentra en movimiento.
No podemos, sin embargo, cuantificar caracteristicas, solo podemos cuantificar definiciones. Lo unico que podemos hacer con caracteristicas es aproximar resultados

Serapis

Con el teorema fundamental de la aritmética, ya Euclides hace milenios, penetró en los números primos, incluso demostró que los primos son infinitos de una forma magistral... Al problema se han aplicado gente de la talla de Euler, Fermat, Gauss, Riemann Goldbach... vamos prácticamente todo matemático que ha 'pisado dicha isla' se ha visto atrapado por la fascinación que despiertan los primos, incluso Ramanuján dejo algún que otro teorema-entuerto sobre el asunto.

Como te señalaba Kub0x, puedes proceder desde las cribas (la primera de todas fue la de Eratóstenes), después de tachar todos los compuestos, los que quedan son primos, la distribución es obvia, no arroja ningún misterio. Si quieres algo más sofisticado tira por la criba de Aitkin y si lo quieres más gráfico, por la de Matiyasevich y Stechkin...
Cuando se dice que los primos son aleatorios, el término ciertamente es impreciso, aunque se entiende perfectamente lo que intenta decir ("no conocemos una función que lo resuelva"), el término adecuado es impredecible, pero incluso dentro de esa impredecibilidad, ya Gauss, demostró con bastante aproximación cuantos primos pueden hallarse en un rango dado de números.

Con la función Zeta lo que Riemann, nos dice es que los primos forman una secuencia en las 4 dimensiones, pero dada la dificultad de concebir 4 dimensiones, lo que se ha hecho desde entonces es 'sacar fotogramas' a lo que se percibe fuera de esas 4 dimensiones (que es a lo que podemos aspirar estando enclavados en un mundo de 3 dimensiones).

Tu hiciste un gráfico 2D, y yo hace 30 años hice uno en 3D y habrá miles de personas más que habrán hecho muchas cosas muy interesante de las que nadie sabe nada ¿y qué...?

...pero nada, llegas tú y dices que no sabemos lo que son, que todo el mundo es tonto por que tú lo dices. Creo que llegado a cierto punto, lo acertado es o demostrar cosas, o dejar de decir sandeces. Teoriza todo lo que quieras (preferiblemente la teoría la lleva uno adentro y solo habla o publica cuando logra demostrar que no se equivoca), mal no hace a nadie, pero no caigas en la banalidad de descalificar a todo el mundo y proponerte por encima de ellos. Todos los nombrados (y muchos más) son sobradamente meritorios, tú, al menos aún, no puedes compartarte en nada. Si tu orgullo te lo exige... entonces déjalo para cuando logres demostrar algo (si esos llegara a suceder) y entonces llamas tonto a todos los matemáticos que existen y existieron, pero hasta entonces camina con humildad. La gente puede tragar de mejor o peor grado la soberbia de un genio, pero jamás la de un necio (y en este estado está todo el mundo hasta que demuestre lo contrario).

Usuario887

Entiendo que todos los mencionados se atribuyan el merito de sus descubrimientos. La economia es una competencia; es casi inmediata la existencia del merito. En realidad, ¿Que se puede hacer? La gloria es dulce pero, en todos los casos, no todos son soberbios.

Si vamos al caso, personalmente no me convendria demostrar la definicion de primo (si la tuviese). Principalmente porque mi trabajo se esfumaria y secundariamente porque estaria deshaciendome de la oportunidad de beneficiarme de mi gran ventaja en esa gran competencia.

Afirme dos cosas, y no te imaginas con que pereza lo hice. Ahora con mas pereza aun, las convierto en preguntas:

¿La definicion de algo depende de sus caracteristicas? Discutase en un coliseo.
¿Puede obtenerse la definicion de algo a partir de sus caracteristicas? Discutase en el mismo coliseo.

Estas preguntas tendran una respuesta ahora, la tuvieron antes de que pisaramos la tierra y tal vez la tengamos nosotros luego.
Es curioso que la primera siempre difiera de la segunda y tercera.

Pero claro, yo tengo solo creencias sobre la realidad. Es que, ¿Se podria tener otra cosa? Uno nunca esta seguro de lo que cree. El mero hecho de interactuar con el entorno se nos manifiesta como una prueba de nosotros mismos. El soberbio se atribuye el entorno a si mismo, ¡Que tonto!

Citarhace 30 años hice uno en 3D

Me gustaria verlo.