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.
n=3
while sum(k*(n%k<1)for k in range(1,n))-n:n+=2
.Respostas:
Geléia , 7 bytes
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
fonte
Geléia ,
119 bytesIsso terminará quando o sexto prime Fermat for encontrado.
Experimente online!
Como funciona
fonte
Pitão, 10 bytes
Usa a conjectura para a qual todos os números Fermat
2^(2^n)+1
são compostosn>4
.fonte
Python, 36 bytes
Usa o problema de Brocard :
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.
fonte
-~n**.5
não funciona no lugar de(n+1)**.5
?~
, portanto, isso aumentaria um TypeError por tentar negar um flutuador bit a bit.Perl,
5038363433 bytesExplicaçã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.
o que não é válido.
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
$n
por$_
para salvar 2 bytes para o argumento implícito emreverse
. 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)-$_
.fonte
MATL, 11 bytes
Encerra se a conjectura de Goldbach for falsa. Ou seja, o programa para se encontrar um número par maior que
2
isso não pode ser expresso como a soma de dois números primos.fonte
05AB1E , 8 bytes
Terminará quando o 6º Fermat prime for encontrado.
Explicação
fonte
Python,
3028 bytesEste 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).
fonte
(n-1)
por~-n
Haskell, 47 bytes
Procurando o primeiro número quase perfeito , que é um número
n
cuja soma dos divisores é2*n+1
. Em vez de adicionar 1, excluo 1 da lista de divisores.fonte
Flacidez cerebral,
212208204 bytesEste 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.
fonte
Brachylog (v2), 3 bytes na codificação de Brachylog
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
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:
Experimente online!
Isso seria impresso
true.
como um programa completo, mas lancei oZ
argumento da linha de comando para realmente imprimir o número em questão, dando uma melhor demonstração de que essa abordagem geral funciona.fonte
Python 2, 88 bytes
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
k
em que todos os números do formulário(k * 2^n) + 1
são compostos.fonte
10223*2^31172165 + 1
foi descoberto . Desde então,21181
tem sido o menor número pelo qual não se sabe se é Sierpiński ou não.Pitão, 16 bytes
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á.
fonte
Na verdade , 16 bytes
Experimente online!
Esse código termina se houver algum número composto
n
quetotient(n)
dividan-1
( problema totiente de Lehmer ).Explicação:
fonte
Geléia ,
98 bytes-1 byte graças a @Dennis! (use exponenciação em vez de multiplicação para evitar
Æṣ(0)
)Retornará uma lista de zero e o menor número perfeito ímpar , se houver algum.
Quão?
fonte
Haskell, 46 bytes
Termina se encontrar a quarta solução para o problema do brocard .
fonte
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.
fonte
Python 2,
1239892 bytesEste 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!
fonte
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".JavaScript (ES6),
104101 bytesUsa 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.
fonte
Python, 80 bytes
Encerra se a conjectura de Collatz for comprovadamente falsa. Veja esta pergunta .
fonte
Python 2, 64 bytes
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.
fonte
Geléia , 7 bytes
Experimente online! (imprime dois elementos, não 4, para que você possa vê-lo parar)
Explicação
fonte
R, 30 bytes, discutível se é determinístico
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.
fonte
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 DiofantinaA^6+B^6+C^6+D^6+E^6==F^6
), para o qual não foi encontrada nenhuma contra-exemplo.No Python 2 (104 bytes):
Menos golfe:
Versão Mathy sem avaliação:
Referência alternativa: Conjectura da soma dos poderes de Euler - MathWorld
fonte
Python, 68 bytes
Experimente online
Tenta responder a uma das perguntas de Gelfand .
fonte
Clojure, 154 bytes
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
,1
e82,000
. Não há mais números que seguem essa regra que sejam menores que aproximadamente3*10^19723
.fonte
Pyt , 14 bytes
Porto da resposta do mbomb007 .
fonte