92
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Luis Mendo Oct 22 '16 at 0:03
  • 3
    \$\begingroup\$ Your code can be golfed to 50 bytes: n=3 while sum(k*(n%k<1)for k in range(1,n))-n:n+=2. \$\endgroup\$ – xnor Oct 22 '16 at 1:24
  • 13
    \$\begingroup\$ This really is a great concept. It's nice to see original ideas like this. \$\endgroup\$ – Nathan Merrill Oct 22 '16 at 1:59
  • 7
    \$\begingroup\$ @Mego I think this challenge only works if you assume infinite data types what will automatically assume infinite memory. \$\endgroup\$ – Martin Rosenau Oct 22 '16 at 9:41
  • 52
    \$\begingroup\$ When I read the title I thought you wanted us to solve the halting problem AND golf the solution. \$\endgroup\$ – MrPaulch Oct 22 '16 at 12:00

27 Answers 27

29
\$\begingroup\$

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.
\$\endgroup\$
  • 3
    \$\begingroup\$ I need to learn jelly... \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Oct 23 '16 at 19:42
19
\$\begingroup\$

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.
\$\endgroup\$
16
\$\begingroup\$

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                   
\$\endgroup\$
11
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Would -~n**.5 not work in place of (n+1)**.5? \$\endgroup\$ – ETHproductions Oct 22 '16 at 15:59
  • \$\begingroup\$ @ETHproductions The precedence of exponentation is higher than the precedence of ~, so that would just raise a TypeError for trying to negate a float bitwise. \$\endgroup\$ – Dennis Oct 22 '16 at 21:22
11
\$\begingroup\$

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)-$_.

\$\endgroup\$
  • 3
    \$\begingroup\$ Since there are a finite number of possible plain perl numbers I can in fact determine if this program terminates or not. You need to load a bigint package to make this work (or implement it) \$\endgroup\$ – Ton Hospel Oct 22 '16 at 8:09
  • \$\begingroup\$ Do it. I dare you. :-) \$\endgroup\$ – Veky Oct 23 '16 at 21:26
11
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Are you sure the parentheses are placed correctly? It looks like you're testing to see if 2^(n-1) !≡ 1 (mod n^3), not 2^n ≡ 1 (mod n^3). Granted, I don't know Python's operator precedence all that well. \$\endgroup\$ – Gabriel Benamy Oct 24 '16 at 18:51
  • \$\begingroup\$ Whoops, the code is correct, but my explanation isn't. I'll fix it. \$\endgroup\$ – Julian Rosen Oct 24 '16 at 18:53
  • 2
    \$\begingroup\$ you can replace (n-1) with ~-n \$\endgroup\$ – Wheat Wizard Oct 24 '16 at 18:59
7
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I hope this problem and the Sierpinski problem are resolved in the near future, just with more calculations. \$\endgroup\$ – qwr Oct 22 '16 at 8:05
  • 4
    \$\begingroup\$ This code surely terminates, since you just name two lambdas, you don't actually call anything. :-P \$\endgroup\$ – Veky Oct 23 '16 at 21:34
  • 4
    \$\begingroup\$ In fact you didn't. Your code still always terminates, since Python2 semantics is frozen (PEP 404), and it includes a hard limit on recursive calls by BDFL's fiat (neopythonic.blogspot.hr/2009/04/final-words-on-tail-calls.html). ;-P \$\endgroup\$ – Veky Oct 26 '16 at 4:03
  • 2
    \$\begingroup\$ @Veky Had to upvote your comment. \$\endgroup\$ – clismique Oct 26 '16 at 4:48
  • 1
    \$\begingroup\$ Not many days after this was written, the prime 10223*2^31172165 + 1 was discovered. Since then, 21181 has been the smallest number for which it is not known if it is Sierpiński or not. \$\endgroup\$ – Jeppe Stig Nielsen May 6 at 5:00
4
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Without being able to read it, I doubt your code does exactly what you claim. Do you search for the first number that goes to a loop different from 4-2-1? I guess you won't find it if there is a smaller number that doesn't end in any loop. Anyway, if that's what your code does, that's good enough for not knowing whether it will terminate. \$\endgroup\$ – Christian Sievers Oct 22 '16 at 0:35
  • 1
    \$\begingroup\$ I search for the first integer >= 1 that goes to a loop and nowhere within the traversal to that loop contains a 1. \$\endgroup\$ – Steven H. Oct 22 '16 at 2:00
  • 3
    \$\begingroup\$ That's what I expected. But that's not the only conceivable way for a number to not satisfy the collatz conjecture. \$\endgroup\$ – Christian Sievers Oct 22 '16 at 2:11
  • \$\begingroup\$ Actually, it has been proven that every number either diverges to infinity or coverges to 1-2-4 under the Collatz map. Your code will never terminate. The idea is that the sequence of steps that forms a loop sets up an equation, whose only solutions are 1-2-4, negative values and non-integer rationals. \$\endgroup\$ – John Dvorak Oct 22 '16 at 12:48
  • 3
    \$\begingroup\$ @JanDvorak I do not believe that is true. Can you cite a source? \$\endgroup\$ – KSFT Oct 22 '16 at 17:03
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I think you can save 6 bytes with g=lambda n:[p(b)*p(n-b)for b in range(n)]and g(n+2). I also think this should read "will terminate if the Goldbach conjecture does not hold". \$\endgroup\$ – Jonathan Allan Oct 24 '16 at 0:31
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Although this is long, it's cleverly golfed, so +1. \$\endgroup\$ – wizzwizz4 Oct 25 '16 at 9:02
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ That's disgusting, but also beautiful. \$\endgroup\$ – James Murphy Oct 29 '16 at 5:52
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ @trichoplax Ah, the tabs / spaces "feature" strikes again... \$\endgroup\$ – wizzwizz4 Oct 25 '16 at 9:28
  • 1
    \$\begingroup\$ If anyone else also finds the tab conversion unhelpful, there's a discussion on meta... \$\endgroup\$ – trichoplax Oct 25 '16 at 9:28
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

  1. Will the row "23456789" ever appear for n>1? None does for n<=10^5. ...
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Pyt, 14 bytes

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

Port of mbomb007's answer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.