lunes, 4 de noviembre de 2019

Unidos por el SOPF



Es tradición en este blog aprovechar cuestiones surgidas en Twitter. La de hoy se basa en una planteada por Juan Carlos Amez, @juankaamez, el día 28 de septiembre de 2019.

¿Podríamos probar que para cualquier valor k existe siempre al menos un valor n que verifica que: sopf(n)=sopf(n+k)?

Como la cuestión directa puede tener una respuesta complicada, abordamos antes la inversa, que dado un N debamos encontrar el K correspondiente.

Recordemos: la función SOPF(N) es la suma de los factores primos de N tomados sin repetición. Así SOPF(6)=2+3=5 y SOPF(12)=5 también, porque ambos tienen los mismos factores primos 2 y 3.

Primera cuestión: Encontrar K para un N dado

Existe una forma sencilla de evaluar la función SOPF sin necesidad de descomponer N en factores primos. Su código para Excel puede ser este:


Public Function sopf(n)
Dim f, a, e, g

a = n
f = 2 ‘Esta variable recorrerá los primos
e = 0 ‘Aquí se sumarán los factores primos
g = 0 ‘Recogerá los divisores primos
While f <= a
While a / f = a \ f ‘Se encuentra un factor
g = f: a = a / f ‘Tomamos nota en g y eliminamos ese factor
Wend
If g <> 0 Then e = e + g: g = 0 ‘Se suman factores en SOPF
If f = 2 Then f = 3 Else f = f + 2 ‘Se buscan nuevos factores
Wend
sopf = e
End Function

Con ella podemos ir descubriendo ya las coincidencias en los valores de SOPF. En la tabla podemos comprobar algunas.


Queda claro en ella que comparten valores de SOPF aquellos números que coinciden en sus factores primos sin contar repeticiones. Los tres primeros se basan en 2+3=5, los segundos en 3+7=10 y los últimos en 2+5=7.

Basta restar dos de ellos para tener una solución a la primera cuestión:

SOPF(6)=SOPF(6+6)=SOPF(6+138)
SOPF(21)=SOPF(21+42)=SOPF(21+126)

Esto resuelve la cuestión para un N dado y K desconocido: los valores posibles de K para un N dado son infinitos. Basta aumentar los exponentes de los factores primos de N y después restar.

Esto tiene una traducción a fórmula: 
Es decir, serán valores válidos de K aquellos formados por la descomposición factorial de N multiplicada a su vez por un producto similar al que restamos una unidad. Los exponentes r, s y t pueden ser nulos (salvo uno, para evitar la solución K=0)

Por ejemplo, para 12=22*3, K podría tener cualquiera de estas estructuras:

22*3*(23-1)=84, que equivaldría a

SOPF(12)=SOPF(12+84)=SOPF(96)=5

22*3*(2*3-1)=60, luego SOPF(12)=SOPF(12+60)=SOPF(72)=5

Así que la primera cuestión ya está resuelta, con la multiplicidad de soluciones de K `para cualquier N.

Segunda cuestión: Dado un valor de K, encontrar posibles valores de N

Esta cuestión es mucho más complicada, pues los valores de N no están acotados. Por ejemplo, para K=87654321, hemos encontrado un valor de N de 13761, lo que ha supuesto recorrer más de trece mil números. Efectivamente es una solución, porque

SOPF(13761)=153, ya que 13761=32*11*139, y 3+11+139=153.

y

SOPF(13761+87654321)=SOPF(87668082)=153, porque 87668082=2*39*17*131, con lo que SOPF(87668082)=2+3+17+131=153.

No parece sencillo demostrar que la conjetura planteada sea verdadera. Son muchas las coincidencias entre sumas de primos, como 29+5=31+3=34 y la herencia de los valores de SOPF que vimos en la primera cuestión, por lo que se puede confiar en que para todo K exista un N que cumpla SOPF(N)=SOPF(N+K). Pero demostrarlo es otra cuestión bien distinta.

Sí podemos presentarlo como conjetura, y esto es lo que figura en la página web

https://www.primepuzzles.net/conjectures/conj_025.htm

rotulada como conjetura 25. En ella puedes consultar algunos intentos de demostración de la misma.

Si no se sabe demostrar la conjetura, sí se puede establecer una búsqueda del mínimo valor de N para cada K. 

Esto lo tienes publicado en http://oeis.org/A065925, y ahí remiten a la conjetura 25. 

Los primeros valores de N son 5, 2, 7, 4, 114, 2, 5, 8, 13, 10, 25, 4, 5, 2, 19, 16, 85, 6, 5, 5, 209, 22, 25, 3, 493, 26, 31, 4, 20, 2, 5, 32, 7, 34, 516, 12, 33, 38, 10, 10, 99, 6, 5, 44, 57, 46, 25, 6,…

Aquí podemos comprobar la conjetura con dos herramientas. Para Excel usaremos una “atrevida” función, que encontrará N para un K dado. La llamamos así porque se basa en un bucle que puede no tener final si la conjetura es falsa, con lo que habría que detener Excel antes de que terminara el proceso. Su código es

Function dsopf(k)
Dim d, n
d = 0
n = 2
While d = 0 ‘En este while radica el peligro, ya que puede no detenerse
If sopf(n) = sopf(n + k) Then d = n
n = n + 1
Wend
dsopf = d
End Function

Se supone definida ya la función SOPF.
Esta función devuelve un 0 si no encuentra ningún valor de N. En realidad no lo devolvería, porque la ejecución no podría detenerse. Se ve que hemos confiado en la conjetura.

Con esta función es fácil reproducir la lista de valores de N publicada en OEIS:



También podemos probar con valores grandes de K, como el número de fecha de la Navidad de este año:

DSOPF(251219)=3256.

Comprobamos: SOPF(3256)=50, SOPF(251219+3256)=SOPF(254475)=50

Parece que podemos confiar en que la conjetura sea cierta. Como Excel tiene una capacidad limitada cuando trata con números grandes, traducimos la cuestión al lenguaje PARI:

sopf(n)= my(f, s=0); f=factor(n); for(i=1, matsize(f)[1], s+=f[i, 1]); s
dsopf(k)= my(d=0,n=2);while(d==0,if(sopf(n)==sopf(n+k),d=n);n+=1);d
print(dsopf(12345678910))

Puedes copiar este código y ejecutarlo en la página


Aquí tienes el resultado: 81147.



Cambiando el ejemplo 12345678910 por otro iríamos comprobando la conjetura para diversos valores.

Este número 12345678910 nos daría problemas de lentitud en Excel, pero hasta aquí sí puede con el problema:


Por si acaso, es preferible usar PARI para evitar los problemas de la coma flotante de Excel.

Esto es lo que podemos afirmar sobre la conjetura. Hay que agradecer a Juan Carlos Amez su propuesta, pues nos ha permitido estudiar un tema interesante.



No hay comentarios: