22/08/2019, 09:24:08 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a NUMERARIUS
 
 
Páginas: 1 2 [3]   Ir Abajo
  Imprimir  
Autor Tema: Criterios matemáticos. Debate. Por Víctor Luis  (Leído 1625 veces)
0 Usuarios y 1 Visitante están viendo este tema.
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.313



Ver Perfil
« Respuesta #40 : 27/07/2019, 08:23:39 am »

Buenos días, Victor Luis.

He estado mirando lo del test de Lucas-Lehmer, que es para primos de Mersenne, pero veo que antes está el test de Lucas, que es para primos en general; no me acordaba absolutamente nada de estos tests, los miré muy poco en su día cuando me hablaste de ellos.

Veo que la idea del test de Lucas tiene en común algo con una que yo te contaba un día para intentar factorizar los semiprimos; era a partir de intentar factorizar el semiprimo quitándole cifras, factorizando primero uno o varios números más pequeños. En el de Lucas, para saber si un número es primo o no, se han de conocer todos los factores de n-1 (factorizarlo completamente) siendo “n” el número a comprobar, lo cual para números grandes puede ser casi tan difícil como llegar a saber si “n” es primo.

Este método de Lucas, en detalle y según la Wiki, se trata de lo siguiente (supongo que lo conoces y mejor que yo):

Sea “n” el número del que queremos saber si es primo y sea “a” un número menor que “n”.

Sean [texx]q_{i}
 [/texx] los factores primos de “n-1”; o sea, si “n-1” fuera 12, tendríamos [texx]q_{1}=2;\, q_{2}=3
 [/texx]; simplemente representa eso, los factores primos distintos.

Entonces, si existe un “a” para el que se cumplen estas dos condiciones (no sólo una)

[texx]a^{n-1}\equiv1\,(mod\: n)
 [/texx]

y

[texx]a^{(n-1)/q}\not\equiv1\,(mod\: n)
 [/texx] (para todos los factores q)

en ese caso es primo seguro; y, si no se cumple, es compuesto.

Pongo un ejemplo:

Queremos saber si es primo [texx]n=1105
 [/texx].

Entonces, [texx]n-1=1104
 [/texx]

Los factores primos distintos de 1104 son 2,3 y 23.

Al probar la primera condición

[texx]a^{n-1}\equiv1\,(mod\: n)
 [/texx]

como 1105 es un número de Carmichael en este caso, la cumple para cualquier “a” coprimo con él, luego pasaría la primera prueba, que es la del pequeño teorema (aunque en este caso es claro que no es primo al acabar en 5, pero supongamos que no supiéramos eso).

Pero para todo “a” va a fallar la congruencia en la segunda condición [texx]a^{(n-1)/q}\not\equiv1\,(mod\: n)
 [/texx]”; esto quiere decir que también habrá que probar distintas bases “a” en el método de Lucas; sin embargo, tiene esta ventaja (la de la segunda condición) de no ser vulnerable respecto de los pseudoprimos; si “n” no es primo, no va a existir ningún “a” que cumpla esas dos condiciones, si es primo, siempre va a existir alguno; que, normalmente, se encontrará sin recorrer demasiados valores (dependiendo de lo grande que sea “n”, claro).

Cita

°) Al respecto y sobre la explicación que expusiste, indicando 'a' como una base y que el teorema se cumple, como que todo primo debe cumplir la congruencia con resto (1) para toda base 'a' ... Lo que implicaría realizar varias, muchas, en sí demasiadas operacionalizaciones como evaluaciones.


En cuanto a las bases “a” a probar, existe una forma de ver si es primo pero no añade nada práctico al test (de hecho ya usa esto que digo).

Son lo que se llaman raíces primitivas.

Si “n” es primo, todos los números menores que “n” son coprimos con “n”; ninguno tiene un primo en común, como es obvio.

Para buscar una raíz primitiva del primo “n”, debemos buscar los restos de las potencias de un número “a” dadas por [texx]a^{n-1},a^{n-2}...a^{2}
 [/texx] al ser divididas por “n”; si resulta que el conjunto de los restos es precisamente el formado por [texx](n-1),(n-2)...2
 [/texx] sin faltar ninguno, entonces “a” es una raíz primitiva módulo “n”; si falta alguno no es raíz primitiva del primo.

Por el ejemplo, el caso más sencillo de ver, con los números más pequeños, dejando el 2 aparte, es éste:

Si el primo es “n” es 5, entonces a=3 es una raíz primitiva; vamos a verlo sacando los restos

[texx]3^{5-1}\equiv1(mod\,5)
 [/texx]

[texx]3^{5-2}\equiv2(mod\,5)
 [/texx]

[texx]3^{5-3}\equiv4(mod\,5)
 [/texx]

[texx]3^{5-4}\equiv3(mod\,5)
 [/texx]

Y tenemos que el conjunto de restos es {1,2,4,3}, es decir, todos los restos posibles módulo 5 menos el cero; entonces esto quiere decir que es primo.

Precisamente es lo que hace que funcione el test de Lucas; si es primo existe al menos una raíz primitiva, y una raíz primitiva siempre va a cumplir la primera y segunda condición, puesto que si elevamos a las potencias (n-1)/q con q un divisor primo distinto de 1, tenemos que (n-1)/q siempre es distinto de (n-1), que es la potencia de “a” que deja resto 1 en la primera condición; de ahí que la segunda condición sea [texx]a^{(n-1)/q}\not\equiv1\,(mod\: n)
 [/texx], o sea, distinto de resto 1; por eso, si es raíz primitiva de un primo, nunca deja resto 1 (deja resto 1 si q=1, que es el caso del Pequeño teorema de Fermat, el de la primera condición).

El en caso de los compuestos, las raíces primitivas, si existen, son las que dejan de restos la colección de todos los coprimos (coprimos con el compuesto que se está comprobando, se entiende) menores que él, sin faltar ningún coprimo; pero los coprimos no son  todos los números menores que el compuesto, como sí pasa con un primo, son sólo los que no tienen factores en común, con lo que la diferencia dada entre las raíces primitivas de los primos y los compuestos es suficiente para distinguir a los primos a partir de éstas.

El test de Lucas-Lehmer es distinto, es para los primos de Mersenne solamente; pero creo que el de Lucas también puede resultarte interesante para ver cosas.

Saludos.
En línea

feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.313



Ver Perfil
« Respuesta #41 : 27/07/2019, 03:33:35 pm »


Hola otra vez, Víctor; he seguido leyendo y esto que dices aquí merece un comentario especial:

Cita

Pero les confronto a que lo demuestren, con algún método de primalidad, donde Fermat no nos sirve; peor aún Miller_Rabin, por no ser "métodos deterministas" ...


Eso que dices ahí no es cierto en cuanto a Fermat. No entro en Miller porque no lo conozco bien; me refiero al Pequeño Teorema de Fermat, donde existe el mito de que no detecta los pseudoprimos. Pues sí los detecta, pese a lo que hayas leído.

En Wiki, aquí, https://es.wikipedia.org/wiki/Test_de_primalidad lo califica de probabilístico debido a los números de Carmichael; pero no se puede considerar así:

Tomemos un número primo, en primer lugar, para ver una cosa. Usemos todas las bases “a” posibles hasta que lleguemos al valor del propio primo; a partir de ese momento, y por primera vez, la congruencia [texx]a^{(p-1)}\equiv1\,(mod\, p)
 [/texx] falla; debido, obviamente, a que “a” entonces no es coprimo con “p”, por ser el propio “p”.

Igualmente, por la misma razón, pasa con los pseudoprimos, pero como son compuestos, fallan cuando toman el valor de cualquiera de sus factores, que son menores que el pseudoprimo. Por tanto, al fallar cuando “a” es igual al factor más pequeño del pseudoprimo, ya sabemos que no es primo (porque eso, ya digo, en los primos sólo pasa con números tan grandes como él o mayores, no con menores).

Además, los números que se conocen de Carmichael son libres de cuadrados (los que he visto, supongo que serán todos así, no sé) y con muchos factores, con lo que están formados siempre por uno o varios primos mucho menores que el pseudoprimo.

De hecho, por esta razón, el Pequeño Teorema es perfecto para factorizar esos números. Basta poner la condición del teorema para cribar e ir desechando los que cumplan a la vez [texx]mcd(a,n)=1
 [/texx] y [texx]a^{n-1}\not\not\not\equiv1(mod\, n)
 [/texx]; si pasa eso con alguna base no son de Carmichael. Y de los que van pasando esa criba miramos el “a” que divide “n” y nos van saliendo todos los factores del pseudoprimo “n”.

Aunque ahora no tienes ordenador, te pongo un programa que he hecho con esa idea usando sólo el Pequeño Teorema:

Código:

 from sympy import*


M=[]

def f(n):
global M

for b in range (2,m):

a= b**(n-1)

if gcd (b,n) == 1 and  a % n != 1:

M=[]

return

elif gcd (b,n)!= 1 and n % b ==0:

M.append (b)

for n in range (1, 3000, 2):

m= int (sqrt(n))

if M != []:

print M

M=[]

f(n)


En el rango que lo he puesto detecta los primeros cuatro números de Carmichael y da su factorización:

Escritorio/programs$ python Fermat.py

[3, 11, 17] [5, 13, 17] [7, 13, 19] [5, 17, 29] [7, 13, 31]

No tarda mucho; de hecho, para al menos los primeros pseudoprimos, creo que será más rápido que el test de Lucas, pues los factores son muy pequeños y da enseguida con el primero; y aquí sólo se usa la primera comprobación, Fermat tal cual.

En esta lista de números de Carmichael

https://primes.utm.edu/glossary/page.php?sort=CarmichaelNumber

el número que tiene su factor más pequeño, y que es más grande respecto de los factores pequeños de los otros números, es uno que tiene al 37 (creo, no sé si he mirado bien del todo, pero creo). Pero el más grande que sale en la lista, que es 7536,1 tiene por factor más pequeño el 11, luego tiene el 13 también... o sea, que pese al tamaño, siempre parece que van a tener factores comparativamente pequeños respecto del número.

