¿El código termina?

92

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.

Bolton Bailey
fuente
2
Bienvenido a PPCG!
Luis Mendo
3
El código puede ser golfed a 50 bytes: n=3 while sum(k*(n%k<1)for k in range(1,n))-n:n+=2.
xnor
13
Este es realmente un gran concepto. Es bueno ver ideas originales como esta.
Nathan Merrill
77
@Mego Creo que este desafío solo funciona si asumes tipos de datos infinitos, lo que asumirá automáticamente una memoria infinita.
Martin Rosenau
52
Cuando leí el título pensé que querías que resolviéramos el problema de detención Y que resolviéramos la solución.
MrPaulch

Respuestas:

29

Jalea , 7 bytes

!‘Ʋµ4#

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

!‘Ʋµ4#  Main link. No arguments. Implicit argument: 0

    µ4#  Convert the links to the left into a monadic chain and call it with
         arguments k = 0, 1, 2, ... until 4 of them return 1.
!        Factorial; yield k!.
 ‘       Increment; yield k! + 1.
  Ʋ     Squareness; return 1 if k! + 1 is a perfect square, 0 if not.
Dennis
fuente
3
Necesito aprender jalea ...
noɥʇʎԀʎzɐɹƆ
19

Jalea , 11 9 bytes

ÆẸ⁺‘ÆPµ6#

Esto terminará una vez que se encuentre el sexto Fermat Prime .

Pruébalo en línea!

Cómo funciona

ÆẸ⁺‘ÆPµ6#  Main link. No arguments. Implicit argument: 0

      µ6#  Convert the links to the left into a monadic chain and call it with
           arguments k = 0, 1, 2, ... until 6 of them return 1.
ÆẸ         Convert [k] to the integer with that prime exponent factorization, i.e.,
           into 2 ** k.
  ⁺        Repeat.
   ‘       Increment.
           We've now calculated 2 ** 2 ** k + 1.
    ÆP     Test the result for primality.
Dennis
fuente
16

Pyth, 10 bytes

fP_h^2^2T5

Utiliza la conjetura para la que todos los números de Fermat 2^(2^n)+1 son compuestos n>4.

f        5   Find the first number T>=5 for which
   h^2^2T    2^(2^T)+1
 P_          is prime                   
xnor
fuente
11

Python, 36 bytes

k=n=1
while(n+1)**.5%1+7/k:k+=1;n*=k

Utiliza el problema de Brocard :

¿Es n! +1 un cuadrado perfecto para cualquier n≥8?

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.

xnor
fuente
1
¿ -~n**.5No funcionaría en lugar de (n+1)**.5?
ETHproductions
@ETHproductions La precedencia de la exponenciación es mayor que la precedencia de ~, por lo que eso solo generaría un TypeError por tratar de negar un flotador a nivel de bits.
Dennis
11

Perl, 50 38 36 34 33 bytes

$_=196;$_+=$%while($%=reverse)-$_

Explicació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.

25 + 52 = 77

Que no es válido.

96 + 69 = 165
165 + 561 = 726
726 + 627 = 1353
1353 + 3531 = 4884

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 $ncon $_para guardar 2 bytes para el argumento implícito en reverse. 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)-$_.

Gabriel Benamy
fuente
3
Dado que hay un número finito de posibles números de perl simples, de hecho puedo determinar si este programa termina o no. Necesita cargar un paquete bigint para que esto funcione (o implementarlo)
Ton Hospel
Hazlo. Yo Te reto. :-)
Veky
11

MATL, 11 bytes

`@QEtZq&+=z

Termina si la conjetura de Goldbach es falsa. Es decir, el programa se detiene si encuentra un número par mayor que 2ese que no puede expresarse como la suma de dos primos.

`        % Do...while
  @      %   Push iteration index k. Gives 1, 2, 3, ...
  QE     %   Add 1 and multiply by 2. Gives 4, 6, 8, ...
  tZq    %   Duplicate. Push all primes up to current k
  &+     %   Matrix with all pairwise additions of those primes
  =z     %   Number of entries of that matrix that equal k. This is used as loop
         %   condition. That is, the loop continues if this number is nonzero
         % Implicit end
Luis Mendo
fuente
8

05AB1E , 8 bytes

Terminará cuando se encuentre el sexto Fermat prime .

5µNoo>p½

Explicación

5µ          # loop over increasing N (starting at 1) until counter reaches 5
  Noo       # 2^2^N
     >      # + 1
      p½    # if prime, increase counter
Emigna
fuente
8

Python, 30 28 bytes

n=2
while 2**~-n%n**3-1:n+=1

Este 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).

