C’est un défi de code de golf auquel j’ai pensé avec un penchant mathématique. Le défi consiste à écrire le code le plus court possible, de manière à poser la question de savoir si le code se termine ou non. Un exemple de ce que je veux dire pourrait être la pièce suivante de code python, adapté d'un anwser à cette question 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

Les mathématiciens supposent qu'il n'y a pas de nombres impairs parfaits, mais comme cela n'a jamais été prouvé, personne ne sait si ce code se terminera jamais. Pouvez-vous proposer d'autres éléments de code (reposant peut-être sur d'autres problèmes non résolus, tels que la conjecture de Collatz ou la conjecture des nombres premiers jumeaux) qui sont plus courts, mais pour lesquels on ne sait pas s'ils se terminent ou non?

Edit: Certaines personnes ont évoqué une bonne règle supplémentaire - Les solutions à la question devraient être déterministes. Bien que cela puisse être encore plus intéressant si vous pouviez trouver des solutions plus courtes en utilisant le non déterminisme. Dans ce cas, la règle serait de rechercher un extrait dont la probabilité de terminaison est inconnue.

Gelée , 7 octets

!‘Ʋµ4#

Essayez-le en ligne!

Contexte

Cela se terminera une fois qu'il aura trouvé une quatrième solution au problème de Brocard , à savoir une solution n! + 1 = m² avec (n, m) (4, 5), (5, 11), (7, 71) sur les entiers positifs. L'implémentation n'utilise pas d'arithmétique en virgule flottante, elle ne se terminera donc que si elle trouve une quatrième solution ou si n! ne peut plus être représenté en mémoire.

Le problème de Brocard a été utilisé pour la première fois dans cette réponse par @xnor.

Comment ça fonctionne

!‘Ʋµ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.

Gelée , 11 à 9 octets

ÆẸ⁺‘ÆPµ6#

Cela se terminera une fois que le sixième prime de Fermat aura été trouvé.

Essayez-le en ligne!

Comment ça fonctionne

ÆẸ⁺‘Æ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.

Pyth, 10 octets

fP_h^2^2T5

Utilise la conjecture pour laquelle tous les nombres de Fermat 2^(2^n)+1 sont composites n>4.

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

Python, 36 octets

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

Utilise le problème de Brocard :

Est-ce que n! +1 est un carré parfait pour tout n≥8?

Calcule les factorielles successives et vérifie si elles sont carrées et ont k>7. Merci à Dennis pour 2 octets!

Cela suppose que Python continue à avoir une arithmétique précise pour des nombres arbitrairement grands. Dans la mise en œuvre réelle, il se termine.

Perl, 50 38 36 34 33 octets

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

Explication: 196 est un nombre possible de Lychrel - un nombre qui ne forme pas un palindrome en ajoutant à plusieurs reprises son inverse à lui-même. La boucle continue jusqu'à ce que $ n soit égal à son inversion, inconnue pour la valeur initiale 196.

25 + 52 = 77

ce qui n'est pas valide.

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

donc aucun des nombres de cette séquence n'est valide.

Edit: Faites un golf en utilisant une boucle till au lieu d'une boucle for (en quelque sorte). De plus, j'avais moins d'octets que je ne le pensais (je devrais probablement regarder mon compte bytount plus attentivement à l'avenir).

Edit: Remplacé $npar $_pour enregistrer 2 octets pour l’argument impliqué dans reverse. Je pense que c'est aussi gâché que cette implémentation va se faire.

Edit: je me suis trompé. Au lieu d'utiliser until($%=reverse)==$_je peux aller alors que la différence est non nulle (c. -à- vrai): while($%=reverse)-$_.

MATL, 11 octets

`@QEtZq&+=z

Se termine si et seulement si la conjecture de Goldbach est fausse. C'est-à-dire que le programme s'arrête s'il trouve un nombre pair supérieur à 2celui qui ne peut pas être exprimé par la somme de deux nombres premiers.

`        % 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

05AB1E , 8 octets

Se terminera lorsque le 6ème prime de Fermat sera trouvé.

5µNoo>p½

Explication

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

Python, 30 à 28 octets

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