El Pequeño Teorema de Fermat es un test determinista, por tanto, probando bases hasta la raíz de “n” tarde o temprano desenmascara al pseudoprimo. Otra cosa es que, en números de Carmichael muy grandes (que aún no se conocen, parece ser) el factor más pequeño pueda estar muy lejos como para decir en un tiempo razonable que no es primo; pero esto no implica que sea probabilístico, ni mucho menos, puede que el tiempo no sea polinomial o cualquier cosa así, pero sí es determinista. Si decimos que no lo es, por las mismas, ningún test sería determinista, porque hay números cuya primalidad no se puede conocer, de puro enormes, con ningún tipo de test.

Así que eso es un mito, no te lo creas, un mito debido a la consideración de que la relación sirve sólo para coprimos, pero es que, precisamente por eso, cuando no son coprimos... no pasan el test y canta la gallina.

Saludos.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.144


Ver Perfil
« Respuesta #42 : 28/07/2019, 07:28:10 am »

Buenas Feriva ...

°°°)  Me complace aprender de las clases magistrales que nos expones ... Lo de Python no lo puedo comprobar, más que todo ponerlo a prueba y confío y agradezco el desarrollo que hiciste ... Pero algo sin duda, es que ningún método de primalidad, por más demostrado y determinista que sea, no se compara con el de Lucas Lehmer y en esto ... No podemos meter en una sola bolsa a todos los métodos de primalidad; sino, diferenciar aparte para Números de Mersenne y aparte para el resto de naturales Impares no múltiplos de (3) es decir 'nb' Naturales Base.

   •) Es absurdo determinar la primalidad de un natural de Mersenne por Factorización, por lo que descartemos ese camino al tratar sobre Primalidad en estos naturales. Ahora bien, como indicas, en nuestra actualidad, no se cuenta con métodos de primalidad que garanticen y/o aseguren la primalidad de naturales grandes ... (en mi criterio, algo vergonzoso)  Imagínate la complejidad del mejor método de primalidad en determinar la primalidad de:  n=(2^(23209)-1) un natural de más de 7300 cifras ... Y probaste determinar com "Mathematica" la primalidad de: (2^(44497)-1) el 26° primo de Mersenne de más de 10000 cifras?

•) Por más la simplificación para el método de primalidad de Fermat que se dé, aplicarlo para determinar la primalidad de los Números de Mersenne, no es una opción práctica y es que hasta cuántas bases 'a' se deben operar para el  Mp[26°] ?  ... Con la PEM realizamos "un solo" proceso operacional y realizaremos "un solo proceso operacional" para determinar la primalidad de todos los 'Mn' en darse ... Qué opinas al respecto?


PSEUDOPRIMOS DE CARMICHAEL.
----------------------------------------------------------

   Agradeciendo a Feriva por la dirección web de la información, los Naturales Compuestos denominados como 'Pseudoprimos' de Carmichael, mismos que se consideran porque hacen fallar a los métodos de primalidad expuestos, donde pasarían por primos ... Compartiendo lo de "Pseudo" pero no así por considerarse que como no hay más criterios sobre Primalidad y métodos desarrollados expuestos en la literatura.

   mc = (561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973,75361)

   Estos son los compuestos de Carmichael, de la página web, indicándose (16) de los cuales descartamos (5) por ser múltiplos de (3) y múltiplos de (5) quedando (11) de los cuales el (91%) pertenecen a PIG(13) y uno solo a PIG(7) lo que en el Conjunto VL todos estarían en PG(7) lo que resume el origen de estos naturales, aparentemente ... Pero veamos algo más sobre estos Naturales Compuestos, mal llamados 'Pseudoprimos' me refiero a los (11) válidos, donde indicaremos su valor natural, su Grupo PIG y sus divisores específicos primos, veamos:

   1729     PIG (13)     (7,13,19)
   2821     PIG(13)      (7,13,31)
   6601     PIG(13)      (7,23,41)
   8911     PIG(7)        (7,19,67)
   15841   PIG(13)      (7,31,73)
   29341   PIG(13)      (13,37,61)
   41041   PIG(13)      (7,11,13,41)
   46657   PIG(13)      (13,37,97)
   52633   PIG(13)      (7,73,103)
   63973   PIG(13)      (7,13,19,37)
   75361   PIG(13)      (11,13,17,31)


•) Me atreví intentar factorizar:  mc(75361) teniendo:  cet(240) con lo que sería sencillo el determinar 'Kf' y con éste 'Ks' con el que como ya sabemos, determinamos 'X' específico y ya tenemos factorizado al compuesto ... Pero resulta que este compuesto 'no es semiprimo', por lo que saber de 'cet' no nos es específicamente útil, ya que:

   (11) = (2•5)
   (13) = (2•2•3)
   (17) = (2•2•2)
   (31) = (5)

   De aquí que:  (2^(3)) • (3) • (5)  =  (120)  no determinan el 'cet' de 'mc' que es (240) ... Pero si, cuando consideramos que mc(75361) sus divisores son:   (143,527)   la cosa es llegar a que:  (240) = (2^(4)) (3) (5)  desde el 'cet' de sus divisores primos, para dar gusto al [EN] "Enfoque Natural" ... Donde desde el Conjunto FV y los otros, todo 'nb' compuesto se conforma como producto de sólo dos naturales divisores (P,Q) mismos que son naturales base, sean estos primos, primo y compuesto ó ambos divisores Compuestos, lo que en algo contradice a que los compuestos se comprenden por la descomposición única en factores primos.

°••) Es por esto Feriva, la importancia de tu hilo: "Factorización de Semiprimos" ... Porque conjeturo y predigo, que a partir de los semiprimos, desde su análisis estructural, comprenderemos lo que es la Distribución de los Números Primos *** Superando con todo respeto a nuestro Riemann, en lo que se refiere a su criterio de primalidad universal.

°°)  Todos los Naturales de Carmichael, son superados por la "PEN" ... Y es que acaso no se dan Pseudoprimos de Carmichael que sean compuestos semiprimos ??


Saludos Cordiales .......
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.313



Ver Perfil
« Respuesta #43 : 28/07/2019, 07:56:03 am »



°°)  Todos los Naturales de Carmichael, son superados por la "PEN" ... Y es que acaso no se dan Pseudoprimos de Carmichael que sean compuestos semiprimos ??


Saludos Cordiales .......

Hola, Víctor Luis, buenos días.

Creo que no se ha encontrado ninguno semiprimo; puedes pinchar en este enlace donde aparece una tabla de estos números con números más grandes que ésos de la lista preliminar; baja un poco en la página hasta la cuarta tabla, una que ocupa todo el ancho de la página. Ahí verás a la izquierda el número y a la derecha sus factores. Observa lo que te decía, son factores muy pequeños y aumentan en la medida que el número es grande, por eso en la tabla van formando una pirámide. Si esto es más o menos así para todos, al tener cada vez más factores y ser más pequeños, el propio test de Fermat los descartaría antes incluso que a otros que no son Carmichael (creo que pasaría eso, aunque no lo sé porque no lo he probado).

http://www.chalcedon.demon.co.uk/rgep/cartable.html

Saludos.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.144


Ver Perfil
« Respuesta #44 : 28/07/2019, 10:04:16 am »

 Buenas Feriva ...

°). Pues me llevaría más tiempo abordar la factorización de los demás Compuestos Pseudoprimos de Carmichael, ... primero para determinar su 'cet' y luego determinar su 'Kf' con éste su 'Ks' el cual nos da 'X' específico el cual nos permite factorizar al compuesto que sea.

••)  Más recordemos que estábamos en la Primalidad de Números de Mersenne, 'Mn', ... Métodos de primalidad dados a lo largo de la historia, que siendo eficientes para naturales base, no lo son para naturales Compuestos distintos a los que son 'Mn' Compuestos ... ... ... Reconozcan que analizar más allá de esto ... les afronta total incertidumbre, sobre el intento siquiera comprender algo más de lo que pudiera ser el absurdo de un criterio Estructural ... Sólo pierden menos de una decena de años ... Y acaso, esto repercute, en lograr un mejor destino?  ... ...

   ••• Sí a la CIA y al PENTÁGONO le diéramos nuestro conocimiento, ... Lo aprovecharían para eliminar a los engendros terroristas, algo bueno ... y qué después :¿eh?: ... A caso no sería mejor, que cada ser humano, decidiera la privacidad de su comunicación en que necesita realizar :¿eh?:  Cuando con la criptografía actual no se nos garantiza la seguridad de una conversación,  entre dos individuos; cuyo 'multicifrado' es protegido por las claves privadas elegidas, no solo en cantidad; sino también en cuanto a las mejores disponibles ofrecidas al usuario para una óptima seguridad informática.

•••). Facebook y la Nube ... A caso disponen de seguridad informática como ésta, para seguir en el juego de resguardar la información que "muchos" ... ... Apuestan su "fe" en que así será, por lo menos en un lapso de (6) años ?? ... Guarda tú dinero en un colchón, antes de 2025, sí es que quieras disponer de algún efectivo, sin que la moneda virtual: "libra" se apodere, de lo que en verdad tienes, ... y es que tú permitiste que la data informática, te diga, lo que tienes, te diga lo que puedes acceder y con esto, ... lo que puedas ser ... ! Te están limitando!  ... "Mira que ya iniciaron con la destrucción de la "UEU" (Unión Europea) por parte de RUSIA = (URSS + CHINA + COREA DEL NORTE)

   ***) Se ha hecho un mal abuso de la información global que es 'Internet', ... Ya no vasta que fuentes informaticas como "CNN" se den la tarea de verificar una noticia, mientras las redes sociales clandestinas contradicen la información y peor que ésto, la tesgiversan, de lo que en realidad sucede.

  °°°) Ten en cuenta que podemos filtrar, identificar, marcar, hacer seguimiento indefinido del usuario y todo lo que en más de te ocurra, ... con la implementación del "Enfoque Estructural" sobre lo que consideran y valoran hasta ahora en esto que llaman, "seguridad informática" ... Aprovechando por los rusos, sin saber lo que en verdad debe considerarse como "seguridad cifromatica" ... Algo como que un usuario, compleje su cifrado, con el simple hecho de complejar su 'Multicifrado' en tiempo real ... Ni Putin  ni Trump, podrían saber lo que Feriva y Yo estemos charlando.

 •) Cuán seguro sería y cuán desastroso sería, ... Aplicar en estos tiempos mi absurda metodología ...!

Saludos Cordiales a Todos .......
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.313



Ver Perfil
« Respuesta #45 : 28/07/2019, 02:26:03 pm »

Hola, Víctor Luis.

Cita

