[jhonny guanipa]

Le explico con ejemplos...
El \( m_3 \) con los pasos de la formula del punto medio da los siguientes residuos:

\( s_0=1 \) \( s_1=5 \), \( s_2=4 \), \( s_3 = \)(6 punto medio), \( s_4 = 2 \),  \( s_5=3 \)...(\( s_6=1 \) loque vuelve al origen y no lo tomo en cuenta).

Como ven para este tipo de Mersenne se cumple que \( s_1=n \), \( s_2=n-1 \) y \( s_3=m_p-1 \)

Para \( m_5 \) son \( 30 \) pasos: dividimos esos pasos entre 6 bloques y nos que queda igual \( s_1 \), \( s_2 \) y \( s_3 \), para este \( m_5 \) seria a saber:

\( s_1= 108 \), \( s_2= 107 \) y \( s_3= 30 \)( punto medio \( m_p-1 \)) y luego los demás pasos...esto se cumple para un numero de Mersenne.

Existen otro tipo de Mersenne (hasta ahora) que cumple que saber:
\( s_1= m_p-1 \), \( s_2= 1 \) y \( s_3= m_p-1 \),
Ambas familias cumplen en el punto medio pero NO en sus pasos \( s_1 \), \( s_2 \) y \( s_3 \) consecuentemente.

Sigo atento a los comentarios.

[jhonny guanipa]

Perdon aca, por error tome los valores de \( m_7 \) que son \(  s_1=108 \), \( s_2=107 \) y \( s_3 =126 \).

[jhonny guanipa]

[Clasificación de los primos de Mersenne en dos familias geométricas

Aqui les hago una pequeña demostracion y una tabla que saque rapidamente.

Sea \( p \) un número primo impar y \( M_p = 2^p-1 \). Definimos
\( r = 3\cdot 2^{p-1} \pmod{M_p}. \)
Notemos que \( 2^{p-1} \) es el inverso de \( 2 \) módulo \( M_p \) (pues \( 2^p\equiv1 \)), luego \( r\equiv 3/2 \) en \( \mathbb{Z}/M_p\mathbb{Z} \).

Consideramos el entero
\( t = \frac{M_p-1}{6} = \frac{2^p-2}{6} = \frac{2^{p-1}-1}{3}, \)
que es entero porque \( p \) impar implica \( 2^{p-1}\equiv1\pmod3 \). Definimos tres valores notables de la órbita de \( r \):
\( s_1 = r^{\,t},\qquad s_2 = r^{\,2t},\qquad s_3 = r^{\,3t}. \)
Obsérvese que \( s_3 = r^{(M_p-1)/2} \). El test de primalidad (conjetural) que hemos estudiado afirma:
\( M_p\text{ es primo}\;\Longleftrightarrow\; s_3 \equiv -1 \pmod{M_p}. \)

Para todos los primos de Mersenne conocidos se cumple \( s_3\equiv-1 \). Además, al calcular \( s_1 \) y \( s_2 \) se observa que siempre ocurre exactamente uno de los dos patrones siguientes:

- Familia I: \( s_2 \equiv s_1-1 \pmod{M_p} \) (y entonces \( s_3\equiv-1 \)). 
  De \( s_3\equiv-1 \) se deduce \( s_1^3\equiv-1 \), luego \( s_1 \) es una raíz sexta primitiva de la unidad (\( s_1^6\equiv1,\; s_1^3\equiv-1 \)). Se cumple la identidad \( s_1^2 - s_1 + 1 \equiv 0 \) (polinomio ciclotómico \( \Phi_6 \)).

- Familia II: \( s_2 \equiv 1 \pmod{M_p} \) (y entonces \( s_1\equiv s_3\equiv-1 \)). 
  En este caso \( s_1\equiv-1 \) y trivialmente \( s_2\equiv1 \).

La siguiente tabla muestra la clasificación para los primeros exponentes (se han abreviado los números enormes usando potencias de 2 cuando corresponde):

\(
\begin{array}{|c|c|c|c|c|}
\hline
p & s_1 & s_2 & s_3 & \text{Familia} \\ \hline
3 & 5 & 4 & 6 & I \\
5 & 26 & 25 & 30 & I \\
7 & 108 & 107 & 126 & I \\
13 & 8190 & 1 & 8190 & II \\
17 & 109166 & 109165 & 131070 & I \\
19 & 69493 & 69492 & 524286 & I \\
31 & 2^{31}-2 & 1 & 2^{31}-2 & II \\
61 & 2^{61}-2 & 1 & 2^{61}-2 & II \\
89 & \cdots & \cdots & \cdots & I \\
107 & \cdots & \cdots & \cdots & I \\
127 & 2^{127}-2 & 1 & 2^{127}-2 & II \\
521 & \cdots & \cdots & \cdots & I \\
607 & 2^{607}-2 & 1 & 2^{607}-2 & II \\
1279 & 2^{1279}-2 & 1 & 2^{1279}-2 & II \\
2203 & \cdots & \cdots & \cdots & I \\
2281 & \cdots & \cdots & \cdots & I \\
3217 & 2^{3217}-2 & 1 & 2^{3217}-2 & II \\
4253 & \cdots & \cdots & \cdots & I \\
4423 & 2^{4423}-2 & 1 & 2^{4423}-2 & II \\
9689 & \cdots & \cdots & \cdots & I \\
9941 & 2^{9941}-2 & 1 & 2^{9941}-2 & II \\
11213 & 2^{11213}-2 & 1 & 2^{11213}-2 & II \\ \hline
\end{array}
 \)

En la Familia II, \( r^t\equiv-1 \), luego \( r^{2t}\equiv1 \); el orden de \( r \) divide a \( 2t = (M_p-1)/3 \). En cambio, en la Familia I, \( r^t \) es una raíz sexta primitiva, lo que fuerza que el orden de \( r \) sea \( 6t = M_p-1 \) (consistente con que \( r \) sea una raíz primitiva, condición necesaria para la primalidad).

Esta clasificación es un hallazgo empírico basado en los primos de Mersenne conocidos. No se ha encontrado ningún contraejemplo hasta los exponentes comprobados (al menos hasta \( p=11213 \)) le dia de hoy, sin embargo he probado con exponentes mas grandes,  Queda como problema abierto:

- Demostrar que para todo primo de Mersenne ocurre exclusivamente uno de los dos patrones.
- Caracterizar aritméticamente qué exponentes producen cada familia (posiblemente en función de \( p \bmod 12 \), \( p \bmod 24 \), o del orden de \( 2 \) módulo \( p \)).
- Relacionar esta dicotomía con la existencia de raíces sextas de la unidad en el grupo multiplicativo \( \mathbb{Z}/M_p\mathbb{Z} \).

Agradezco los buenos comentarios y observaciones , estoy para aprender.

Saludos cordiales.]

[danizafa]

Si, creo que tengo algo relacionado... Y ahora entiendo tu tabla porque justamente con la forma que yo veo los números de Mersenne llegue a algo que se parece a $$s_3=r^{3t}$$. Y solo tuve que pasar la congruencia a mi notación en $$\pmod6$$.

De hecho si llamamos: $$M_p=6t(M_p)+1$$, y pasamos la congruencia al mismo idioma, sale naturalmente, partimos de:

\[
3^{\frac{M_p-1}{2}} \equiv -1 \pmod {M_p}
\]

Pero usando

\[
t(M_p)=\frac{2^{p-1}-1}{3}
\]

tenemos

\[
\frac{M_p-1}{2}=2^{p-1}-1=3t(M_p)
\]

Por lo tanto.

\[
3^{3t(M_p)} \equiv -1 \pmod{6t(M_p)+1}
\]

Pero bueno, yo no creo que sea un test de primalidad asi nomás, de hecho ya lo dijiste LL es más eficiente.

Pero de convertirse en un teorema, es mejor que un test de primalidad.

[danizafa]

Hola de nuevo.

Revisando la clasificación de las dos familias, me parece que hay una observación algebraica interesante que quizás explique por qué aparecen esos dos patrones.

Partamos de tus definiciones:

\[
t=\frac{M_p-1}{6},
\qquad
s_1=r^t,
\qquad
s_2=r^{2t},
\qquad
s_3=r^{3t}.
\]

Como

\[
s_3=s_1^3,
\]

si se cumple la condición del punto medio

\[
s_3\equiv -1 \pmod{M_p},
\]

entonces necesariamente

\[
s_1^3+1\equiv 0 \pmod{M_p}.
\]


Ahora:

\[
x^3+1=(x+1)(x^2-x+1),
\]

de modo que las soluciones posibles quedan asociadas a las dos ramas de esta factorización.


Primera posibilidad

\[
s_1\equiv -1 \pmod{M_p}.
\]

Entonces automáticamente

\[
s_2=s_1^2\equiv 1 \pmod{M_p},
\]

que coincide con la familia II.


Segunda posibilidad

\[
s_1^2-s_1+1\equiv0\pmod{M_p}.
\]

de aquí se obtiene

\[
s_1^3\equiv -1,
\quad
s_1^6\equiv1,
\]

por lo que $$s_1$$ se comporta como una raíz sexta primitiva de la unidad. Además,

\[
s_2=s_1^2\equiv s_1-1,
\]

que coincide exactamente con la familia I.


Por lo tanto, suponiendo la condición central

\[
s_3\equiv -1,
\]

las dos familias parecen surgir de manera natural de la descomposición algebraica de

\[
x^3+1.
\]

En otras palabras, la dicotomía observada experimentalmente podría no ser accidental: serían precisamente las dos ramas posibles inducidas por la factorización

\[
x^3+1=(x+1)(x^2-x+1).
\]

Y esto conecta directamente con las raíces sextas de la unidad que mencionaste.

Además, si se reescribe todo usando

\[
M_p=6t+1,
\]

la condición del punto medio toma la forma

\[
3^{3t}\equiv -1 \pmod{6t+1},
\]

y por lo tanto

\[
(3^t+1)(3^{2t}-3^t+1)\equiv0
\pmod{6t+1}.
\]

Habría que estudiar qué ocurre divisor por divisor en los factores primos de $$M_p$$, y si la estructura de órdenes multiplicativos asociada a estas dos ramas puede ayudar a entender por qué la congruencia parece distinguir a los primos de Mersenne.

No sé si esto llevará a una demostración, pero sí parece dar una explicación de la aparición de las dos familias.

[jhonny guanipa]

Muchas gracias por la observacion, y claro, al factorizar toma sentido tener las 2 familias mersenne. Impresionante, no habia visto esa parte de la factorizacion.

[danizafa]

Muchas gracias por la observacion, y claro, al factorizar toma sentido tener las 2 familias mersenne. Impresionante, no habia visto esa parte de la factorizacion.

De nada! A mi revisar tu post también me aportó algo!

Fijate de natural que sale el punto medio en aritmética $$\pmod6$$.

Lo de las familias parece ser algo más profundo que a lo que suena. Sin duda es impresionante.

En tu post inicial no hace ni sombra a lo que te referías. Yo rescataba la congruencia casi exclusivamente, pero esto de las raíces sextas y de la factorización $$x^3+1$$ sin dudas es para estudiarse.

Si encuentro cosas en común o algo en dirección a alguna restricción estructural estudiando divisores de mersennes que muestren que si M_p es compuesto no puede cumplir la congruencia, sin duda te lo haré saber!

[jhonny guanipa]

HOLA,

Siguiendo con mis estudios he notado algo que me parece muy interesante con respecto a la factorizacion, la permutacion de los numeros primos a lo cual revisando en OEIS, solo vi publicado la permuta del M3, pero mas alla de eso, noto que las 2 familias no son mas que las 2 formas que tienen los numeros primos de dividirse, entre 1 y ellos mismos, cada solucion hace referencia a un modo, pero siguiendo revisando me fui al plano buscando una figura geometrica y me quede sosprendido con el toroide donde TODOS los mersenne tienden al punto (0.25 , 1) y me acorde de la funsion Z de riemman de sus ceros no triviales, de 1/2 y dije waooo...como saben riemman expone que los primos converjen en un punto, lo mismo los mersenne el problema era halla la funsion que ubicara en el plano los mersenne, porque tengo muchos meses tratanto de hallar una funsion que ubique a los mersenne en un punto y me habia sido imposible siempre ubicados aleatoriamente en el plano mezclados con los compuestos etc, pero esto puede ser revelador, primos quedan resultado compuesto dan como resultado que todos dan (los que pude revisar) coordenadas (0.25 , Y ) dispersos alejado del 1 pero en promedio 0,5 lo que facilita un algoritmo que tengo que me da los valores y ahora es clara la diferencia, para los mersenne es 0.25 y 0,98 tendiendo a 1 a medida que el expoenente crece, mientras los compuestos se mantienen en rangos medios.
En proximos dias envio material visual de lo que he revisado en latex.
les dejo esto a la comunidad para que vayan revisando por su cuenta.

