Does the code terminate?

Question

This is a code golf challenge I thought of with a mathematical bent. The challenge is to write the shortest code possible such that it is an open question whether or not the code terminates. An example of what I mean could be the following piece of python code, adapted from an anwser to this cs stackexchange question.

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

Mathematicians conjecture that there are no odd perfect numbers, but it has never been proven, so no one knows if this piece of code will ever terminate. Can you come up with other pieces of code (perhaps relying on other open problems like the Collatz conjecture, or the twin primes conjecture) that are shorter, but for which it is unknown whether or not they terminate?

Edit: Some people have brought up a good additional rule - The solutions to the question should be deterministic. Although it might be even more interesting if you could find shorter solutions using nondeterminism. In this case, the rule would be to find a snippet for which the probability of termination is unknown.

Answer 1

Jelly, 7 bytes

!‘Ʋµ4#

Try it online!

Background

This will terminate once it finds a fourth solution to Brocard's problem, i.e. a solution n! + 1 = m² with (n,m) ≠ (4, 5), (5, 11), (7, 71) over the positive integers. The implementation doesn't use floating point arithmetic, so it will only terminate if it does find a fourth solution or if n! can no longer be represented in memory.

Brocard's problem was first used in this answer by @xnor.

How it works

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

Answer 2

Jelly, 11 9 bytes

ÆẸ⁺‘ÆPµ6#

This will terminate once the sixth Fermat prime is found.

Try it online!

How it works

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

Answer 3

Pyth, 10 bytes

fP_h^2^2T5

Uses the conjecture that all Fermat numbers 2^(2^n)+1 are composite for n>4.

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

Answer 4

Python, 36 bytes

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

Uses Brocard's problem:

Is n!+1 a perfect square for any n≥8?

Computes successive factorials and checks whether they are squares and have k>7. Thanks to Dennis for 2 bytes!

This assumes Python continues to have accurate arithmetic for arbitrarily large numbers. In actual implementation, it terminates.

Answer 5

MATL, 11 bytes

`@QEtZq&+=z

Terminates iff the Goldbach conjecture is false. That is, the program stops if it finds an even number greater than 2 that cannot be expressed as the sum of two primes.

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

Answer 6

Brachylog (v2), 3 bytes in Brachylog's encoding

⟦cṗ

Try it online! (will time out without doing anything visible, for obvious reasons)

Full program; if run with no input, searches for the first Smarandache prime, and outputs true. if and when it finds one. It's an open question as to whether any Smarandache primes exist. (Note that Brachylog's prime-testing algorithm, although it works in theory on arbitrarily large numbers, tends to run slowly on them; thus, if you're interested in finding Smarandache primes yourself, I recommend using a different language.)

Explanation

⟦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 operates on the decimal digits of a number whenever you try to treat it like a list, so "range" followed by "concatenate" is a very terse way to generate the sequence of Smarandache numbers (and then we filter that by primality; Brachylog's default full program behaviour will then force the first element of the resulting generator). The range has a leading zero, but fortunately, with this flow pattern, Brachylog removes the zero rather than failing.

Here's an example that finds the first Smarandache number that's equal to 6 (mod 11), as a demonstration of a similar program that terminates within 60 seconds rather than having unknown halting status:

⟦c{-₆~×₁₁&}

Try it online!

This would print true. as a full program, but I threw in the Z command line argument to actually print the number in question, giving a better demonstration that this general approach works.

Answer 7

Perl, 50 38 36 34 33 bytes

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

Explanation: 196 is a possible Lychrel number - a number that does not form a palindrome by repeatedly adding its reverse to itself. The loop continues until $n is equal to its reverse, which is as yet unknown for initial value 196.

25 + 52 = 77

which is not valid.

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

so none of the numbers in this sequence are valid.

Edit: Golfed it down by using an until loop instead of a for loop (somehow). Also, I had fewer bytes than I thought (I should probably look at my bytecount more carefully in the future).

Edit: Replaced $n with $_ to save 2 bytes for the implied argument in reverse. I think this is as golfed as this implementation is going to get.

Edit: I was wrong. Instead of using until($%=reverse)==$_ I can go while the difference is nonzero (i.e. true): while($%=reverse)-$_.

Answer 8

Python, 30 28 bytes

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

This program will halt if and only if there is an integer n bigger than 1 such that 2^(n-1)-1 is divisible by n^3. To my knowledge it is not known whether any number with this property exists (if a number satisfying this property is prime, it is called a Wieferich prime of order 3 to base 2, and it is open whether any such prime exists).

Answer 9

05AB1E, 8 bytes

Will terminate when the 6th Fermat prime is found.

5µNoo>p½

Explanation

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

Answer 10

Haskell, 47 bytes

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

Searching the first quasiperfect number, which is a number n whose sum of divisors is 2*n+1. Instead of adding 1, I exclude 1 from the list of divisors.

Answer 11

Brain-Flak, 212 208 204 bytes

This program uses a multiplication algorithm written by MegaTom and a non-square checker written by 1000000000

Try It Online

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

This program starts at 8 and tests each number to see if n!+1 is a square number. It exits when it finds one. This is known as Brocard's Problem and it is an open problem in mathematics.

Answer 12

Actually, 16 bytes

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

Try it online!

This code terminates iff there is some composite number n such that totient(n) divides n-1 (Lehmer's totient problem).

Explanation:

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

Answer 13

Jelly, 9 8 bytes

-1 byte thanks to @Dennis! (use exponentiation instead of multiplication to avoid Æṣ(0))

*ḂÆṣ=µ2#

Will return a list of zero and the smallest odd perfect number, if any exist.

How?

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

Answer 14

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)

This code will terminate if 10223 is a Sierpiński number. 10223 is currently the smallest candidate that may or may not be a Sierpiński number, as of December 2013.

A Sierpiński number is a number k in which all numbers of the form (k * 2^n) + 1 are composite.

Answer 15

Pyth, 16 bytes

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

Returns the first value for which the Collatz conjecture does not hold. As it is unknown whether the conjecture holds for all numbers, it is unknown whether this code will terminate.

Answer 16

Haskell, 46 bytes

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

Terminates if it finds the 4th solution to brocard's problem.

Answer 17

Python, 92 bytes

This isn't winning any code golf competitions, and it requires infinite memory and recursion depth, but this is an almost perfect opportunity to plug an interesting problem I asked on math stackexchange two years ago, that no Fibonacci number greater than 8 is the sum of two positive cubes. Funnily enough, it started as an code golf challenge idea, so I guess I've come full circle.

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)

Answer 18

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)

This code will terminate if the Goldbach conjecture does not hold for all even numbers (i.e. if all even numbers can be expressed as the sum of two primes). It has currently been tested for numbers up to 4*10^18.

A huge amount of thanks to @Pietu1998 for shortening my code by a lot!

EDIT: Thanks to @JonathanAllan for shaving 6 bytes off my code!

Answer 19

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

Uses the same method as the Perl answer: sets n to 196, then repeatedly adds n to its base 10 reverse until it's a palindrome in base 10. This would be shorter if JS supported arbitrary-precision numbers, but oh well.

Answer 20

Python, 80 bytes

Terminates if the Collatz Conjecture is proven false. See this 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

Answer 21

Jelly, 7 bytes

*+3Ẓµ4#

Try it online! (prints two elements, not 4, so that you can actually see it halt)

Prints the first four \$n\$ such that \$n^n+3\$ is prime. It is not known whether four+ numbers with this property exist. The first three are 2, 1036, and 2770.

Explanation

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

Answer 22

Pyth, 13 bytes

.u@,/G2h*5GG7

Like Steven H.'s answer, but saving a few bytes by using the 5n+1 problem instead

Do the iterates of $$f(n)=\begin{cases}5n+1&\mbox{if }n\mbox{ is odd}\\\frac{n}{2}&\mbox{otherwise}\end{cases}$$ starting with 7, cycle?

While it seems unlikely, the answer is unknown!

Answer 23

Vyxal, 8 bytes

λEE›æ;5ȯ

Try it Online!

Finds the fifth Fermat Prime.

λ    ;5ȯ # First 5 numbers where
 EE›     # 2^2^n + 1
   æ     # Is prime

Answer 24

Python 2, 64 bytes

A Lychrel number is a natural number that cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers.

No Lychrel numbers have been proven to exist in base ten. 196 is the smallest base ten Lychrel number candidate. It has been shown that if a palindrome exists (making 196 not a Lychrel number), it would have at least a billion (10^9) digits, because people have run the algorithm that long.

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

Answer 25

R, 30 bytes, arguable whether it is deterministic

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

R's default random number generator has equidistribution in 653 consecutive dimensions but it is not known to in 654 dimensions. Thus there may or may not be a sequence of pseudorandom numbers that sample the lowest element from a given vector 654 times in a row (here the vector 1:2).

Since R's RNG is periodic (albeit with very long period), I claim that this is deterministic since it will eventually loop round to the start. Your opinions may differ, of course.

Answer 26

Pushy, 13 bytes

7$h&fh&r2e=?i

Try it online!

This program attempts to find a solution to Brocard's Problem - it will keep running until it finds a \$n \ge 8\$ such that \$ n! +1=m^2, m \in \mathbb{N} \$

Answer 27

Python 3, 101 bytes

I know it's longer than many others, but I spent a lot of time seeing how short I could golf this.

This attempts to disprove Euler's Sum of Powers Conjecture for k=6 (there exists no positive integer solution to the Diophantine equation A^6+B^6+C^6+D^6+E^6==F^6), for which no counterexample has been found.

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

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

Less golfed:

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

Mathy version with no 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

Alternate reference: Euler's Sum of Powers Conjecture - MathWorld

Answer 28

Python, 68 bytes

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

Try it online

Tries to answer one of Gelfand's Questions.

2. Will the row "23456789" ever appear for n>1? None does for n<=10^5. ...

Answer 29

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

Checks if there's a number above 82,000 that only contains 0's and 1's for base 2 all the way to base 5. In other words, it checks if there's another number in this sequence.

In that special group, there are only 3 numbers: 0, 1 and 82,000. There are no more numbers that follow that rule that are less than approximately 3*10^19723.

Answer 30

Pyt, 14 bytes

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

Port of mbomb007's answer.