Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

You are given the functions: h1(f,*args) and h2(f,*args)

Both are methods which are already defined for you (here the asterisk indicates a variable number of arguments)

f is a function, *args is a list of parameters to be passed to that function

h1 returns a boolean value: True if the function f ever halts when called on *args and False if it doesn't (assuming the machine running it has infinite time and memory and that the interpreter/compiler for the language you're writing in knows how to handle infinite time and memory).

If f(*args) would ever make a call to h1 or h2, h1 throws an exception

h2 behaves exactly like h1 except that if f makes calls to h1, then h2 will not throw an exception

In as few characters as possible, write a program which takes no input and should output:

The Collatz Conjecture is {True/False}
Goldbach's Conjecture is {True/False}
The Twin Primes Conjecture is {True/False}

based on the validity of each of those conjectures.

Here are wikipedia links explaining each of the conjectures:

http://en.wikipedia.org/wiki/Collatz_conjecture

http://en.wikipedia.org/wiki/Goldbach%27s_conjecture

http://en.wikipedia.org/wiki/Twin_prime

You may assume any big integer library in whatever language you choose to use will successfully represent arbitrary large integers (so no bugs when the underlying array of digits exceeds 2^64 or anything like that)

Obviously since it's impossible to run your program, please provide an explanation of how it works along with the code

share|improve this question
    
This still needs an objective scoring criteria. Also, proving that the pseudo-program works might be really challenging. –  GigaWatt Sep 6 '12 at 19:41
    
I said fewest characters. It's a codegolf problem. –  dspyz Sep 6 '12 at 21:06
    
That is an, interesting, scoring procedure for this problem. "Solve the twin prime conjecture in the fewest number of characters." –  PyRulez Mar 8 at 16:16
add comment

1 Answer 1

Python (965 characters)

Since my question is getting no love. I'm posting my (non-code-golfed) solution in Python:

def numCollatzSteps(n):
    numSteps=0
    while n>1:
        if n%2==0:
            n//=2
        else:
            n=3*n+1
        numSteps+=1
    return numSteps

def findNonHaltingN():
    for n in count(1):
        if not h1(numCollatzSteps,n):
            return n

print "The Collatz Conjecture is "+str(not h2(findNonHaltingN))

def isPrime(n):
    for i in range(2,n):
        if n%i==0:
            return False
    else:
        return True

def isSumOf2Primes(n):
    for i in range(2,n-2):
        if isPrime(i) and isPrime(n-i):
            return True
    else:
        return False

def findNonSum():
    for i in count(4,2):
        if not isSumOf2Primes(i):
            return i

print "Goldbach's Conjecture is "+str(not h1(findNonSum))

def isSmallTwinPrime(n):
    return isPrime(n) and isPrime(n+2)

def nextSmallTwinPrime(n):
    for i in count(n):
        if isSmallTwinPrime(i):
            return i

def largestTwinPrimes():
    for n in count(2):
        if not h1(nextSmallTwinPrime,n):
            return n-1,n+1

print "The Twin Primes Conjecture is "+str(not h2(largestTwinPrimes))

It's fairly simple.

numCollatzSteps(n) says how many steps the Collatz sequence for a particular n takes. It runs on infinitely if said Collatz sequence doesn't terminate.

findNonHaltingN() counts upwards checking that numCollatzSteps terminates for every n. findNonHaltingN terminates if and only if there exists an n for which numCollatzSteps does not terminate.

So we can check if the Collatz conjecture is true by checking that findNonHaltingN() does not halt

isPrime(n) checks if a number is prime by seeing that no positive integer from 1 to n-1 divides it

isSumOf2Primes(n) iterates over all positive integers between 2 and n-2 and checking that at least one is prime together with its complement

findNonSum() counts even numbers upwards from 4 until it reaches the first number which is not a sum of 2 primes and then returns it. If no such number exists, then it will continue infinitely.

We can check if Goldbach's conjecture is true by seeing that findNonSum does not halt.

isSmallTwinPrime(n) returns true if and only if n and n+2 are both prime

nextSmallTwinPrime(n) returns the next number >= n for which isSmallTwinPrime is true

largestTwinPrimes() counts upwards from 2 checking that nextSmallTwinPrime halts for all n. If ever nextSmallTwinPrime does not halt for some n, then it follows that the largest twin primes are n-1 and n+1 and we stop there

Then we can check the validity of the twin primes conjecture by checking that largestTwinPrimes never halts.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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