••• Sí a la CIA y al PENTÁGONO le diéramos nuestro conocimiento, ... Lo aprovecharían para eliminar a los engendros terroristas


Si te refieres a conocimiento matemático, si les dieran el mío... me parece que iban a aprovechar muy poco :sonrisa:

En cuanto a lo otro, no sé casi nada de criptografía, no sé decirte. Cuando oigo lo de las claves públicas y privadas y eso, sé lo que son por los primos, pero no sé exactamente cómo funcionan en la práctica.

Cita

Guarda tú dinero en un colchón, antes de 2025, sí es que quieras disponer de algún efectivo


¿Dinero?, ¿qué es eso? Creo recordar que un día tuve algo llamado así, sí, pero ahora lo mismo me da guardarlo en el banco que en el colchón :cara_de_queso:

Cita

Ni Putin ni Trump, podrían saber lo que Feriva y Yo estemos charlando.


Ni feriva tampoco, menudo eres tú cifrando con siglas y nombres raros :cara_de_queso:

Cita

°). Pues me llevaría más tiempo abordar la factorización de los demás Compuestos Pseudoprimos de Carmichael, ... primero para determinar su 'cet' y luego determinar su 'Kf' con éste su 'Ks' el cual nos da 'X' específico el cual nos permite factorizar al compuesto que sea.


No entiendo. Al ser números con muchos factores “graduados” en tamaño, que empiezan por ser bastante pequeños y, por ende, parecen ser todos libres de cuadrados, resultan especialmente sencillos de factorizar. Lo que no puedes hacer es encerrarte sólo en tus métodos, a cada tipo de números les va bien un tipo de test. Aquí no se puede quitar el 3, hay que probar, porque pueden ser múltiplos de 3. Llama al 2 y al 3 como quieras, pero por lo menos considera que existen y que son factores de muchos números, no todo son Mersennes ni semiprimos de factores grandes.

*** En cuanto a la cita del otro hilo que he traído aquí:

Cita

°) En tú criterio natural, primero, partes en considerar y validar al conjunto de naturales primos, como tal que si fueran, Números Primos, conocibles y comprensibles y por supuesto, demostrables como darles a comprender y más que todo, "convencer" sobre un criterio que desconocen ahora y pronto, aglomeraran en tratar de comprender lo que ya les hube dicho desde hace meses atrás ......

°°) Carmichael aspiró a mucho, ... Supuso que sus compuestos, eran naturales algo así místicos, que pasarían externamente como primos divisores, algo que es absolutamente cierto y con certidumby_Parcial respecto a todos los naturales Impares y todos los números de Mersenne.

•) Consideremos primalidad como factorización, ante los casos de análisis en la Factorización Estructural.

Saludos Cordiales .....


Pues esperaremos a cuando quieras dar a conocer ese criterio; nada qué decir a eso.

...

No pasan como primos divisores por lo que te dije, porque tienen factores que se delatan, tanto por el método de Fermat como por el método de conteo corriente, probando los números; es obvio, si un número es múltiplo de 3 ó de 11 ó de 13 ó de 17... o cualquier otro, como lo son los Carmichael y cualquier compuesto, pues cualquier criba (aunque pueda tardar varias vidas, eso sí) dará con esos factores.

Carmichael encuentra que hay números que cumplen esto siempre:

si [texx]n,a
 [/texx] son coprimos, entonces [texx]a^{n-1}\equiv1\,(mod\, n)
 [/texx] para todo “a” (para todo coprimo con “n”, como ya se ha dicho).

Pero cuando “a” es factor de “n”, entonces no es verdad; como ejemplo, el más sencillo, [texx]11^{561-1}\not\equiv1\,(mod\,561)
 [/texx] (puedes comporbarlo con Wolfram si puedes acceder con el teléfono; y también probar que falla con los otros dos factores de 561, que son 3 y 17).

Entonces, como falla para un número menor que de 561, esto es [texx]a<561
 [/texx], cuando lleguemos a ese “a” ya sabemos que no es primo (y “a” va a ser menor o igual que la razí de 561).

Por las mismas, si es primo, falla a partir de a=n, nunca antes, porque “n” no tiene más divisores que “n” y 1 y la congruencia sí se cumple para todo a<n al ser coprimos hasta ahí. Tambien puedes comporbarlo; por ejemplo, 127 es primo, [texx]127^{127-1}\not\equiv1\,(mod\,127)
 [/texx]; lo cual es obvio, directo, pues 127 elevado a cualquier potencia es divisible por 127 y el resto es cero, no 1.

Y cuando son compuestos es igual de obvio, pues la congruencia inicial de Fermat es ésta [texx]a^{n}\equiv a\,(mod\, n)
 [/texx] y al dividir entre “a” queda la otra; o sea [texx]a^{n}-a=ka
 [/texx] nos lleva a [texx]a^{n-1}-1=k
 [/texx]; lo que evidentemente quiere decir que, despejando, k+1 es divisible entre “a”; ahora bien, que pasa si “k” es múltiplos de “a”, pasa que entonces [texx]k=ta
 [/texx], para algún entero “t”, y en ese caso k+1 es [texx]ta+1
 [/texx], que al dividir entre “a” los sumandos nos da un entero “t”, más un número menor que uno [texx]\dfrac{1}{a}
 [/texx] por ser “a” mayor que 1; así pues, tenemos que es “t” más una parte no entera; no se cumple nunca con ningún factor que sea común con un factor de “n”; nunca, y ya se trate de un compuesto de Carmichael o de quien sea.

Saludos.


En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.144


Ver Perfil
« Respuesta #46 : 31/07/2019, 05:56:25 am »

Buenas Feriva ...

••)  Comprendo lo que me explicas con el ejemplo de (561) donde la base 'a' al ser comprimo con 'n' el resto de la congruencia es (1) y de no darse esto, se daría que 'n' es compuesto ... Pero si 'n' es primo, los naturales menores a este y mayor a (1) son coprimos con este, serían bases 'a' que con el resto (1) corroborarian su primalidad, lo que es complejo, simplemente para determinar su primalidad ... Y es que con la PEN no se realizarían tantos procesos operacionales para determinar la primalidad de naturales tan grandes como los mismísimos Números de Mersenne.

°) Es más, con la PEM, solo realizamos "un solo proceso operacional" para determinar la primalidad de todo Número de Mersenne ... Una Consulta:  cuán complejo es aplicar Fermat:  2^(Mn-1) mod Mn como único proceso operacional para un solo proceso de evaluación, en la determinación de primalidad de los 'Mn' dados, después del último 'Mp' Primo de Mersenne encontrado?   ... En sí, aplicando Fermat, con solo la base a(2)  Cuál sería el tiempo de proceso operacional?


Saludos Cordiales .......
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.313



Ver Perfil
« Respuesta #47 : 31/07/2019, 08:12:48 am »

Buenas Feriva ...

••)  Comprendo lo que me explicas con el ejemplo de (561) donde la base 'a' al ser comprimo con 'n' el resto de la congruencia es (1) y de no darse esto, se daría que 'n' es compuesto ... Pero si 'n' es primo, los naturales menores a este y mayor a (1) son coprimos con este, serían bases 'a' que con el resto (1) corroborarian su primalidad, lo que es complejo, simplemente para determinar su primalidad ... Y es que con la PEN no se realizarían tantos procesos operacionales para determinar la primalidad de naturales tan grandes como los mismísimos Números de Mersenne.

°) Es más, con la PEM, solo realizamos "un solo proceso operacional" para determinar la primalidad de todo Número de Mersenne ... Una Consulta:  cuán complejo es aplicar Fermat:  2^(Mn-1) mod Mn como único proceso operacional para un solo proceso de evaluación, en la determinación de primalidad de los 'Mn' dados, después del último 'Mp' Primo de Mersenne encontrado?   ... En sí, aplicando Fermat, con solo la base a(2)  Cuál sería el tiempo de proceso operacional?


Saludos Cordiales .......

Hola, Víctor Luis, buenos días.

Eso ya es harina de otro saco (o costal, que se dice más habitualmente). Nadie dice que el método sea rápido en general para determinar si un número es primo; yo sólo digo que si se prueban todas las bases necesarias (como mucho hasta la raíz del número) se podrá decir con toda seguridad si el número es primo o no.

Esto podría llegar a ser muy lento si existen pseudoprimos semiprimos o compuestos por pocos factores y grandes; podría tardarse mucho en descartarlos.

Como siempre, todo depende del tamaño del número y de sus factores. Porbar todas las bases para un número muy grande es imposible en un tiempo “humano”, por eso sólo se prueban algunas y, lógicamente, en ese caso no se termina el proceso y puede que no determine la primalidad; pero esto ocurre con cualquier método cuando no se prueba todo lo necesario. Por eso, el Pequeño Teorema sirve normalmente como método previo; la mayoría de los números no son primos ni pseudoprimos, con los que no son así se descartan fácilmente (normalmente enseguida fallan para alguna de las primeras bases que se prueban). Si se ve que, probadas unas cuantas bases, no falla, lo lógico es pasar a otro método más rápido.

No sé en detalle qué haces con el método que llamas la PEM, seguramente será rápido, pero según entiendo es especial para números de Mersenne.

Como te decía, la cosa depende del tipo de números y de lo que queramos llegar a determinar; no es exactamente lo mismo factorizar un número que decir si es primo o no (aunque lo primero implique lo segundo).

Para demostrar lo que digo, te voy a confiar el resultado de mis últimas investigaciones.

Tú sabes que con el método de factorización de Fermat (no el pequeño teorema, el otro) cuanto más cercan están los factores de la raíz antes se encuentran los factores; pues bien, yo he encontrado una fórmula con la que ocurre lo contrario, cuanto más lejos están, más fácil es determinarlos. Sin embargo, esto es relativo a la cantidad de cifras, si existe diferencia entre la cantidad de cifras de los factores no funciona igual. Te explico.

Esto del spoiler son preliminares

Spoiler (click para mostrar u ocultar)

Entonces, restando 1, [texx](n-1)^{2}
 [/texx] tenemos un [texx]kn
 [/texx], un múltiplo de “n”.

Por tanto, si tenemos un número compuesto por dos factores (aunque no sean primos o no lo sean los dos, y entonces cualquier compuesto cumple esto) lo podemos expresar siempre así

[texx]((p-1)^{2}-1)*((q-1)^{2}-1)=kpq=kR
 [/texx]; donde llamo R al compuesto; o sea, ese producto, por la ya dicho, tiene que ser múltiplo de “p” y de “q”, y por tanto de “pq”. También operado se ve que [texx]k=(p-2)(q-2)
 [/texx].

Haciendo [texx]q=\dfrac{R}{p}
 [/texx] y despejando (no me entretengo en explicar operaciones, créetelo o, si te interesa, ya me preguntas) obtenemos esta ecuación

[texx]-p=\dfrac{-R(-k+R+4)\pm\sqrt{R^{2}(-k+R+4)^{2}-16R^{3}}}{4R}
 [/texx]

Como ves, tenemos dos soluciones posibles debido al [texx]\pm
 [/texx]; si tomamos el signo “+” nos da un factor y si tomamos “-” el otro.

De aquí no sabemos “k”, pero sí sabemos, como decía, que es igual a [texx](p-2)(q-2)
 [/texx]; por tanto, tiene que ser un valor parecido al cuadrado de la parte entera de la raíz de R (y lo es, de hecho).

La parte entera de la raíz se denota por [texx]\lfloor\sqrt{R}\rfloor
 [/texx].

Bien, pues probando semiprimos con factores de las mismas cifras pero muy separados, resultó que en los casos observados [texx]\lfloor\sqrt{R}\rfloor^{2}
 [/texx] coincidía en la mitad de las primeras cifras (la mitad menos dos ellas exactamente) con el valor de [texx](p-2)(q-2)
 [/texx]. Ya digo, en varios casos.

Sin embargo, al tomar semiprimos con primos muy parecidos (iguales en las primeras cifras) la cantidad de cifras en las que coincidían era menor; en una cifra, no mucho, pero tampoco lo he investigado del todo, tengo que probar más.

Esto quiere decir, evidentemente, que usando esta fórmula y el argumento dicho vamos a factorizar antes semiprimos con los factores más alejados que semiprimos con factores más cercanos entre sí (si en ambos cosas los factores tienen las mismas cifras, ya digo).

Si hecha una prueba más exahustiva veo que, en efecto, esta observación no es una mera casualidad, entonces tenemos algo que puede ser útil: usando un algoritmo que vaya probando por Fermat a la vez que por éste.

En fin, que hay que compaginar siempre varios métodos para atacar la factorización. Piensa que un número compuesto por dos factores es como la sábana de una cama; si tiras mucho de un lado se sale del otro, hay que ir tirando de los dos para aproximarnos a los factores o al menos para cribar de una forma eficiente, porque es cosa de dos, no de uno.

En cuanto a saber si es primo o no, si determinar otros factores, sí es más cosa de uno, pero entre comillas. No obstante, no olvides que si se encontrara un método de factorización por acercamiento y que fuera rápido, también diría, lógicamente, si es primo o no; por lo investigar la factorización es muchísimo más interesante que la mera primalidad.

Saludos.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.144


Ver Perfil
« Respuesta #48 : 03/08/2019, 05:06:35 am »

Buenas Feriva ...

••) Disculpa que insista, pero en mi consulta me refería a que siendo:

      mp(48)=(2^(57885161)-1)   un natural primo de más de 17 millones de cifras

   Entonces con:   'np'=(mp-1)  operaremos en obtener el resto de dividir:

      3^(np)   mod mp  =  'rt'

   Te lo explico con palabras, el dividendo 3^(np)  dividimos entre (mp) tomando el resto final en 'rt'

   ••• Mi pregunta es el tiempo que con Python llegas a operar está división ... Solo está única división... Y si no fuera mucho pedir, tú criterio de en qué parte del proceso se daría la complejidad.


Saludos Cordiales y Muchas Gracias .......
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.313



Ver Perfil
« Respuesta #49 : 03/08/2019, 08:12:52 am »

Buenos días, Víctor Luis.

Voy a centrarme más en lo que planteas, no me regañes :sonrisa:

Sabiendo que mp es primo entonces sólo puede ser

[texx]3^{mp-1}\equiv1(mod\, mp)
 [/texx]

por el pequeño teorema.

Si no sabemos si es primo, el Python tarda mucho (no sé porque no ha terminado) para un número tan grande en hallar el resto sin más implementaciones tal cual; si es a eso a lo que te refieres. No obstante, más adelante te digo una cosa sobre esto.

Me he estado documentando sobre el test de Miller-Rabin; ya hace años que preguntaste cosas sobre él varias veces, una de ellas era que hasta dónde había que llegar en los valores de la potencia para terminar el test, otra cosa que preguntaste varias veces era que de qué manera estaba relacionado con la hipótesis de Riemann. Creo que Luis te contestó a algunas cosas de éstas para que pudieras crear el código en Python y, finalmente, adoptaste un código ya hecho que venía en internet y que no entendías muy bien.

Como te digo, me he documentado y, además, he observado o conjeturado una cosa acerca del test de Miller-Rabin que te mencionaré al final; supongo que esto sí te interesará.

Este test nació debido precisamente a los números de Carmichael, como sabrás mejor que yo, los cuales podrían tardar en detectarse casi infinitamente para números muy grandes mediante el pequeño Teorema de Fermat; hasta encontrar una base que no fuera un coprimo con la potencia, como te comentaba en las últimas respuestas.

En este enlace puedes ver que hay números de Carmichael con sólo tres factores bastante grandes, de cuatro o cinco cifras cada uno; como éste, por ejemplo 2199733160881 = 6037 * 12073 * 30181. El enlace lo tienes aquí y viene una lista bastante larga de lso primeros

https://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Carmichael-Zahlen

Por otro lado, en este otro enlace de Gaussianos...

https://www.gaussianos.com/los-numeros-de-carmichael/

Puedes ver que se dice que está demostrado que son libres de cuadrados (tal como yo sospechaba) y también se dice que al menos tienen tres factores, nunca son semiprimos, como también imaginaba.

En cuanto al test de Miller, hice un programa a mi modo para probarlo; estuve todo el día, porque en algunos sitios se explica mal el test o de forma incompleta; tuve que mirar varios vídeos (todos en inglés, que no me enteraba casi de nada, me enteraba más que nada por lo que se escribía en la pizarra) y varias páginas hasta que ya vi del todo cómo era.

Mi programa es algo especial, busca los números “m” contenidos en un intervalo (n,2n) tales que estos números son de la forma [texx]2n-p
 [/texx], donde “p” es primo y está contenido en (0,n); ya sabes, lo de la conjetura del Goldbach, tendremos [texx]p+m=2n[/texx].

De esta forma analizo la primalidad de ese tipo de compuestos cuando “p” y “m” son coprimos.

Uso en todo caso base 2 para el test (en el de los resultados no, ahí uso base 2 para Fermat pero al pasar a Miller uso de base "p", el primo compañero de "m" porque probé varias cosas) y, primeramente, lo hago con el test de Fermat; si el resto no es 1, no es primo y no pasa a la rutina donde analiza según el test de Miller (curiosamente, y ésta es la conjetura que te decía, se observa que los “m” compuestos coprimos con “p” tales que “p+m=2n” nunca son números de Carmichael; si esto se demostrara, se podría usar para el test de primalidad; de momento, también se puede usar, pero sin seguridad de si es cierto o no).

Siendo “y” el candidato a primo, la rutina que hago para Miller comienza así

Código:

k=0

while m % 2**k == 0:

k=k+1

b = (m)/ (2**(k-1))


Como también sabrás, aquí se está buscando la potencia de 2 tal que [texx]y-1=2^{k-1}*b
 [/texx]; es “k-1” debido a que k se inicia con el valor cero y el bucle devuelve una unidad más grane del que es; pero eso es igual.
Y “b” es un número impar con el que si el resto de [texx]2^{b}\equiv r(mod\, y) [/texx] resulta r=1 ó r=-1 entonces “y” es primo seguro (en este caso es seguro, no simplemente probable).

Ahora vuelvo a tu Mersenne; resulta que, si intentamos aplicar Miller, la potencia de 2 es 1, con lo que el impar “b” sigue siendo un número grandísimo; porque con esto no podríamos ir más deprisa; hay métodos para correr más que hallando las potencias tal cual, pero, no obstante, va a tardar porque el número es enorme. Cuando preguntas “cuánto tarda Python”, no es Python, depende de cómo se programe, porque hay muchas cosas para atajar.
Y usar Lehmer, por lo que he visto y si entiendo bien como va... me parece un método inviable para los Merseenes de hoy en día, quizá en su época serviría para algo; el número correspondiente de la secuencia para esa potencia creo que, lo mismo, no lo podría ni manejar un futuro ordenador cuántico de lo gigantesco que sería; estamos hablando de un número cuyo resultado se va  elevando al cuadrado iterativamente más de 50 millones de veces (se le va quitando 2 al resultado, pero eso poco quita). Eso no es lo que usa el GIMP, como decías o decías creer por ahí; no sé lo que usará, pero un número así es imposible de manejar y lo será durante quizá muchos siglos. Si puede que aprovechen algo del test de Lehmer, pero, vamos, muy modificado tendrá que ser.

Sigamos con Miller.
Después, el programa, si el resto de la congruencia dicha no es 1 ó -1, eleva al cuadrado y comprueba el resto módulo “y”; si es 1, no es primo, y esto con seguridad, si es -1, entonces es probablemente primo.
Acabado este último paso, supongamos que el resto no ha sido 1 ni-1. Se vuelve a elevar al cuadrado y si es 1 ó -1, entonces es primo (es como el primer paso)... y así sigue.

Según he visto en vídeos, parece ser suficiente con que el que bucle corra de 1 hasta “k”; aunque, a partir de la hipótesis de Riemann se demuestra (según he leído y creo entender) que tiene que ser algo mayor; el valor se halla con un simple logaritmo, pero ahora no sé dónde lo vi.

En este spoiler te pongo los resultados que fue arrojando para las parejas “p,m” donde el número a comprobar es “m” (parejas Goldbach o no Goldbach).

Si el número no es primo y lo detecta simplemente con Fermat, lo indica; si detecta que es primo cuando ocurre después, para la rutina de Miller, que el resto es 1 ó -1 (segunda comprobación) pone segunda. Si detecta que es primo para después, al elevar al cuadrado, con el resto -1, entonces pone pri resto -1. Lo mismo para cuando no es primo y entonces pri resto 1; pero esto no aparece nunca en la pantalla porque ya te digo que si “p” y “m” coprimos entonces “m” nunca es Carmichael (para los primeros, que es lo que yo he comprobado) 

En todas las entradas aparece el número “m” y entre corchetes los primos diferentes de los que se compone

Spoiler (click para mostrar u ocultar)

Saludos.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.144


Ver Perfil
« Respuesta #50 : 04/08/2019, 09:03:40 am »

Buenas Feriva ...

   Agradezco tu explicación, lo entiendo (el 90% para ser sincero) y si nuestro amigo El_Manco nos lo explicaba, un tanto más formalmente ... Pero cuando dices: "... lo hago con Fermat, sí el resto no es 1, no es primo ..."  (Disculpa si no lo pongo como cita, pues no me doy en copiar y pegar con el celular táctil) continuando... y como ya te lo dije, el criterio de solo considerar restos:  r(1) ó r(-1) ... no es suficiente, y todo parte de la insuficiencia de Fermat con su pequeño teorema donde:  2^(p-1) mod p = r(1)  que si bien cumplen todos los primos (naturales impares) este criterio de primalidad, también lo cumplen muchos naturales compuestos. Ahora, en mi criterio, Miller con Rabin solo hacen una generalización en base al criterio de Fermat, cuyo pequeño teorema no dice nada sobre 'primalidad' y si me dicen que sí, tendríamos que considerar primalidad el hecho de que los primos son naturales Impares ó que son de la forma (n6+1) (n6-1) ... Y es que nuestro Fermat fue más cauto en quedarse con su teorema, mientras que el dúo Miller Rabin de arriesgaron en ir un poco más, generalizando un criterio, sin antes preguntarse y saber, de dónde viene ese r(1) ó r(-1) más que todo debieron antes llegar a saber, lo que Fermat supongo ya sospechaba y es el Enfoque Estructural; pero no, levantaron el nombre de Riemann, para apoyar su metodología ... Y es que acaso no debieron antes demostrar la hipótesis de Riemann ? Y es que se basaron en ella verdad? Y si así fuera, me atrevería decir que la hipótesis de Riemann es un trabajo incompleto y no responde a la comprensión sobre la Distribución de los Números Primos.

   Te pongo un par de naturales, donde uno es primo y el otro compuesto:

      n1(2304167)            n2(1103)

•) Sobre la consulta que te hice (disculpa por lo de insistir) tengo clara la respuesta de lo complejo que es para Python el operar con semejante dividendo:  2^(mp-1) y como dices, hay maneras de operarlo con menor complejidad, como el operar desde la potencia y/o exponente en 'binario' para cualquier base 'a' que se necesite.

   * Una misión (sí decides aceptarlo...) Harías un programa para que evalúe y determine la primalidad de todos los 'Mn' Números de Mersenne dados hasta el exponente primo p(21701) que es el Mp [25°] ... No se cuántos primos se dan hasta (21701) solo que tenemos (7236) 'nb' Naturales Base según nuestro Conjunto FV.

   ¿En qué tiempo llevas a cabo esta tarea ó misión? ... empleando un solo y simple ordenador, empleando la metodología que mas te parezca ... (( lo aceptas? ))

•) Continuando con los Mersenne, el Mp [8°] = 2^(31)-1 = (2147483647) = mn  tomamos el natural de 10 cifras en la variable 'mn'. Ahora, tenemos dos divisiones:

   a)   2^(2147483646)  mod mn

   b)   2^(715827882)  mod mn

   c)   2^(35000000)  mod mn

   * Hay diferencia entre estos en cuanto a su complejidad operacional? Y con 'Complejidad Operacional' me refiero, a la dificultad que presenta en realizar la operación de división.

°) Por último, L. Lehmer evalúa con:  r(0)  Fermat con:  r(1)  Miller_Rabin Con:  r(1) r(-1)  y no sabría decir sobre los demás métodos de primalidad que se expondrán en la literatura. En el caso de la PEM evalúa con:  r(c{...})  donde 'c{...}' es el conjunto de cierto tipo de naturales, no dándose uno, dos, tres, ó más valores constantes para 'r' ... ¿Por qué? ... Porque si para mp(2^(3)-1)=(7) de da: r(a) un primer primo de Mersenne, en  mp(2^(5)-1)=(31) de dará:  r(c)  no así un r(a)  Ahora en  mp(2^(7)-1)=(127) de podrá dar:  r(b) u otro, "NUNCA" así:  r(a,c)  porque se dan como únicos y no sé repiten ... Es el criterio de la PEM el cual es "determinista" sin darse un solo fallo al comprobarlo evaluando cada 'Mn' hasta más allá de  Mp[26°]=(2^(23209)-1) empleando un computador Pentium-IV y con los pocos conocimientos que tengo en Python.


Saludos Cordiales .......
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.313



Ver Perfil
« Respuesta #51 : 04/08/2019, 11:56:11 am »


Hola, Víctor Luis.

Cita

y como ya te lo dije, el criterio de solo considerar restos: r(1) ó r(-1) ... no es suficiente, y todo parte de la insuficiencia de Fermat con su pequeño teorema donde: 2^(p-1) mod p = r(1) que si bien cumplen todos los primos (naturales impares) este criterio de primalidad, también lo cumplen muchos naturales compuestos


Fermat, sí, pero en el de Miller no me falla en ningún caso; si, haciendo las operaciones que decía, y en le paso del test que decía, da resto -1, es primo, no encuentro ningún caso en que no sea primo; si encunetras que esto falla (con un programa bien hecho) te llevas un millón de dólares por demostrar con un ejemplo que la hipótesis de Riemann es falsa :sonrisa: (vamos, es de suponer).

En caso de que en Miller ,después del primer proceso, dé resto 1, entonces es compuesto seguro, independientemente de la hipótesis de Riemann.

En cuanto a Fermat, pues qué es lo que he estado diciendo, que sí, que los pseudoprimos dan resto 1; en el caso de los Carmichael dan resto 1 para cualquier base que sea un coprimo con “n”, y, después hay pseudoiprimos parciales, que dan resto 1 en algunas bases y en otras no.

Cita

Y es que nuestro Fermat fue más cauto en quedarse con su teorema, mientras que el dúo Miller Rabin de arriesgaron en ir un poco más, generalizando un criterio, sin antes preguntarse y saber, de dónde viene ese r(1) ó r(-1) más que todo debieron antes llegar a saber, lo que Fermat supongo ya sospechaba y es el Enfoque Estructural; pero no, levantaron el nombre de Riemann, para apoyar su metodología ... Y es que acaso no debieron antes demostrar la hipótesis de Riemann ? Y es que se basaron en ella verdad? Y si así fuera, me atrevería decir que la hipótesis de Riemann es un trabajo incompleto y no responde a la comprensión sobre la Distribución de los Números Primos.


Hombre, si se pudiera demostrar estaría estupendo, pero, mientras, sirve para muchas cosas. Como ya te decía, el test sólo es probabilístico ne ese caso concreto cuando dice que un número puede ser primo si resto “-1”, en los demás pasos del test es seguro, también cuando descarta los Carmichael con resto 1; lo puedes en la Wikipedia misma, ahí te lo dice (y hasta donde yo he comprobado, que no es mucho, funciona todo).

Pero puede pasar que no lo descarte, que el test no diga nada o que diga que el resto es “-1” dentro del proceso del programa dicho. En ese caso, para asegurarlo más, se aconseja probar con más bases distintas, para ver si no hay nada contradictorio... Pero hasta ahora no ha pasado nada; ya te digo, es de suponer que un fallo demuestre negativamente, a modo de contraejemplo la hipótesis de Riemann (aunque no estoy del todo seguro, pero no veo cómo podría ser de otra manera).

La hipótesis de Riemann, aunque sea complicada, implica otros resultados que, si se demuestran, también se demuestra la Hipótesis; uno de ellos es éste, lee, que es muy corto:

https://www.cs.upc.edu/~argimiro/mypapers/newspapers/rieman4bachi.html

¿Te das cuenta? Tiene que ver con la cantidad de números libres de cuadrados dados en un intervalo desde 1 hasta “n”, libres de cuadrados como son los Carmichael, por ejemplo.

Recuerdo que, cuando empecé a pensar en la conjetura de Goldbach (al principio, hace ya ocho años o más) los números que no eran múltiplos sólo de primos distintos me daban guerra para visualizar las parejas. También recuerdo que tú mismo, al principio de hablar conmigo en el foro, me comentaste sobre algo que llamabas “múltiplos multicomunes” o algo parecido, que también te daban guerra para visualizar las secuencias y ciclos que buscabas, ¿no? Pues ahí lo tienes, no hace falta tampoco que entendamos bien la función Z de Riemann, pues a todos nos pasa igual, ciertos números “enturbian” especialmente la visión de la distribución de los primos.

Así que, la hipótesis de Riemann no es que se correponda con la distribucción de los números primos, es que es en sí la distribucción de los primos con un cierto vestido; tú puedes verla con otro disfraz... pero al final se trata de desenredar una madeja en la que “se ve que pasa esto” o “se ve que pasa la otro”, pero nadie puede demostrar por qué pasa lo que pasa.

Por otro lado me decías ayer que los números 5, 5+12, 5+12+12... etc., siguen una secuencia en sus útlimas cifras. Eso es una observación, ¿sabes demostrar que siempre va a pasar eso?, ¿no deberías demostrarlo antes de usarlo, como pasa con todo lo que usas sin demostrar? El propio Fermat no supo demostrar su pequeño teorema (no dejó prueba de ello) pero lo usó; y desués, años más tarde, llegaron otros matemáticos que lo demostraron. Y no sólo eso, dejaba sin demostrar casi todo; hasta 1995, hecho que recuerdo bien, no se demostró su llamado Último Teorema.

Así que no es precisamente Fermat un ejemplo en ese sentido, es el ejemplo de lo contrario. Es decir, para hablar con propiedad, el Pequeño toerema de Fermat, ése del resto 1, no es de Fermat, él es el autor de la conjetura, para él fue una hipótesis toda la vida.

...

Cita

Te pongo un par de naturales, donde uno es primo y el otro compuesto:

n1(2304167) n2(1103)


Y qué tengo que hacer con ellos :sonrisa:

Cita

Sobre la consulta que te hice (disculpa por lo de insistir) tengo clara la respuesta de lo complejo que es para Python el operar con semejante dividendo: 2^(mp-1) y como dices, hay maneras de operarlo con menor complejidad, como el operar desde la potencia y/o exponente en 'binario' para cualquier base 'a' que se necesite.

