Este es un desafío de código de golf que pensé con una inclinación matemática. El desafío es escribir el código más corto posible de modo que sea una pregunta abierta si el código termina o no. Un ejemplo de lo que quiero decir podría ser el siguiente fragmento de código de Python, adaptado de una respuesta a esta pregunta cs stackexchange.
def is_perfect(n):
return sum(i for i in range(1, n) if n % i == 0) == n
n = 3
while not is_perfect(n):
n = n + 2
Los matemáticos conjeturan que no hay números perfectos impares, pero nunca se ha probado, por lo que nadie sabe si este código terminará alguna vez. ¿Puedes encontrar otras piezas de código (tal vez depender de otros problemas abiertos como la conjetura de Collatz o la conjetura de primos gemelos) que son más cortos, pero para los cuales se desconoce si terminan o no?
Editar: Algunas personas han planteado una buena regla adicional: las soluciones a la pregunta deben ser deterministas. Aunque podría ser aún más interesante si pudiera encontrar soluciones más cortas utilizando el no determinismo. En este caso, la regla sería encontrar un fragmento para el cual se desconozca la probabilidad de terminación.
n=3
while sum(k*(n%k<1)for k in range(1,n))-n:n+=2
.Respuestas:
Jalea , 7 bytes
Pruébalo en línea!
Antecedentes
Esto terminará una vez que encuentre una cuarta solución al problema de Brocard , es decir, una solución n! + 1 = m² con (n, m) ≠ (4, 5), (5, 11), (7, 71) sobre los enteros positivos. La implementación no utiliza aritmética de coma flotante, por lo que solo terminará si encuentra una cuarta solución o si n! ya no se puede representar en la memoria.
El problema de Brocard fue utilizado por primera vez en esta respuesta por @xnor.
Cómo funciona
fuente
Jalea ,
119 bytesEsto terminará una vez que se encuentre el sexto Fermat Prime .
Pruébalo en línea!
Cómo funciona
fuente
Pyth, 10 bytes
Utiliza la conjetura para la que todos los números de Fermat
2^(2^n)+1
son compuestosn>4
.fuente
Python, 36 bytes
Utiliza el problema de Brocard :
Calcula factores sucesivos y comprueba si son cuadrados y tienen
k>7
. ¡Gracias a Dennis por 2 bytes!Esto supone que Python continúa teniendo una aritmética precisa para números arbitrariamente grandes. En la implementación real, termina.
fuente
-~n**.5
No funcionaría en lugar de(n+1)**.5
?~
, por lo que eso solo generaría un TypeError por tratar de negar un flotador a nivel de bits.Perl,
5038363433 bytesExplicación: 196 es un posible número de Lychrel , un número que no forma un palíndromo al agregar repetidamente su reverso. El ciclo continúa hasta que $ n sea igual a su reverso, que aún se desconoce para el valor inicial 196.
Que no es válido.
entonces ninguno de los números en esta secuencia es válido.
Editar: Golfed hacia abajo utilizando un bucle hasta en lugar de un bucle for (de alguna manera). Además, tenía menos bytes de lo que pensaba (probablemente debería mirar mi bytecount con más cuidado en el futuro).
Editar: se ha sustituido
$n
con$_
para guardar 2 bytes para el argumento implícito enreverse
. Creo que esto es tan complejo como va a ser esta implementación.Editar: estaba equivocado. En lugar de utilizar
until($%=reverse)==$_
puedo ir mientras que la diferencia no es cero (es decir, verdadera):while($%=reverse)-$_
.fuente
MATL, 11 bytes
Termina si la conjetura de Goldbach es falsa. Es decir, el programa se detiene si encuentra un número par mayor que
2
ese que no puede expresarse como la suma de dos primos.fuente
05AB1E , 8 bytes
Terminará cuando se encuentre el sexto Fermat prime .
Explicación
fuente
Python,
3028 bytesEste programa se detendrá si y solo si hay un número entero n mayor que 1, de modo que 2 ^ (n-1) -1 sea divisible por n ^ 3. Que yo sepa, no se sabe si existe algún número con esta propiedad (si un número que satisface esta propiedad es primo, se llama Wieferich primo de orden 3 a la base 2, y está abierto si existe dicho primo).
fuente
(n-1)
con~-n
Haskell, 47 bytes
Buscando el primer número cuasiperfecto , que es un número
n
cuya suma de divisores es2*n+1
. En lugar de agregar 1, excluyo 1 de la lista de divisores.fuente
Cerebro-Flak,
212208204 bytesEste programa utiliza un algoritmo de multiplicación escrito por MegaTom y un corrector no cuadrado escrito por 1000000000
Pruébalo en línea
Este programa comienza en 8 y prueba cada número para ver si n! +1 es un número cuadrado. Sale cuando encuentra uno. Esto se conoce como el problema de Brocard y es un problema abierto en matemáticas.
fuente
Brachylog (v2), 3 bytes en la codificación de Brachylog
Pruébalo en línea! (expirará sin hacer nada visible, por razones obvias)
Programa completo; si se ejecuta sin entrada, busca el primer Smarandache prime y genera resultados
true.
si encuentra uno. Es una pregunta abierta sobre si existen primos de Smarandache. (Tenga en cuenta que el algoritmo de prueba principal de Brachylog, aunque funciona en teoría en números arbitrariamente grandes, tiende a ejecutarse lentamente en ellos; por lo tanto, si está interesado en encontrar los primos de Smarandache, le recomiendo usar un lenguaje diferente).Explicación
Brachylog opera en los dígitos decimales de un número cada vez que intenta tratarlo como una lista, por lo que "rango" seguido de "concatenar" es una forma muy concisa de generar la secuencia de números Smarandache (y luego lo filtramos por primordial; Brachylog's El comportamiento predeterminado del programa completo forzará el primer elemento del generador resultante). El rango tiene un cero inicial, pero afortunadamente, con este patrón de flujo, Brachylog elimina el cero en lugar de fallar.
Aquí hay un ejemplo que encuentra el primer número de Smarandache que es igual a 6 (mod 11), como una demostración de un programa similar que finaliza en 60 segundos en lugar de tener un estado de detención desconocido:
Pruébalo en línea!
Esto se imprimiría
true.
como un programa completo, pero agregué elZ
argumento de la línea de comando para imprimir realmente el número en cuestión, dando una mejor demostración de que este enfoque general funciona.fuente
Python 2, 88 bytes
Este código terminará si 10223 es un número de Sierpiński. 10223 es actualmente el candidato más pequeño que puede o no ser un número de Sierpiński, a partir de diciembre de 2013.
Un número de Sierpiński es un número
k
en el que todos los números de la forma(k * 2^n) + 1
son compuestos.fuente
10223*2^31172165 + 1
se descubrió la prima . Desde entonces,21181
ha sido el número más pequeño para el que no se sabe si es Sierpiński o no.Pyth, 16 bytes
Devuelve el primer valor para el que no se cumple la conjetura de Collatz. Como se desconoce si la conjetura se cumple para todos los números, se desconoce si este código terminará.
fuente
En realidad , 16 bytes
Pruébalo en línea!
Este código termina si hay algún número compuesto
n
tal que setotient(n)
dividen-1
( el problema total de Lehmer ).Explicación:
fuente
Jalea ,
98 bytes-1 byte gracias a @Dennis! (use exponenciación en lugar de multiplicación para evitar
Æṣ(0)
)Devolverá una lista de cero y el número perfecto impar más pequeño , si existe alguno.
¿Cómo?
fuente
Haskell, 46 bytes
Termina si encuentra la cuarta solución al problema de Brocard .
fuente
Python, 92 bytes
Esto no está ganando ninguna competencia de golf de código, y requiere memoria infinita y profundidad de recursión, pero esta es una oportunidad casi perfecta para resolver un problema interesante que pregunté en el intercambio de pila matemática hace dos años, que ningún número de Fibonacci mayor que 8 es la suma de dos cubos positivos . Curiosamente, comenzó como una idea de desafío de golf de código, así que supongo que he cerrado el círculo.
fuente
Python 2,
1239892 bytesEste código terminará si la conjetura de Goldbach no se cumple para todos los números pares (es decir, si todos los números pares se pueden expresar como la suma de dos números primos). Actualmente se ha probado para números de hasta 4 * 10 ^ 18.
¡Muchísimas gracias a @ Pietu1998 por acortar mucho mi código!
EDITAR: ¡Gracias a @JonathanAllan por eliminar 6 bytes de mi código!
fuente
g=lambda n:[p(b)*p(n-b)for b in range(n)]and g(n+2)
. También creo que esto debería leer "terminará si la conjetura de Goldbach no se cumple ".JavaScript (ES6),
104101 bytesUtiliza el mismo método que la respuesta de Perl: establece n en 196, luego agrega repetidamente n a su base 10 en reversa hasta que es un palíndromo en la base 10. Esto sería más corto si JS admitiera números de precisión arbitraria, pero bueno.
fuente
Python, 80 bytes
Termina si se demuestra que la conjetura de Collatz es falsa. Ver esta pregunta .
fuente
Python 2, 64 bytes
No se ha demostrado que existan números de Lychrel en la base diez. 196 es el candidato número diez de Lychrel de base más pequeño. Se ha demostrado que si existe un palíndromo (lo que hace que 196 no sea un número de Lychrel), tendría al menos mil millones (10 ^ 9) dígitos, porque la gente ha ejecutado el algoritmo durante tanto tiempo.
fuente
Jalea , 7 bytes
Pruébalo en línea! (imprime dos elementos, no 4, para que pueda ver cómo se detiene)
Explicación
fuente
R, 30 bytes, discutible si es determinista
El generador de números aleatorios predeterminado de R tiene una distribución equitativa en 653 dimensiones consecutivas, pero no se conoce en 654 dimensiones. Por lo tanto, puede haber o no una secuencia de números pseudoaleatorios que muestree el elemento más bajo de un vector dado 654 veces seguidas (aquí el vector
1:2
).Dado que el RNG de R es periódico (aunque con un período muy largo), afirmo que esto es determinista ya que eventualmente se repetirá al principio. Sus opiniones pueden diferir, por supuesto.
fuente
Python 3, 101 bytes
Sé que es más largo que muchos otros, pero pasé mucho tiempo viendo lo corto que podía jugar golf.
Esto intenta refutar Suma de Powers conjetura de Euler para
k=6
(no existe ninguna solución entero positivo a la ecuación DiophantineA^6+B^6+C^6+D^6+E^6==F^6
), para los que no se ha encontrado contraejemplo.En Python 2 (104 bytes):
Menos golfizado:
Versión Mathy sin evaluación:
Referencia alternativa: Conjetura de la suma de poderes de Euler - MathWorld
fuente
Python, 68 bytes
Pruébalo en línea
Intenta responder una de las preguntas de Gelfand .
fuente
Clojure, 154 bytes
Comprueba si hay un número superior a 82,000 que solo contiene 0 y 1 para la base 2 hasta la base 5. En otras palabras, comprueba si hay otro número en esta secuencia .
En ese grupo especial, sólo hay 3 números:
0
,1
y82,000
. No hay más números que sigan esa regla que sean menores que aproximadamente3*10^19723
.fuente
Pyt , 14 bytes
La respuesta del puerto de mbomb007 .
fuente