Julian Rosen
fuente
¿Estás seguro de que los paréntesis se colocan correctamente? Parece que estás probando para ver si 2 ^ (n-1)! ≡ 1 (mod n ^ 3), no 2 ^ n ≡ 1 (mod n ^ 3). De acuerdo, no sé muy bien la precedencia del operador de Python.
Gabriel Benamy
Vaya, el código es correcto, pero mi explicación no lo es. Lo arreglaré.
Julian Rosen
2
puede reemplazar (n-1)con~-n
Wheat Wizard
7

Haskell, 47 bytes

[n|n<-[1..],2*n==sum[d|d<-[2..n],n`mod`d<1]]!!0

Buscando el primer número cuasiperfecto , que es un número ncuya suma de divisores es 2*n+1. En lugar de agregar 1, excluyo 1 de la lista de divisores.

Christian Sievers
fuente
6

Cerebro-Flak, 212 208 204 bytes

Este 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.

Asistente de trigo
fuente
6

Brachylog (v2), 3 bytes en la codificación de Brachylog

⟦cṗ

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

⟦cṗ
⟦     Form an increasing range from 0 to {the smallest number with no assertion failure} 
 c    Concatenate all the numbers that make up that range, in decimal
  ṗ   Assert that the result is prime

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:

⟦c{-₆~×₁₁&}

Pruébalo en línea!

Esto se imprimiría true.como un programa completo, pero agregué el Zargumento 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.

ais523
fuente
5

Python 2, 88 bytes

p=lambda n:all(n%x for x in range(2,n))
s=lambda n:0if p((10223*2**n)+1)else s(n+1)
s(0)

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 ken el que todos los números de la forma (k * 2^n) + 1son compuestos.

Qwerp-Derp
fuente
Espero que este problema y el problema de Sierpinski se resuelvan en el futuro cercano, solo con más cálculos.
qwr
44
Este código seguramente termina, ya que solo nombra dos lambdas, en realidad no llama a nada. :-P
Veky
44
De hecho no lo hiciste. Su código siempre termina, ya que la semántica de Python2 está congelada (PEP 404), e incluye un límite estricto para llamadas recursivas por parte de BDFL fiat ( neopythonic.blogspot.hr/2009/04/final-words-on-tail-calls.html ) ;-P
Veky
2
@ Veky Tuvo que votar tu comentario.
Qwerp-Derp
1
No muchos días después de que esto se escribió, 10223*2^31172165 + 1 se descubrió la prima . Desde entonces, 21181ha sido el número más pequeño para el que no se sabe si es Sierpiński o no.
Jeppe Stig Nielsen
4

Pyth, 16 bytes

f!}1.u@,/G2h*3GG

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á.

Steven H.
fuente
3
Sin poder leerlo, dudo que su código haga exactamente lo que usted dice. ¿Busca el primer número que va a un ciclo diferente de 4-2-1? Supongo que no lo encontrarás si hay un número menor que no termina en ningún bucle. De todos modos, si eso es lo que hace su código, es lo suficientemente bueno para no saber si terminará.
Christian Sievers
1
Busco el primer entero> = 1 que va a un bucle y en ninguna parte dentro del recorrido a ese bucle contiene un 1.
Steven H.
3
Eso es lo que esperaba. Pero esa no es la única forma concebible para que un número no satisfaga la conjetura del collatz.
Christian Sievers
En realidad, se ha demostrado que cada número diverge al infinito o cubre al 1-2-4 bajo el mapa de Collatz. Su código nunca terminará. La idea es que la secuencia de pasos que forma un bucle establece una ecuación, cuyas únicas soluciones son 1-2-4, valores negativos y racionales no enteros.
John Dvorak
3
@ JanDvorak No creo que sea cierto. ¿Puedes citar una fuente?
KSFT
4

En realidad , 16 bytes

1`;;pY)▒@D÷íu*`╓

Pruébalo en línea!

Este código termina si hay algún número compuesto ntal que se totient(n)divide n-1( el problema total de Lehmer ).

Explicación:

1`;;pY)▒@D÷íu*`╓
1`            `╓  first integer, starting with 0, where the following function leaves a truthy value on top of the stack:
    pY       *      composite (not prime) and
   ;  )▒            totient(n)
  ;     @D֒u       is in the list of divisors of n-1
Mego
fuente
4

Jalea , 9 8 bytes

-1 byte gracias a @Dennis! (use exponenciación en lugar de multiplicación para evitar Æṣ(0))

*ḂÆṣ=µ2#

Devolverá una lista de cero y el número perfecto impar más pequeño , si existe alguno.

¿Cómo?

*ḂÆṣ=µ2# - Main link: no arguments
     µ   - monadic chain separation
      2# - count up from implicit `n=0` and return the first 2 truthy results of
 Ḃ       -     mod 2        -> n%2