Ce programme s’arrêtera si et seulement s’il existe un nombre entier n supérieur à 1 tel que 2 ^ (n-1) -1 soit divisible par n ^ 3. À ma connaissance, on ne sait pas s'il existe un nombre avec cette propriété (si un nombre satisfaisant cette propriété est un nombre premier, il est appelé un nombre premier de Wieferich d'ordre 3 à base 2, et il est possible de savoir s'il existe).

Haskell, 47 octets

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

Recherche du premier nombre quasi-parfait , qui est un nombre ndont la somme des diviseurs est 2*n+1. Au lieu d'ajouter 1, j'exclus 1 de la liste des diviseurs.

Brain-Flak, 212 208 204 octets

Ce programme utilise un algorithme de multiplication écrit par MegaTom et un vérificateur non carré écrit par 1000000000.

Essayez-le en ligne

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

Ce programme commence à 8 et teste chaque nombre pour voir si n! +1 est un nombre carré. Il se ferme quand il en trouve un. C'est ce qu'on appelle le problème de Brocard et c'est un problème ouvert en mathématiques.

Brachylog (v2), 3 octets dans le codage de Brachylog

⟦cṗ

Essayez-le en ligne! (expirera sans rien faire de visible, pour des raisons évidentes)

Programme complet; si exécuté sans entrée, recherche le premier nombre premier Smarandache et renvoie true.si et quand il en trouve un. C'est une question ouverte de savoir s'il existe des nombres premiers Smarandache. (Notez que l'algorithme de test principal de Brachylog, bien qu'il fonctionne en théorie sur des nombres arbitrairement grands, a tendance à s'exécuter lentement. C'est pourquoi, si vous souhaitez que Smarandache vous amorce vous-même, je vous recommande d'utiliser un autre langage.)

Explication

⟦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 fonctionne sur les chiffres décimaux d’un nombre chaque fois que vous essayez de le traiter comme une liste. "Plage" suivi de "concaténer" est donc un moyen très succinct de générer la séquence de nombres de Smarandache (puis nous le filtrons par primalité; Brachylog le comportement par défaut du programme complet forcera le premier élément du générateur résultant). La plage a un zéro non significatif, mais heureusement, avec ce modèle d'écoulement, Brachylog supprime le zéro plutôt que d'échouer.

Voici un exemple qui trouve le premier nombre Smarandache égal à 6 (mod 11), comme démonstration d'un programme similaire qui se termine dans les 60 secondes au lieu d'avoir un statut d'arrêt inconnu:

⟦c{-₆~×₁₁&}

Essayez-le en ligne!

Cela s’imprimerait true.comme un programme complet, mais j’ai ajouté l’ Zargument de la ligne de commande pour imprimer le numéro en question, ce qui montre mieux que cette approche générale fonctionne.

Python 2, 88 octets

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)

Ce code se termine si 10223 est un numéro Sierpiński. 10223 est actuellement le plus petit candidat pouvant être ou ne pas être un numéro de Sierpiński, à partir de décembre 2013.

Un numéro Sierpiński est un nombre kdans lequel tous les numéros de la forme (k * 2^n) + 1sont composites.

Pyth, 16 octets

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

Retourne la première valeur pour laquelle la conjecture de Collatz ne tient pas. Comme on ne sait pas si la conjecture est vraie pour tous les nombres, on ne sait pas si ce code va se terminer.

Réellement , 16 octets

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

Essayez-le en ligne!

Ce code se termine si et seulement si un nombre composé ntel que totient(n)divise n-1( le problème Lehmer ).

Explication:

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

Jelly , 9 8 octets

-1 octet grâce à @Dennis! (utilisez l'exponentiation au lieu de la multiplication pour éviter Æṣ(0))

*ḂÆṣ=µ2#

Renverra une liste de zéro et le plus petit nombre parfait impair , s'il en existe.

Comment?

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

Haskell, 46 octets

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

Se termine s'il trouve la 4ème solution au problème de brocard .

Python, 92 octets

Ce n'est pas gagner un concours de golf de code, et cela nécessite une mémoire infinie et une profondeur de récursion, mais c'est une opportunité presque parfaite de résoudre un problème intéressant de deux cubes positifs . Curieusement, cela a commencé comme une idée de défi de code de golf, alors je suppose que j'ai bouclé la boucle.

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)