saludos

[jhonny guanipa]

Buenos días a toda la comunidad,

Continuando con mis estudios sobre los números primos he llegado a una parte interesante que me gustaría compartir con ustedes a saber:

Una criba determinista para números de la forma \( p=24k+7 \) y su aplicación a la búsqueda de exponentes de Mersenne

RESUMEN:
Se describe una criba paramétrica que genera todos los números primos de la forma \( p = 24k+7 \) (\( k \ge 0 \)) sin divisiones trial. El método se basa en cinco ecuaciones paramétricas que representan todas las factorizaciones posibles de un compuesto de esa progresión aritmética. Se implementa en C con OpenMP, obteniendo tiempos muy reducidos (menos de 17 segundos para \( k \le 990.000.000 \)). Como aplicación, se filtran aquellos \( p \) tales que \( p+1 \) es potencia de dos, identificando los exponentes de la cadena de dobles Mersenne. Se presentan resultados empíricos hasta \( p \approx 2.4\times10^{10} \).

1. INTRODUCCIÓN

Los números de Mersenne son \( M_n = 2^n - 1 \). Un exponente \( n \) da un primo de Mersenne si \( M_n \) es primo. Todo primo de Mersenne mayor que 3 cumple \( n \equiv 7 \pmod{24} \). Por tanto, los exponentes candidatos son \( n = 24k + 7 \).

2. FUNDAMENTO TEÓRICO

Sea \( p = 24k+7 \) (impar, no divisible por 3). Cualquier factor \( a \) de \( p \) debe ser coprimo con 24, luego \( a \bmod 24 \in \{1,5,7,11,13,17,19,23\} \).

Si \( p \) es compuesto, \( p = a\cdot b \) con \( a,b > 1 \).

Los residuos de \( a \) y \( b \) multiplicados deben dar \( 7 \pmod{24} \). Las únicas combinaciones son:

\( (1,7), (5,11), (7,1), (11,5), (13,19), (17,23), (19,13), (23,17) \).

Escribiendo \( a = 24k_1 + r_a \), \( b = 24k_2 + r_b \), se obtienen expresiones paramétricas para \( k \). Por ejemplo, para \( (5,11) \):

\( (24k_1+5)(24k_2+11)=24\left(24k_1k_2 + 11k_1 + 5k_2 + 2\right)+7 \).

Los valores de \( k \) que corresponden a números compuestos son aquellos que cumplen alguna de las siguientes ecuaciones (con \( k_1,k_2 \ge 0 \) excepto donde se indica):

(A) \( k = 24k_1k_2 + 11k_1 + 5k_2 + 2 \)

(B) \( k = 24k_1k_2 + 19k_1 + 13k_2 + 10 \)

(C) \( k = 24k_1k_2 + 23k_1 + 17k_2 + 16 \)

(D) \( k = 24k_1k_2 + 7k_1 + k_2 \), con \( k_1 \ge 1 \), \( k_2 \ge 0 \)

(E) \( k = 24k_1k_2 + k_1 + 7k_2 \), con \( k_2 \ge 1 \), \( k_1 \ge 0 \)

La ecuación (E) es redundante con (D) por simetría. Marcando todos los \( k \) que cumplen alguna, los restantes son aquellos para los que \( p = 24k+7 \) es primo.

3. ALGORITMO Y OPTIMIZACIONES

Se implementa una criba booleana para \( k \) desde 0 hasta un límite \( K_{\max} \). Para cada \( k_1 \) se recorre la progresión aritmética correspondiente y se marca el array. Pseudocódigo para (A):

for (k1 = 0; ; k1++) {
  start = 11*k1 + 2;
  if (start > Kmax) break;
  step = 24*k1 + 5;
  for (k = start; k <= Kmax; k += step)
    compuesto[k] = 1;
}

El algoritmo se paraleliza con OpenMP (4 hilos). Se usa un array de bytes. Tras la criba, se recorren los \( k \) no marcados, se calcula \( p = 24k+7 \) y se comprueba si \( p+1 \) es potencia de dos (operación de bits). De ser así, \( p \) es un exponente de doble Mersenne.

