Hoy he preguntado una pregunta en codegolf.se sobre una secuencia bastante elemental. La secuencia se define como una función $f : \mathbb {N} \setminus\ {1\} \mapsto \mathbb {N} \setminus \{1\}$ donde $f(n)$ es el número más pequeño $m$ de tal manera que se satisfagan las siguientes propiedades:
-
$ \gcd (m,n) = 1$
-
$ \nexists x < n:f(x) = m$
-
$ \left |n-m \right | > 1$
El primer par de términos en esta secuencia son
$$ 5,7,9,2,11,3,13,4,17,6,19,8,23,22,21,10,25,12,27,16,15,14$$
Junto con el desafío de escribir el código para calcular la secuencia, también añadí un desafío extra para probar que $f$ era su propio inverso.
Los comentaristas verificaron que así fue para los primeros millones de valores de la secuencia, pero nadie ha podido probar que así sea hasta ahora. Busqué literatura, pero como inventé la secuencia y no tiene ninguna entrada de OEIS no llegué muy lejos.
Lo que he probado hasta ahora es que no puede haber bucles de tamaño $3$ , (es decir ) $f \circ f \circ f(x) \neq x$ ). Para probar esto asumamos que tenemos $3$ valores $a$ , $b$ y $c$ de tal manera que $a < b < c$ . Para tener un bucle 3 necesitamos cualquiera de los dos:
\begin {ecuación}f(a) = b, f(b) = c, f(c) = a \end {ecuación}
o
\begin {ecuación}f(a) = c, f(c) = b, f(b) = a \end {ecuación}
El primero no puede ser el caso porque para $f(b)$ , $a$ debe satisfacen todos los requisitos, porque $f(a)=c$ son coprimas y difieren en más de 1 y porque $f(b)=a$ sabemos que $a$ no puede haber aparecido ya en la secuencia. Así, $f(b)=a$ contradiciendo nuestra declaración anterior. El mismo razonamiento puede aplicarse al otro caso.
Creo que este razonamiento puede ser extensible a bucles más grandes, pero no estoy muy seguro de que este sea el caso, e incluso si probamos que los bucles de tamaño más grande que $2$ son imposibles, todavía tenemos que probar que cada número hace un bucle para obtener el resultado que queremos.