* Una misión (sí decides aceptarlo...) Harías un programa para que evalúe y determine la primalidad de todos los 'Mn' Números de Mersenne dados hasta el exponente primo p(21701) que es el Mp [25°] ... No se cuántos primos se dan hasta (21701) solo que tenemos (7236) 'nb' Naturales Base según nuestro Conjunto FV.

¿En qué tiempo llevas a cabo esta tarea ó misión? ... empleando un solo y simple ordenador, empleando la metodología que mas te parezca ... (( lo aceptas? ))


Pues ya te digo que tardaré eternamente, porque no sé ningún método eficaz para factorizar los Mersenne de potencias con cuatro o más números; y por lo que he visto de Lucas- Lehmer, me quedaría muy corto para esas potencias. En cuento a usar Miller, sin más cosas o trucos que haya por ahí y no conozco, tampoco podría hacerlo en poco tiempo.

Cita

°) Por último, L. Lehmer evalúa con: r(0) Fermat con: r(1) Miller_Rabin Con: r(1) r(-1) y no sabría decir sobre los demás métodos de primalidad que se expondrán en la literatura. En el caso de la PEM evalúa con: r(c{...}) donde 'c{...}' es el conjunto de cierto tipo de naturales, no dándose uno, dos, tres, ó más valores constantes para 'r' ... ¿Por qué? ... Porque si para mp(2^(3)-1)=(7) de da: r(a) un primer primo de Mersenne, en mp(2^(5)-1)=(31) de dará: r(c) no así un r(a) Ahora en mp(2^(7)-1)=(127) de podrá dar: r(b) u otro, "NUNCA" así: r(a,c) porque se dan como únicos y no sé repiten ... Es el criterio de la PEM el cual es "determinista" sin darse un solo fallo al comprobarlo evaluando cada 'Mn' hasta más allá de Mp[26°]=(2^(23209)-1) empleando un computador Pentium-IV y con los pocos conocimientos que tengo en Python.


Seguro que es así, ya imagino que no lo dices por decir; pero mientras no demuestres rigurosamente (y la demostración sea adeptada) que no pueden fallar lo de esos restos que dices, es tan hipótesis como cualquier otra; no puedes ciriticar los métodos probabilísticos de los demás si los tuyos no están demostrados; que a lo mejor se pueden demostrar, pero si no dices los restos que son ésos ni nada... pues el “no está demostrado” ya lo tenemos de antemano.

Saludos.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.144


Ver Perfil
« Respuesta #52 : 10/08/2019, 06:13:11 am »

Buenas Feriva ...


Cita
   
Así que, la hipótesis de Riemann no es que se correponda con la distribucción de los números primos, es que es en sí la distribucción de los primos con un cierto vestido; tú puedes verla con otro disfraz... pero al final se trata de desenredar una madeja en la que “se ve que pasa esto” o “se ve que pasa la otro”, pero nadie puede demostrar por qué pasa lo que pasa

•) Disculpa que te contradiga Feriva ... Lo digo con el criterio de haber leído la publicación que indicaste, eso de  (1,n) considerando a los naturales libres de cuadrados y entre estos la casi igualdad entre los considerados como: Buenos y/o Malos ... ... En fin, sobre esto que se explica y es parte del criterio de Riemman, ... No nos dice "nada" sobre "primalidad" y por tanto, dudo en mucho que explique o por lo menos nos dé a comprender sobre la Distribución de los Números Primos,  ... Supongo que la Función_Z y demás complementos de su criterio, (que desconozco) responderían a esta problemática, lo que precipitadamente pongo en duda (para mí).

°) Recién comprendo eso de "Naturales Libres de Cuadrados" pues suponía era sólo descartar ó depurar a los cuadrados de naturales, resultando que no sólo a éstos, sino también a los que sean divisibles entre estos cuadrados ... Bueno, no sé en verdad, la finalidad de esto; me refiero al aporte que harían los N. libres de cuadrados en primalidad, conocimiento previo y requisito indispensable para luego comprender sobre la distribución de los primos, es mi criterio personal.

'NB' LIBRES de CUADRADOS en el CONJUNTO FV.
----------------------------------------------------------------------------------
   Considero que ese criterio, también debe aplicarse a otras formas de agrupación como es el Conjunto FV, al menos eso me dije, curioso por saber de cómo se darían estos, donde los 'nb' son naturales Impares no múltiplos de 3, generados desde 4 sucesiones los Grupos PIG(5,7,11,13)

   Diremos que:  "nbc"= nb^(2)  es el cuadrado de un natural base, descartando éste y los que sean divisibles, para obtener al final, naturales base libres de cuadrados.

•) Supuse sería complejo el obtenerlos; pero recordemos que todos los 'nbc' se dan en PIG(13) y que contamos con la SMD(4,2) Secuencia de Múltiplos Directos, con el que generamos los múltiplos de los 'nbc' dados en el intervalo (1,n) mismos que depuramos, en ves de evaluar la divisibilidad de los 'nb' entre los 'nbc'. Veamos:

   nb(5) ... nbc(25)   con SMD(100,50)

        (25) es PIG(13)
        (125) es PIG(5)
        (175) es PIG(7)
        (275) es PIG(11)
        (325) es PIG(13)
        (425) es PIG(5) ...

   Observamos que el grupo PIG de los múltiplos se dan en una misma secuencia que se repite:  PIG (13)(5)(7)(11) ... Sucediendo esto en Todo 'nbc'. Ya con esto se nos facilita el obtener 'nb' libres de cuadrados ... Por ejemplo, en el intervalo (1,313) se tienen  (95) 'nb' libres de cuadrados, siendo (63) Primos y los restantes (32) Compuestos; pero no cualquier tipo de compuestos ... todos son "Compuestos Semiprimos" con dos únicos divisores  (P,Q) que son Primos, que junto al (1) Riemman los consideraría como BUENOS ... ¿Se aplicaría este criterio de buenos y malos al Conjunto FV?  Especulo que no... Más luego te exportare Feriva la continuación de 'nb', su correspondiente 'nbc' y los múltiplos de éste con la SMD dónde encontraremos un dato interesante.

Saludos Cordiales .......
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.313



Ver Perfil
« Respuesta #53 : 10/08/2019, 09:13:08 am »

Buenos días, Víctor Luis.

Como te dije, yo sé poco sobre la hipótesis de Riemann, tendría que estudiar mucho para comprenderla en toda su extensión; y ya pasando de los 60, que estoy más torpe de lo que he sido siempre... pues ni lo intento :cara_de_queso:

Pero algo tengo oído, y no es un enfoque “natural”, como tú puedes sospechar, sino una idea muy curiosa.

Como sabes, todo empieza con una suma, la suma [texx]\dfrac{1}{1}+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4}...
 [/texx], donde en este caso los denominadores en están elevados a s=1.

Esta serie tiene a infinito, sin embargo, existen trucos para considerar que converge a una cantidad.

No sólo con esa serie, esta suma 1+2+3+4...+n, puede no ser infinita, existe una forma de “extender” el resultado y que sea [texx]-\dfrac{1}{12}
 [/texx]; sí, un número no entero y además negativo; fíjate qué poco natural.

Para demostrarlo, se empieza por la serie de Grandi, que dice que

[texx]1-1+1-1+1-1...etc[/texx] hasta infinito, da [texx]\dfrac{1}{2}
 [/texx]; lo cual es otra no es el resultado normal, como ves, el resultado de la serie puede ser cero ó 1... pero ¡cómo va a ser un medio!

Como la suma es asociativa, podemos poner paréntesis así, con lo cual el resultado correcto

[texx]{\color{blue}S}={\color{blue}1+(-1+1)+(-1+1)...=1+0+0...}=1
  [/texx], o sea, S=1.

Pero también S=0

[texx]{\color{magenta}S=1-1+1...}=0
  [/texx]

Ahora escribimos la identidad 1-S=1-S teniendo en cuenta S=0:

[texx]1-S=1-{\color{magenta}S}=1-0=1={\color{blue}S}
  [/texx]

Entonces podemos escribir

[texx]1-{\color{magenta}S}={\color{blue}S}
  [/texx]; pues la S azul es el resultado 1;

y de ahí, despejando

[texx]1=S+S
 [/texx]

[texx]1=2S
 [/texx]

[texx]\dfrac{1}{2}=S
  [/texx].

Esto no es mentira, en el infinito existen varias verdades, digamos, y se puede elegir, se puede considerar unos axiomas u otros si eso supone alguna utilidad para algo.

En la serie que usa Riemann se considera una extensión de la serie y no su valor “normal”, que en el caso de s=1 (la potencia del denominador igualada a 1) sería infinito claramente.

A partir de ahí (y considerando más cosas) surge una relación asombrosa con los primos de la cual, ya te digo, yo no puedo hablarte mucho.

No sólo tiene que ver con números libres de cuadrados, también tiene que ver con las potencias, obviamente; en ése enlace que te puse se muestra un aspecto de la hipótesis, pero no es el único..

Fíjate en esto que podemos deducir considerando dos intervalos (0,n) y (n,2n); por ejemplo para n=16

[texx]0,{\color{magenta}1,2,3,4,5,6,7,8,9,10,11,12,13,14,15},16,{\color{red}17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,}32
 [/texx]

Cualquiera de los números rojos (excepto los que son primos y los libres de cuadrados, que lo había puesto antes y lo borré pensando en las combinaciones con repetición, que es como yo lo hacía esto y me he liado) se puede formar como producto de dos morados. Pero si tomamos todas las combinaciones, los productos, formadas con dos números morados (sin repetir) tenemos, en primer lugar, números que se repiten y no llegan a “n”; por ejemplo, 2*6=12 es lo mismo que 3*4 (siendo 12 un número rosa también) y en segundo lugar tenemos números que se “salen”, números mayores que 32, como, 6*7, 6*8... etc.

La distribución de los primos está totalmente relacionada con esos productos de dos números morados; pues si sacamos al 1 del conjunto, tenemos todos los compuestos rojos y además podemos establecer una relación de orden que nos va a decir cuáles se sitúan antes que otros en el intervalo (n,2n).

