O código termina?

92

Este é um desafio de código de golfe que eu pensei com uma inclinação matemática. O desafio é escrever o código mais curto possível, de modo que seja uma questão em aberto se o código termina ou não. Um exemplo do que quero dizer pode ser o seguinte trecho de código python, adaptado de uma resposta para essa pergunta do 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

Os matemáticos conjeturam que não há números perfeitos ímpares, mas isso nunca foi provado; portanto, ninguém sabe se esse código terminará. Você pode criar outros trechos de código (talvez confiando em outros problemas em aberto, como a conjectura de Collatz ou a conjectura de primos gêmeos) que são mais curtos, mas para os quais não se sabe se eles terminam ou não?

Edit: Algumas pessoas trouxeram uma boa regra adicional - As soluções para a pergunta devem ser determinísticas. Embora possa ser ainda mais interessante se você pudesse encontrar soluções mais curtas usando o não-determinismo. Nesse caso, a regra seria encontrar um trecho para o qual a probabilidade de término é desconhecida.

Bolton Bailey
fonte
2
Bem-vindo ao PPCG!
Luis Mendo
3
Seu código pode ser golfed para 50 bytes: n=3 while sum(k*(n%k<1)for k in range(1,n))-n:n+=2.
Xnor 22/10
13
Este é realmente um ótimo conceito. É bom ver idéias originais como essa.
Nathan Merrill
7
@Mego Eu acho que esse desafio só funciona se você assumir tipos de dados infinitos, o que assumirá automaticamente memória infinita.
Martin Rosenau
52
Quando li o título, pensei que você queria que resolvêssemos o problema da parada E jogássemos a solução.
MrPaulch

Respostas:

29

Geléia , 7 bytes

!‘Ʋµ4#

Experimente online!

fundo

Isso terminará assim que encontrar uma quarta solução para o problema de Brocard , ou seja, uma solução n! + 1 = m² com (n, m) ≠ (4, 5), (5, 11), (7, 71) sobre os números inteiros positivos. A implementação não usa aritmética de ponto flutuante; portanto, somente será encerrada se encontrar uma quarta solução ou se n! não pode mais ser representado na memória.

O problema de Brocard foi usado pela primeira vez nesta resposta por @xnor.

Como 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
fonte
3
Eu preciso aprender geléia ... #
23416
19

Geléia , 11 9 bytes

ÆẸ⁺‘ÆPµ6#

Isso terminará quando o sexto prime Fermat for encontrado.

Experimente online!

Como 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
fonte
16

Pitão, 10 bytes

fP_h^2^2T5

Usa a conjectura para a qual todos os números Fermat 2^(2^n)+1 são compostos n>4.

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

Python, 36 bytes

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

Usa o problema de Brocard :

N! +1 é um quadrado perfeito para qualquer n≥8?

Calcula fatoriais sucessivos e verifica se são quadrados e possuem k>7. Agradecimentos a Dennis por 2 bytes!

Isso pressupõe que o Python continue a ter aritmética precisa para números arbitrariamente grandes. Na implementação real, ele termina.

xnor
fonte
1
Será que -~n**.5não funciona no lugar de (n+1)**.5?
ETHproductions
@ETHproductions A precedência da exponenciação é maior que a precedência de ~, portanto, isso aumentaria um TypeError por tentar negar um flutuador bit a bit.
Dennis
11

Perl, 50 38 36 34 33 bytes

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

Explicação: 196 é um número possível de Lychrel - um número que não forma um palíndromo adicionando repetidamente seu reverso a si próprio. O loop continua até que $ n seja igual ao seu reverso, que ainda é desconhecido para o valor inicial 196.

25 + 52 = 77

o que não é válido.

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

portanto, nenhum dos números nesta sequência é válido.

Edit: Golpeou usando um loop até em vez de um loop for (de alguma forma). Além disso, eu tinha menos bytes do que eu pensava (provavelmente eu deveria olhar meu número de bytes com mais cuidado no futuro).

Editar: substituído $npor $_para salvar 2 bytes para o argumento implícito em reverse. Eu acho que isso é tão complicado quanto esta implementação.

