miércoles, 12 de octubre de 2011

Distancia binaria entre primos


La historia se repite

En una entrada anterior “¿Alguien sabe algo de esto?” nos planteábamos si dado un primo p cualquiera, existe otro q tal que la suma de ambos sea una potencia de 2. Después de algo de reflexión y ayudas externas llegamos a la conclusión de que esta posibilidad fallaba, quizás en el número 1871.

Al revisar la entrada para integrarla en una publicación se me ocurrió usar la diferencia entre primos en lugar de la suma: dado un número primo p, ¿existe siempre un exponente k entero tal que p+2^k sea primo? Al mínimo valor posible de este exponente le llamaremos “distancia binaria entre ambos primos” o DISTBIN.

Podíamos interpretar ese número k como el lugar donde podríamos sumar 1 a la expresión binaria de p para que se convirtiera en otro número primo, el menor posible.

Por ejemplo, el número primo 61 tiene como expresión binaria 111101 y su función distbin vale 8. Esto quiere decir que en el orden 8 de su expresión binaria hay que añadir un 1 (tomamos como 0 la primera posición): 100111101, que equivale al número primo 317.

En los primeros números primos el cálculo de distbin es sencillo:

Primo P
Distancia binaria
Primo Q
2
0
3
3
1
5
5
1
7
7
2
11
11
1
13
13
2
17
17
1
19
19
2
23
23
3
31
29
1
31
31
4
47
37
2
41
41
1
43
43
2
47
47
5
79
53
3
61
59
1
61
61
8
317

Tienes los datos de q en http://oeis.org/A139758 y los de k en http://oeis.org/A094076

Como en el caso anterior de p+q=2^n, hay primos en los que el cálculo de esta distancia desborda la capacidad de una hoja de cálculo. Destacan los siguientes:

El 773

Se tiene que distbin(773)=955, con lo que el otro primo presenta 288 dígitos:

304541062856249971261043199621099634714882089299843985214622076787904646586450815702050470808812820600790778632231520880733099058287596688955562103009770419360352428123639782183462176734064176511024987296225574339802674935168589842054573862983405175400866837597008673346307143437247316741


Imagina que su expresión binaria estará formada por un 1, más de novecientos ceros y después la expresión del 773.

El 1627

Distbin: 127 q: 85070591730234615865843651857942054491

El 2131

Bloquea las herramientas que hemos usado. En  http://oeis.org/A094076. se afirma que se ha probado el 2131 para k<30000

Si deseas practicar con el tema, te ofrecemos los códigos de búsqueda que se han usado:

Basic

Definición de DISTBIN

Function distbin(a)
Dim c, p, p2, i

c = 0
If a > 2 And esprimo Then
p = 0
p2 = 1
i = 1
Do Until esprimo(p2)
i = i * 2
p2 = a + i
p = p + 1
If esprimo(p2)  Then c = p
Loop
End If
distbin = c
End Function


Wxmáxima

Imagen del cálculo de distbin(1627)




Calculadora Wiris

Imagen del cálculo de distbin(773). En ella no entra todo el resultado.



Con ellas puedes tener una idea de los algoritmos usados. Puedes usarlos para continuar las búsquedas.