Python 2, 123 98 92 octets

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)

Ce code se terminera si la conjecture de Goldbach ne s'applique pas à tous les nombres pairs (c'est-à-dire si tous les nombres pairs peuvent être exprimés sous forme de la somme de deux nombres premiers). Il a actuellement été testé pour des nombres allant jusqu'à 4 * 10 ^ 18.

Un grand merci à @ Pietu1998 pour avoir beaucoup raccourci mon code!

EDIT: Merci à @JonathanAllan pour avoir supprimé 6 octets de mon code!

JavaScript (ES6), 104 101 octets

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

Utilise la même méthode que la réponse Perl: définit n sur 196, puis ajoute plusieurs fois n à sa base 10 inverse jusqu'à ce que ce soit un palindrome en base 10. Cela serait plus court si JS prenait en charge des nombres à précision arbitraire, mais bon.

Python, 80 octets

Se termine si la conjecture de Collatz s'avère fausse. Voir cette question .

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

Python 2, 64 octets

Un numéro de Lychrel est un nombre naturel qui ne peut pas former un palindrome par le processus itératif consistant à inverser ses chiffres à plusieurs reprises et à additionner les nombres résultants.

Aucun nombre de Lychrel n'a été prouvé en base dix. 196 est le plus petit candidat du nombre de Lychrel en base dix. Il a été démontré que si un palindrome existait (faisant 196 pas un nombre de Lychrel), il aurait au moins un milliard (10 ^ 9) chiffres, car les gens ont exécuté l'algorithme aussi longtemps.

n=196
while 1:
    x=str(n);r=x[::-1]
    if x!=r:n=n+int(r)
    else:1/0

Gelée , 7 octets

*+3Ẓµ4#

Essayez-le en ligne! (imprime deux éléments, et non 4, pour que vous puissiez réellement le voir s'arrêter)

$n$$n^n+3$

Explication

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

R, 30 octets, discutable si c'est déterministe

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

Le générateur de nombres aléatoires par défaut de R possède une équidistribution dans 653 dimensions consécutives, mais on ne le sait pas dans 654 dimensions. Ainsi, il peut y avoir ou non une séquence de nombres pseudo-aléatoires qui échantillonne l'élément le plus bas d'un vecteur donné 654 fois dans une ligne (ici le vecteur 1:2).

Puisque le RNG de R est périodique (bien qu’il ait une très longue période), j’affirme que cela est déterministe puisqu’il ira en boucle au début. Vos opinions peuvent différer, bien sûr.

Python 3, 101 octets

Je sais que c'est plus long que beaucoup d'autres, mais j'ai passé beaucoup de temps à voir à quel point je pouvais jouer au golf.

Cette tente de réfuter la somme des puissances d'Euler Conjecture pour k=6(il existe pas de solution entière positive à l'équation diophantienne A^6+B^6+C^6+D^6+E^6==F^6), pour laquelle aucun n'a été trouvé contre - .

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 octets):

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

Moins joué au golf:

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

Version Mathy sans eval:

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

Référence alternative: Conjecture d'Euler sur la somme des pouvoirs - MathWorld

Python, 68 octets

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

Essayez-le en ligne

Essaie de répondre à l'une des questions de Gelfand .

2. La ligne "23456789" apparaîtra-t-elle pour n> 1? Aucun ne le fait pour n <= 10 ^ 5. ...

Clojure, 154 octets

(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))))

Vérifie si un nombre supérieur à 82 000 ne contient que des 0 et des 1 pour la base 2 jusqu'à la base 5. En d'autres termes, il vérifie s'il existe un autre nombre dans cette séquence .

Dans ce groupe spécial, il n'y a que trois chiffres: 0, 1et 82,000. Il n’ya pas d’autres chiffres qui suivent cette règle qui sont inférieurs à environ 3*10^19723.

Pyt , 14 octets

27*²0`ŕĐ₫+Đ₽¬ł

Port de la réponse de mbomb007 .