Por ejemplo, 3*6>n, es rojo, y es el menor rojo que podemos formar (y el 3 ya no pude formar otra pareja); por tanto luego viene un producto con 4, o sea, le sigue el 4*5... Evidentemente son los primeros en colocarse a la derecha de 16. Pero con “asombro” vemos que 18 no es el primero y 20 no es el segundo ni el tercero, sino el cuarto.

Además, como la parte entera de la raíz cuadrada de 32 es 5, ya sabemos que cualquier producto de 5 y otro número igual o mayor se va a “salir”; por tanto, parece que no tenemos poco material para establecer teóricamente cuál es la distribución de los primos en el intervalo (n,2n).

Pero resulta que hay cuadrados, y cubos... y más potencias; y la cosa se complica notablemente.

No es la cuestión obtener libres de cuadrados, eso es fácil, lo difícil es saber cuántos no libres de cuadrados hay y dónde se colocan dado un intervalo cualquiera en general; y lo mismo con los otros. En la Hipótesis de Riemann parece ser importante si la cantidad de factores de los libres es para o impar; pero no sé decirte ahora por qué, tiene que ver con la función Z.

Esto último que te cuento no es de la Hipótesis de Riemann (estará relacionadísimo casi seguro, pero no sé) es un análisis mío que hice hace tiempo; y creo que te hablé largo y tendido de él cuando discutimos sobre el postulado de Bertrand.

Riemann no considera “divisibilidad” ni “primalidad” (aunque siempre esté relacionada con los números queramos o no) considera cuestiones de distribución de los primos; a Riemann no le interesaba lo de saber si un número aislado era primo o no, le interesaba la distribución, la cantidad de ellos en los intervalos y su colocación, sobre eso vaticina su hipótesis. El que luego otros la empleen para los test y otras cosas, es porque se puede hacer, pero es aparte.

Saludos.
En línea

feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.313



Ver Perfil
« Respuesta #54 : 10/08/2019, 03:17:02 pm »



°) Recién comprendo eso de "Naturales Libres de Cuadrados" pues suponía era sólo descartar ó depurar a los cuadrados de naturales, resultando que no sólo a éstos, sino también a los que sean divisibles entre estos cuadrados ... Bueno, no sé en verdad, la finalidad de esto; me refiero al aporte que harían los N. libres de cuadrados en primalidad, conocimiento previo y requisito indispensable para luego comprender sobre la distribución de los primos, es mi criterio personal.


Aquí te dejo los primeros cien [texx]6n\pm1
 [/texx] compuestos libres de cuadrados, por si encuentras alguna relación con tus PIG o algo (entre corchetes aparece su factorización).

Spoiler (click para mostrar u ocultar)

Saludos.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.144


Ver Perfil
« Respuesta #55 : 11/08/2019, 06:38:17 am »

Buenas Feriva ...

   * Disculpa Amigo; pero estoy en desacuerdo, cuando dices que Riemman sin "divisibilidad" ni "primalidad" estudia la ' Distribucion de los Numeros Primos' ... Y es que acaso puedo estudiar a los Tigres de Bengala, sin antes comprender de estos? con solo saber   que son animales mamiferos y felinos?  un gatito pasaria como pseudoprimo ... Y es que en mi criterio, sin comprender ampliamente lo que es PRIMALIDAD, no se podra lograr comprender de cómo es que se distribuyen los primos, y esto no deberá ser complejo de explicar, porque se deberá enseñar en las escuelas y no restringirse a postgrados universitarios, no crees?


* Sobre tu explicacion de:  (0,n) y (n,2n) Estos son "INTERVALOS" en los cuales, y como ya analizamos tiempo atras, los naturales de (0,n) se complementan con (n,2n) para que por medio de la SUMA, se conforme ' 2n' y por medio de la RESTA, desde (2n) y (0,n) se obtiene (n,2n) y vicebersa. Entre Intervalos, considero no válido el aplicar: Multiplicacion, Division u otros ... En un producto:  m=(p*q)  el punto medioesta dado por la "raiz cuadrada" (rz) donde para  m(30) su raiz es:  rz=5,47 dándose:

   (1,2,3,4,5)
   (6,7,8,9,10,11,12,13,..., 30)

   No se si se denominara "intervalo" tambien a estos, naturales que se dan antes y despues de la raiz cuadrada, cuya cantidad no es igual o con una diferencia minima de (1) ni en una proporcion constante, ya que a mayor 'm', mayor cantidad de naturales en  (rz,m) dados despues de la raiz.


*) Los Multiplos de Cuadrados en el Conjunto FV, que te mencioné te los expongo:

   nb(5) = (25,125,175,275,325,425,...)
   nb(7) = (49,245,343,539,637,833,...)
   nb(11) = (121,605,847,1331,1573,2057,...)
   nb(13) = (169,845,1183,1859,2197,2873,...)
   nb(17) = (289,1445,2023,3179,3757,4913,...)
   nb(19) = (361,1805,2527,3971,4693,6137,...)
   nb(23) = (529,2645,3703,5819,6877,8993,...)

*) Estos 'nb' son los 'PG' Primos de Generacion del Conjunto_V cuya importancia es por hacer una primera clasificacion de 'nb' de acuerdo al Enfoque Estructural ... Me dirás que claro eso yo lo sé; qero ahora, te lo muestro, no todo, sino una parte.

   Recordaras que te dije que descubrí el origen de los divisores de los N. de Mersenne Compuestos, pues bien, tenemos 8 Grupos PG (5,7,11,13,17,19,23,25)  NO te detengas en que (25) no es primo; pero desde este se generan nb con su constante K(24) ... El asunto es que observa la exportacion de cuadrados y sus multiplos, fijate en su "digito final" (ultimo de la derecha) donde encontraras coincidencias, en si igualdades, dandose una clasificacion por asi decirlo, de 4 grupos vs los otros 4, y es que en solo 4 de estos, se daran los divisores de Mersennes Compuestos, y esto desde vuestro Enfoque Natural.


Saludos Cordiales .......
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.313



Ver Perfil
« Respuesta #56 : 11/08/2019, 04:17:36 pm »


Hola, Víctor Luis, buenas tardes.

Cita
Entre Intervalos, considero no válido el aplicar: Multiplicacion, Division u otros ... En un producto:  m=(p*q)  el punto medioesta dado por la "raiz cuadrada"


Pues las raíces uso; y algo más; porque o sí considero multiplicar números.

Lo que digo es que en el intervalo (0,n) tienes factores para elegir dos y multiplicarlos, de manera que puedes encontrar así todos los libres de cuadrados del intervalo (n.2n) y otros más (como podría ser el 4*3, para cierto “n”; que no es libre de cuadrado porque 12 no lo es, pero también se puede considerar).

Pero además, si consideramos los productos de los números por sí mismos (2*2), (3*3). etc,. es decir, los cuadrados perfectos (que supone usar combinaciones con repetición) vamos a tener con esos productos todos, todos los números que hay en (n,2n) más otros que se salen o no llegan al intervalo.

Y sí, son intervalos eso que haces tomando las raíces; en este caso basta con la parte entera de las raíces porque estamos considerando números naturales.

El por qué basta tomar el producto de sólo dos números del intervalo que digo lo demostré en su día y te lo expliqué.

Te lo recuerdo con un ejemplo:

[texx]{\color{red}0,1},(2,3,4,5,6,7,8,9,10,11,12),{\color{blue}13},(14,15,16,117,18,19,20,21,22,23,24,25),{\color{red}26}
 [/texx]

Para esta cuestión quitamos también el 1, es decir, tomo (1,n) en vez de (0,n) porque 1 multiplicado por cualquier número menor que “n” va a estar en ese intervalo, no en el siguiente.

En primer lugar, vemos que necesitamos repeticiones en los productos, como 4*4 para obtener 16, pero también vemos que ya no puede haber otra potencia perfecta de 2 en el intervalo (n, 2n), que en este caso es (13,26).

La razón de ello es que si existe una potencia de dos [texx]2^k[/texx] (o potencia de cualquier número que no sea 2) en el intervalo [texx](n,2n)
 [/texx], entonces obviamente [texx]2^{k}>n
 [/texx]; y si existiera otra potencia tendríamos [texx]n<2^{k}<2^{m}\Rightarrow2^{m}>2n[/texx]; y saldría del intervalo, no puede estar ahí (esto te lo expliqué y estuviste muy de acuerdo, ¿recuerdas?). (ahí he editado, que había puesto al revés algunos signos de desigualdad)

En este ejemplo tenemos [texx]2^{4}=16
 [/texx], y no tenemos ninguna de las otras por pequeñas o por grandes: no tenemos a [texx]2^{2}
 [/texx] ni a [texx]2^{3}
 [/texx] ni a [texx]2^{5}
 [/texx]... esto es imposible (con 2 u otro número de (n,2n).

Ahora voy a demostrar que no voy a necesitar el producto más de dos factores para obtener cualquier número de (n,2n).

Supongamos por reducción al absurdo que necesitáramos usar tres factores para el producto y no menos; sean los factores a*b*c.

Esos tres factores habrán de estar contenidos en (1,n) pues si alguno estuviera contenido en (n,2n) sería mayor que “n” y, al estar multiplicado por otros dos números, el compuesto sería mayor que 2n y no estaría en (n,2n); obvio, evidente.

Ahora supongamos, por ejemplo, que el producto de dos de ellos, (a*b), está en (n,2n); entonces al multiplicarlo por “c” el compuesto c(a*b) también sería mayor que 2n (aunque “c” valiera 2, que es lo menos que puede valer).

En resumidas cuentas, si [texx]abc\in(n,2n)
 [/texx], ni “ab”, ni “bc”, ni “ac” pueden estar en (2,n) y, por tanto, están en (1,n).

En conclusión, tendremos siempre dos factores, que podrán ser varios asociando de distintas maneras y dar un mismo número como producto: a(bc) ó b(ac) etc.

Para más de tres factores la demostración de la imposibilidad es análoga (e igualmente obvia). Es decir, en todo caso podremos dejarlos en dos factores asociando de manera similar (abc)*d... o lo que sea.

Así que, como ves, con sólo dos factores tendremos todos los compuestos de (n,2n).

Y queda demostrado (distinto es que hayas entendido o no la demostración; si tienes dudas, lo discutimos o le pedimos a un matemático que lo explique él de forma más rigurosa).

Ahora volvamos al ejemplo que teníamos, lo pego otra vez, para hacer la cuenta a modo de “demostración” empírica también.

[texx]{\color{red}0,1},(2,3,4,5,6,7,8,9,10,11,12),{\color{blue}13},(14,15,16,17,18,19,20,21,22,23,24,25),{\color{red}26}
 [/texx]

Para ver cuáles entran, cuáles no llegan y cuáles se salen, tenemos que considerar la raíz de “n” y de “2n”; un poco más complicado que cuando se busca por tentativa la primalidad de un número.

La parte entera de la raíz de 13 es 3, esto quiere decir que si formamos productos con (2,3) todos se quedan en (1,n), son menores (y en este caso particular sólo tenemos tres productos de dos números, que dan 4,6 ó 9, que ya se ve que no pasan de 13).

Pero vemos que en este caso 3*4=12 tampoco entra; luego no basta con la raíz, también hay que probar a ver desde cuál entran.

Seguidamente vemos que la raíz de 26 (siempre haciendo referencia a la parte entera) es 5. Por tanto, salvo 5 cuadrado, todos los productos que podemos formar con éstos (5,6,7,8,9,10,12) no los consideramos porque son mayores que 2*n=26. Con esto nos quitamos unas cuantas combinaciones de encima.

Entonces hay que mirar estos (5,6,7,8,9,10,12) con (2,3,4).

Vemos que sirve 4*4.

El 5 sirve con el 3 y el 4, son dos productos que hacen ya 4 productos váildos (con el 5*5 y el 4*4 que teníamos).

El 6 sirve con el 3,4, hacen dos más y van 6.

El 7 sirve con el 2 y el 3, hacen dos más y van 8.

El 8 sirve con el 2 y el 3, otros dos que hacen 10

El 9 sólo vale con el 2, una más, hacen 9

El 10 también sólo con el dos, hacen 10

Lo mismo para el 11, hacen 11

Lo mismo para el 12, hacen 12.

Y ya hemos terminado.

12 es la cantidad de números que hay en el intervalo (13,26); lo calculas así, 26-13-1; o los cuentas directamente.

Ahí tienes todos los compuestos de (n,2n) tomando el producto de sólo dos números de (1,n); hay productos repetidos, si no, no cabrían los primos (al cantidad de primos es la cantidad de repeticiones, como también te dije al explicarte cómo contaba los primos con el método de inclusión-exclusión; el auténtico método feriva, que es muy pesado y largo :cara_de_queso:).

Pero la cuestión es que no falta ningún compuesto, lo de contar los primos es aparte.

Y cómo se colocan estos compuestos en el intervalo (n,2n); pues, evidentemente, de izquierda a derecha empezando por los productos más pequeños; donde quede hueco, ahí están los primos (“donde estén los buitres ahí estará el cuerpo”, que decía una frase bíblica).

Y ésta es la distribución de los primos tal cual; tú puedes usar nombres como los PIG, artificios; o números complejos o extensiones de series, como Reiamann... pero ¿qué es la distribución de los primos? Esto, y no hay más, lo otro (lo tuyo o cualquier otra cosa) no puede ser más que esto mismo con distintos vestidos; porque los primos tienen un secreto que viene a ser como el de la Esfinge del cuento de Wilde; distinta es la cuestión el tiempo que lleven los cálculos y las ambiciones que tengamos.

Mira, hablando de esto, el otro día me preguntas sobre calcular el resto de un Mersenne; pues fíjate: le doy esta cuenta al Python, usando base 2, la más pequeña, [texx]2^{2^{500}-1}+1
 [/texx] (da igual que no sea primo) y me da error de memoria; sin intentar hallar ningún resto, sin ser primo... sólo intentado sumar 1 al número. Esto te demuestra que el “misterio” no está en sí en los primos, está en que hay cálculos que a los que no llegan las máquinas, aunque sea una suma.

Saludos.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.144


Ver Perfil
« Respuesta #57 : 16/08/2019, 05:35:48 am »

Buenas Feriva ...

°) Lo último que escribí, no se publicó, por una mala señal del Internet que se dió en ese momento y pues que le vamos a hacer ... Y es que me sorprendió tú razonamiento demostrativo, que me dije ... ¿Cómo no se me ocurrió llegar a eso que lo veo simple e irrefutable? ... Ahí está el detalle, me considero insuficiente en hacer una demostración matemática desde el Enfoque Natural, pero como te dije, en eso que denomino Conjunto_V con 8 Grupos PG (5,7,11,13,17,19,23,25) en solo 4 de estos, se dan los Divisores (P,Q) de los Mersenne Compuestos,... Estructuralmente se identifican éstos 4 Grupos PG y no se si casualmente, se identifican por los dígitos finales de 'nbc' que son el cuadrado de 'nb' y de los múltiplos de estos 'nbc' ... Observación que la pueden determinar desde su criterio natural.

°) Una cosa que dijiste, es que nuestro Python no llega a operar: 
      2^(2^(500)-1) ...

   Fíjate que:  2^(500)-1  es un natural de aproximadamente unos  173 cifras, exponente de una potencia en base 2 que es grandísima ... Mira que el:  Mp[51]= 2^(82589933)-1  natural de más de 28 millones de cifras, cuyo exponente es de apenas 8 cifras ... No crees que es mucho trabajito para nuestro Python ?


SIGUIENDO los PASOS de MARÍN MERSENNE.

•) Se nos ocurre analizar las potencias en base 2 con exponentes: (a) y (b) Siendo 'a' naturales PARES y 'b' naturales IMPARES, conformando naturales con:  (+1) y (-1) para cada exponente, encontrando que:  2^(a)-1  y  2^(b)+1  "siempre" serán naturales compuestos múltiplos de (3)

•) Ahora con:  2^(a)+1 se dan naturales impares pertenecientes al Grupo PIG(5) recordando que los exponentes 'a' son naturales pares, resultando que el 50% serán compuestos múltiplos de (5)

•) Nos queda:  2^(b)-1  naturales impares que pertenecen al Grupo PIG(7) mismos que ninguno será múltiplo de (3) ni de (5) sucediendo que al considerar exponentes primos, se conforman naturales Primos, al menos esto se observa en los primeros 4 primeros conformados, secuencialmente dados, algo difícil de ignorar,...  lo que dió lugar a los 'Mn' Números de Mersenne.

•) ¿Por qué sería el considerar exponentes primos?  ... Simple, exponente b(9) de la forma:  2^(b)-1 tenemos que:  m=2^(9)-1=(511) el exponente b(9) es divisible entre (3) de donde tenemos: P=2^(3)-1=7 divisor específico del compuesto (511) y así sucede con todos los exponentes compuestos ... De ahí que empíricamente consideraremos exponentes primos ... Razonamiento que supongo siguió M. Mersenne.


Saludos Cordiales .......
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.313



Ver Perfil
« Respuesta #58 : 16/08/2019, 07:13:27 am »


Buenos días, Víctor Luis.

Cita

Una cosa que dijiste, es que nuestro Python no llega a operar: 2^(2^(500)-1) ...

Fíjate que: 2^(500)-1 es un natural de aproximadamente unos 173 cifras, exponente de una potencia en base 2 que es grandísima ... Mira que el: Mp[51]= 2^(82589933)-1 natural de más de 28 millones de cifras, cuyo exponente es de apenas 8 cifras ... No crees que es mucho trabajito para nuestro Python ?


Sí, es una barbaridad. La verdad es que, para ser sincero, no tengo ni idea de cómo han podido encontrar que esos números son primos. Sé que los del GIMPs usan los ordenadores de miles de particulares que se descargan un programa libre, a los cuales prometen un premio si su ordenador encuentra un primo de no sé cuántas cifras (una cantidad brutal). Aun así, esos números son tan grandes que no sé cómo pueden, ni tardando tantos años como tardan en encontrarlos, que son muchos bastantes años, no los encuentran así como así.

En cuanto a que la potencia sea un primo si es primo, se demuestra usando el binomio de Newton; también se demuestra que cuando la base no es 2, nunca es primo, es decir, una cosa así [texx]a^{n}-1
 [/texx] con [texx]a\neq2
 [/texx] nunca es primo; cosa que, por cierto, yo observé hace un tiempo (creo que en mi hilo de las “memorias sobre Goldbach”, no sé ahora seguro) y fue Sqrmatrix quién demostró que sí, que eso pasaba; después también dio una demostración más sencilla Luis.

Lo primero que se observa para ver eso que dices (lo de que la potencia es un primo) es que, si suponemos que es compuesta la potencia (supongamos “n=ab” con dos números distintos de 1, y así ya es un compuesto) se da la igualdad siguiente:

[texx]2^{ab}-1={\color{blue}(2^{a}-1)}\cdot{\color{magenta}\left(1+2^{a}+2^{2a}+...+2^{ab-a)}\right)}
 [/texx]

Se llega a esta igualdad, ya te digo, a través del binomio, pero tampoco te hace falta analizar cómo se llega; multiplicando por la distributiva puedes ver que la igualdad es cierta:

al multiplicar, primeramente, [texx]2^{a}
 [/texx] por el paréntesis grande, tenemos

[texx]2^{a}+2^{a+a}+2^{2a+a}...+2^{ab-a+a}
 [/texx]; o sea: [texx]2^{a}+2^{2a}+2^{3a}...+2^{ab}
 [/texx]

y al multiplicar por -1, sumamos a eso esto

[texx]-1-2^{a}-2^{2a}-2^{3a}...
 [/texx]

con lo que se cancelan positivos con negativos; menos el “-1” del principio, que no tiene compañero positivo; y el [texx]2^{ab}
 [/texx] del final, que no tiene compañero negativo.

Por tanto, ya está demostrado que si la potencia es compuesta, al darse siempre esa igualdad en general, tendremos que el número de esa forma es compuesto, pues es producto de los factores “azul” y “magenta”, que ambos son distintos de 1

[texx]{\color{blue}(2^{a}-1)}\cdot{\color{magenta}\left(1+2^{a}+2^{2a}+...+2^{ab-a)}\right)}
 [/texx] es lo mismo, como queda demostrado, que [texx]2^{ab}-1
 [/texx].

Y a partir de ahí, ya, pues la potencia tiene que ser un primo.

...

En cuanto a lo de las terminaciones de los números se saben algunas cosas curiosas, como la de los números cíclicos, relacionados con los primos; mira este vídeo

https://www.youtube.com/watch?v=QuxhYXVCz5w

Saludos.
En línea

Páginas: 1 2 [3]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!