4. RESULTADOS EMPÍRICOS

El programa se ejecutó en un portátil Intel con 4 hilos. Los tiempos y resultados se resumen a continuación:

- \( K_{\max}=1.000.000 \) → \( p_{\max}=24.000.007 \), tiempo 0.13 s, primos encontrados 188.491
- \( K_{\max}=20.000.000 \) → \( p_{\max}=480.000.007 \), tiempo 3.05 s, primos 3.169.767
- \( K_{\max}=90.000.000 \) → \( p_{\max}=2.160.000.007 \), tiempo 1.23 s, primos 13.210.775
- \( K_{\max}=990.000.000 \) → \( p_{\max}\approx 23.760.000.007 \), tiempo 16.95 s, primos 130.020.221

En todos los casos se identificaron los exponentes de doble Mersenne conocidos:

\( 7,\;31,\;127,\;8191,\;131071,\;524287,\;2147483647 \)

correspondientes a

\( k=0,\;1,\;5,\;341,\;5461,\;21845,\;89478485 \).

5. CONCLUSIONES

Se ha desarrollado una criba al parecer determinista perfecta para la progresión \( 24k+7 \), lineal en \( K_{\max} \) y fácilmente paralelizable. Es ideal para filtrar exponentes candidatos a primos de Mersenne. La comprobación de \( p+1 \) potencia de dos detecta instantáneamente los exponentes de la cadena de dobles Mersenne. El método puede extenderse a otras clases de congruencia (por ejemplo, \( 24k+1 \), \( 24k+5 \), etc.) para cribar todos los primos.

Estas observaciones vienen de otro trabajo que he ido desarrollando que llamo el reloj de Mersenne, como mencione en artículos anteriores todos los primos de Mersenne se alinean en n6, 90 grados, posición \( (0.25,1) \) con la suma de sus estados \( 0,5 \) para cada primo. Se observo que los números primos se establecen en 5 nodos \( 15^\circ \) (50%), \( 60^\circ \) (12,5%), \( 90^\circ \) (12,5%), \( 240^\circ \) (12,5%), \( 270^\circ \) (12,5%). Esto último lo presentare en prúximos días.

Agradeciendo de antemano a los miembros del foro y administradores por el estudio e información que puedan hacer al respecto.

Saludos cordiales

Johnny Guanipa

[Luis Fuentes]

Hola

Los números de Mersenne son \( M_n = 2^n - 1 \). Un exponente \( n \) da un primo de Mersenne si \( M_n \) es primo. Todo primo de Mersenne mayor que 3 cumple \( n \equiv 7 \pmod{24} \). Por tanto, los exponentes candidatos son \( n = 24k + 7 \).

Lo que marco en rojo, no es cierto. Por ejemplo \( M_5=2^5-1=31 \) es un primo de Mersenne, pero \( 5 \) no es igual a \( 7 \) módulo \( 24 \). Cosa distinta es que quieres que \( M_n \) sea un "doble" primo de Mersenne, es decir, que \( n \) también sea primo de Mersenne.

En todos los casos se identificaron los exponentes de doble Mersenne conocidos:

\( 7,\;31,\;127,\;8191,\;131071,\;524287,\;2147483647 \)

No sé muy bien que quieres decir con esa frase. Todos esos son primos de Mersenne; pero no todos son dobles primos de Mersenne.

5. CONCLUSIONES

Se ha desarrollado una criba al parecer determinista perfecta para la progresión \( 24k+7 \), lineal en \( K_{\max} \) y fácilmente paralelizable.

No es cierto que sea lineal. Hay dos bucles anidados y se puede ver que el orden es en realidad \( O(K_{max}log(K_{max})) \). Es un "poquito" más que lineal.

Es ideal para filtrar exponentes candidatos a primos de Mersenne. La comprobación de \( p+1 \) potencia de dos detecta instantáneamente los exponentes de la cadena de dobles Mersenne. El método puede extenderse a otras clases de congruencia (por ejemplo, \( 24k+1 \), \( 24k+5 \), etc.) para cribar todos los primos.

No es demasiado viable para buscar primos de Mersenne en general, porque no deja de ser una criba que exige marcar en un array. En cuanto crece el rango de trabajo el array terminaría por colapsar la memoria.

Saludos.