Edit: Eu estava errado. Em vez de usar until($%=reverse)==$_posso ir enquanto a diferença é diferente de zero (isto é verdade): while($%=reverse)-$_.

Gabriel Benamy
fonte
3
Como existe um número finito de possíveis números perl simples, posso de fato determinar se esse programa termina ou não. Você precisa carregar um pacote bigint para fazer este trabalho (ou implementá-lo)
Ton Hospel
Faça. Atreva-se. :-)
Veky
11

MATL, 11 bytes

`@QEtZq&+=z

Encerra se a conjectura de Goldbach for falsa. Ou seja, o programa para se encontrar um número par maior que 2isso não pode ser expresso como a soma de dois números 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
fonte
8

05AB1E , 8 bytes

Terminará quando o 6º Fermat prime for encontrado.

5µNoo>p½

Explicação

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

Python, 30 28 bytes

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

Este programa será interrompido se, e somente se, houver um número inteiro n maior que 1, de modo que 2 ^ (n-1) -1 seja divisível por n ^ 3. Que eu saiba, não se sabe se existe algum número com essa propriedade (se um número que satisfaça essa propriedade for primo, ele será chamado de primo Wieferich da ordem 3 à base 2, e está aberto se esse primo existe).

Julian Rosen
fonte
Tem certeza de que os parênteses estão colocados corretamente? Parece que você está testando para ver se 2 ^ (n-1)! ≡ 1 (mod n ^ 3), não 2 ^ n ≡ 1 (mod n ^ 3). É verdade que não conheço muito bem a precedência de operadores do Python.
Gabriel Benamy
Opa, o código está correto, mas minha explicação não está. Eu resolvo isso.
Julian Rosen
2
você pode substituir (n-1)por~-n
Assistente de trigo
7

Haskell, 47 bytes

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

Procurando o primeiro número quase perfeito , que é um número ncuja soma dos divisores é 2*n+1. Em vez de adicionar 1, excluo 1 da lista de divisores.

Peneiradores cristãos
fonte
6

Flacidez cerebral, 212 208 204 bytes

Este programa usa um algoritmo de multiplicação escrito por MegaTom e um verificador não quadrado escrito por 1000000000

Experimente Online

(((()()()()){})){{}((({}()))<{(({})[()])}{}>[()]){({}<({}<>)({<({}[()])><>({})<>}{}<><{}>)>[()])}{}(({}())){(({}[()]<>)<>)(({({})({}[()])}{}[({})]<>)){{}{}({}<>)(<([()])>)}{}({}()){(((<{}{}<>{}>)))}{}}{}}

Este programa começa em 8 e testa cada número para ver se n! +1 é um número quadrado. Sai quando encontra um. Isso é conhecido como Problema de Brocard e é um problema aberto em matemática.

Assistente de Trigo
fonte
6

Brachylog (v2), 3 bytes na codificação de Brachylog

⟦cṗ

Experimente online! (atingirá o tempo limite sem fazer nada visível, por razões óbvias)

Programa completo; se executado sem entrada, procura pelo primeiro Smarandache prime e gera saída true.se e quando o encontrar. É uma questão em aberto se existem primos do Smarandache. (Observe que o algoritmo de teste principal de Brachylog, embora funcione teoricamente em números arbitrariamente grandes, tende a correr lentamente neles; portanto, se você estiver interessado em encontrar o Smarandache como primo, recomendo usar um idioma diferente.)

Explicação

⟦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

O Brachylog opera nos dígitos decimais de um número sempre que você tenta tratá-lo como uma lista; portanto, "range" seguido de "concatenate" é uma maneira muito concisa de gerar a sequência de números de Smarandache (e então filtramos isso por primalidade; Brachylog's o comportamento padrão do programa completo forçará o primeiro elemento do gerador resultante). O intervalo tem um zero inicial, mas felizmente, com esse padrão de fluxo, o Brachylog remove o zero em vez de falhar.

Aqui está um exemplo que encontra o primeiro número do Smarandache igual a 6 (mod 11), como uma demonstração de um programa semelhante que termina em 60 segundos, em vez de ter um status de interrupção desconhecido:

⟦c{-₆~×₁₁&}

Experimente online!

Isso seria impresso true.como um programa completo, mas lancei o Zargumento da linha de comando para realmente imprimir o número em questão, dando uma melhor demonstração de que essa abordagem geral funciona.

ais523
fonte
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 será encerrado se 10223 for um número Sierpiński. 10223 é atualmente o menor candidato que pode ou não ser um número Sierpiński, em dezembro de 2013.

Um número de Sierpiński é um número kem que todos os números do formulário (k * 2^n) + 1são compostos.

Qwerp-Derp
fonte
Espero que esse problema e o problema de Sierpinski sejam resolvidos no futuro próximo, apenas com mais cálculos.
Qd #
4
Esse código certamente termina, já que você apenas cita duas lambdas, na verdade não chama nada. :-P
Veky 23/10
4
Na verdade você não fez. Seu código ainda sempre termina, uma vez que a semântica do Python2 está congelada (PEP 404) e inclui um limite rígido de chamadas recursivas do decreto da BDFL ( neopythonic.blogspot.hr/2009/04/final-words-on-tail-calls.html ) ;-P
Veky
2
@Veky Tinha que votar em seu comentário.
Qwerp-Derp
1
Poucos dias depois disso, o primo 10223*2^31172165 + 1 foi descoberto . Desde então, 21181tem sido o menor número pelo qual não se sabe se é Sierpiński ou não.
Jeppe Stig Nielsen
4

Pitão, 16 bytes

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

Retorna o primeiro valor para o qual a conjectura de Collatz não é válida. Como não se sabe se a conjectura se aplica a todos os números, não se sabe se esse código terminará.

Steven H.
fonte
3
Sem poder ler, duvido que seu código faça exatamente o que você afirma. Você procura o primeiro número que passa para um loop diferente de 4-2-1? Eu acho que você não o encontrará se houver um número menor que não termine em nenhum loop. De qualquer forma, se é isso que o seu código faz, é bom o suficiente para não saber se ele será encerrado.
Christian Sievers
1
Eu procuro o primeiro número inteiro> = 1 que vai para um loop e em nenhum lugar dentro do percurso para esse loop contém um 1.
Steven H.
3
Era o que eu esperava. Mas essa não é a única maneira concebível de um número não satisfazer a conjectura de collatz.
Christian Sievers
Na verdade, ficou provado que todo número diverge para o infinito ou cobre para 1-2-4 sob o mapa de Collatz. Seu código nunca será encerrado. A idéia é que a sequência de etapas que forma um loop configure uma equação, cujas únicas soluções são 1-2-4, valores negativos e racionais não inteiros.
John Dvorak
3
@JanDvorak Eu não acredito que isso seja verdade. Você pode citar uma fonte?
KSFT 22/10/16
4

Na verdade , 16 bytes

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

Experimente online!

Esse código termina se houver algum número composto nque totient(n)divida n-1( problema totiente de Lehmer ).

Explicação:

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
fonte
4

Geléia , 9 8 bytes

-1 byte graças a @Dennis! (use exponenciação em vez de multiplicação para evitar Æṣ(0))

*ḂÆṣ=µ2#

Retornará uma lista de zero e o menor número perfeito ímpar , se houver algum.

Quão?

*ḂÆṣ=µ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
fonte
4

Haskell, 46 bytes

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

Termina se encontrar a quarta solução para o problema do brocard .

BlackCap
fonte
3

Python, 92 bytes

Isso não está vencendo nenhuma competição de código de golfe, e exige memória infinita e profundidade de recursão, mas é uma oportunidade quase perfeita para conectar um problema interessante que eu perguntei na troca de pilha matemática há dois anos, que nenhum número de Fibonacci maior que 8 é a soma de dois cubos positivos . Curiosamente, tudo começou como uma ideia de desafio de código de golfe, então acho que fiz um círculo completo.

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
fonte
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 será encerrado se a conjectura de Goldbach não for válida para todos os números pares (ou seja, se todos os números pares puderem ser expressos como a soma de dois números primos). Atualmente, foi testado para números de até 4 * 10 ^ 18.

Um enorme agradecimento a @ Pietu1998 por reduzir muito meu código!

Edição: Graças a @ JonathanAllan por raspar 6 bytes fora do meu código!

Qwerp-Derp
fonte
Eu acho que você pode salvar 6 bytes com g=lambda n:[p(b)*p(n-b)for b in range(n)]and g(n+2). Eu também acho que deve ler-se "terminará se a conjectura de Goldbach não se sustentar".
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

Usa o mesmo método da resposta Perl: define n para 196 e depois adiciona n repetidamente à sua base 10 reversa até que seja um palíndromo na base 10. Isso seria mais curto se o JS suportasse números de precisão arbitrária, mas tudo bem.

ETHproductions
fonte
Embora seja longo, ele é habilmente jogado de golfe, então +1.
Wizzwizz4
2

Python, 80 bytes

Encerra se a conjectura de Collatz for comprovadamente falsa. Veja esta pergunta .

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
fonte
Isso é nojento, mas também bonito.
James Murphy
1

Python 2, 64 bytes

Um número de Lychrel é um número natural que não pode formar um palíndromo através do processo iterativo de reverter repetidamente seus dígitos e adicionar os números resultantes.

Nenhum número de Lychrel foi provado existir na base dez. 196 é o menor candidato a número dez da lista Lychrel. Foi demonstrado que, se um palíndromo existe (tornando 196 não um número Lychrel), ele teria pelo menos um bilhão (10 ^ 9) dígitos, porque as pessoas executam o algoritmo por tanto tempo.

n=196
while 1:
    x=str(n);r=x[::-1]
    if x!=r:n=n+int(r)
    else:1/0
mbomb007
fonte
@trichoplax Ah, as guias / espaços "recurso" golpeia outra vez ...
wizzwizz4
1
Se alguém encontra também a conversão guia inútil, há uma discussão sobre a meta ...
Trichoplax
1

Geléia , 7 bytes

*+3Ẓµ4#

Experimente online! (imprime dois elementos, não 4, para que você possa vê-lo parar)

nnn+3

Explicação

*+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
fonte
0

R, 30 bytes, discutível se é determinístico

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

O gerador de número aleatório padrão de R possui equidistribuição em 653 dimensões consecutivas, mas não é conhecido em 654 dimensões. Assim, pode ou não haver uma sequência de números pseudo-aleatórios que amostram o elemento mais baixo de um determinado vetor 654 vezes seguidas (aqui o vetor 1:2).

Como o RNG de R é periódico (embora com um período muito longo), afirmo que isso é determinístico, uma vez que eventualmente retornará ao início. Suas opiniões podem diferir, é claro.

JDL
fonte
0

Python 3, 101 bytes

Eu sei que é mais longo do que muitos outros, mas passei muito tempo vendo o quão curto eu poderia jogar isso.

Isto tenta refutar Conjetura de Euler para k=6(não existe nenhuma solução inteiro positivo para a equação Diofantina A^6+B^6+C^6+D^6+E^6==F^6), para o qual não foi encontrada nenhuma contra-exemplo.

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

No 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 golfe:

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

Versão Mathy sem avaliação:

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

Referência alternativa: Conjectura da soma dos poderes de Euler - MathWorld

mbomb007
fonte
0

Python, 68 bytes

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

Experimente online

Tenta responder a uma das perguntas de Gelfand .

  1. A linha "23456789" será exibida para n> 1? Nenhum faz para n <= 10 ^ 5. ...
mbomb007
fonte
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))))

Verifica se existe um número acima de 82.000 que contém apenas 0 e 1 para a base 2 até a base 5. Em outras palavras, verifica se há outro número nessa sequência .

Nesse grupo especial, existem apenas 3 números: 0, 1e 82,000. Não há mais números que seguem essa regra que sejam menores que aproximadamente 3*10^19723.

Qwerp-Derp
fonte