*        -     exponentiate -> n**(n%2)  (1 when n is even, n when n is odd)
  Æṣ     -     sum of proper divisors of n**(n%2)
    =    -     equals n?    -> 1 if n is zero or both perfect and odd, else 0
Jonathan Allan
fuente
4

Haskell, 46 bytes

[n|m<-[1..],n<-[1..m],product[1..n]+1==m^2]!!3

Termina si encuentra la cuarta solución al problema de Brocard .

Alondra
fuente
3

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.

def f(i,j):
 r=range(i)
 for a in r:
  for b in r:
   if a**3+b**3==i:1/0
 f(j,i+j)
f(13,21)
qwr
fuente
3

Python 2, 123 98 92 bytes

p=lambda n,k=2:n<=k or n%k*p(n,k+1)
g=lambda n:[p(b)*p(n-b)for b in range(n)]and g(n+2)
g(4)

Este 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!

Qwerp-Derp
fuente
Creo que puedes guardar 6 bytes con 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 ".
Jonathan Allan
2

JavaScript (ES6), 104 101 bytes

for(n=[6,9,p=1];!p;n=n.map((x,i)=>(q=n[n.length+~i],p|=x^q,c=q+x+c/10|0)%10).concat(c/10|0||[]))c=p=0

Utiliza 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.

ETHproducciones
fuente
Aunque esto es largo, es hábilmente golfizado, entonces +1.
wizzwizz4
2

Python, 80 bytes

Termina si se demuestra que la conjetura de Collatz es falsa. Ver esta pregunta .

n=2
while 1:
 L=[];x=n
 while~-n:1/(n not in L);L+=[n];n=(n/2,n*3+1)[n%2]
 n=x+1
mbomb007
fuente
Eso es asqueroso, pero también hermoso.
James Murphy
1

Python 2, 64 bytes

Un número de Lychrel es un número natural que no puede formar un palíndromo a través del proceso iterativo de invertir repetidamente sus dígitos y sumar los números resultantes.

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.

n=196
while 1:
    x=str(n);r=x[::-1]
    if x!=r:n=n+int(r)
    else:1/0
mbomb007
fuente
@trichoplax Ah, las "características" de las pestañas / espacios vuelven a aparecer ...
wizzwizz4
1
Si alguien más también encuentra que la conversión de pestañas no es útil, hay una discusión sobre meta ...
trichoplax
1

Jalea , 7 bytes

*+3Ẓµ4#

Pruébalo en línea! (imprime dos elementos, no 4, para que pueda ver cómo se detiene)

nortenortenorte+3

Explicación

*+3Ẓµ4#
     4#  Find the first four numbers with the following property:
    µ      (bracketing/grouping: place everything to the left inside the loop)
*          {The number} to the power of {itself}
 +3        plus 3
   Ẓ       is prime
ais523
fuente
0

R, 30 bytes, discutible si es determinista

while(any(sample(2,654,T)>1))1

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.

JDL
fuente
0

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 Diophantine A^6+B^6+C^6+D^6+E^6==F^6), para los que no se ha encontrado contraejemplo.

R=[1]
while 1:R+=[R[-1]+1];eval(("[1/("+"+%s**6"*5+"!=%%s**6)%s]"%("for %s in R "*6))%(*"ABCDEF"*2,))

En Python 2 (104 bytes):

R=[1]
while 1:R+=[R[-1]+1];eval(("[1/("+"+%s**6"*5+"!=%%s**6)%s]"%("for %s in R "*6))%tuple("ABCDEF"*2))

Menos golfizado:

x=2
while 1:
    R=range(1,x)
    [1/(A**6+B**6+C**6+D**6+E**6!=F**6)for F in R for E in R for D in R for C in R for B in R for A in R]
    x+=1

Versión Mathy sin evaluación:

R=range
x=2
while 1:
    for i in R(x**6):1/(sum(map(lambda x:x**6,[1+(i%x**-~j/x**j)for j in R(6)]))-i%x-1)
    x+=1

Referencia alternativa: Conjetura de la suma de poderes de Euler - MathWorld

mbomb007
fuente
0

Python, 68 bytes

n=2
while"".join(str((i+2)**n)[0]for i in range(8))!="23456789":n+=1

Pruébalo en línea

Intenta responder una de las preguntas de Gelfand .

  1. ¿Aparecerá la fila "23456789" para n> 1? Ninguno lo hace para n <= 10 ^ 5. ...
mbomb007
fuente
0

Clojure, 154 bytes

(loop[x 82001](if(= 0(reduce +(map{true 1 false 0}(for[y(range 3 6)](true?(for[z(str(range 2 y))](.indexOf z(Integer/toString x y))))))))x(recur(inc x))))

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, 1y 82,000. No hay más números que sigan esa regla que sean menores que aproximadamente 3*10^19723.

Qwerp-Derp
fuente