Proofs a theorem false

checkab.py

"""
A nice example of the difference between an optimized algorithm and one that is not.

Problem comes from the "Mathematical theorems you had no idea existed, cause they're false" facebook page.
The (false) theorem is:

Let a<=b be positive integers and put I = range(a, b+1). Then there is a n in I such that for all k in I: k != n -> gcd(n,k) = 1.

In the code we look for an interval for which no suuch n exists.

 - find_ab_slow() is a naive implementation that runs in n**4 polylog(n) time (overnight run would be needed)
 - find_ab_fast() reuses as much information as possible. Also for...else... statements are cool. (17.7 s on my laptop)
 - print_ab() prints a table of n/k pairs to check by hand
"""


from fractions import gcd
import itertools

def find_ab_slow():
    for b in itertools.count(2):
        print b
        for a in range(1, b+1):
            for n in range(a, b+1):
                for k in range(a, b+1):
                    if k == n:
                        continue
                    if gcd(n, k) != 1:
                        # k shows that n does not work
                        break
                else:
                    # n works for a,b since no k is found
                    break  # stop searching for an n
            else:
                # no n works, a,b is not a good pair
                return (a, b)


def find_ab_fast():
    for b in itertools.count(2):
        lastn = b
        print b
        for a in range(b-1, 0, -1):
            # we work backwards, first checking the smaller interval and seeing if it starts failing when we d more
            for n in range(lastn, a-1, -1):
                if n == lastn:
                    # we only just moved a, so we know a+1...b are fine for lastn.
                    if gcd(n, a) == 1:
                        # lastn also works for this extra a
                        break
                else:
                    # we have changed n, so we need to check everything
                    for k in range(a, b+1):
                        if k == n:
                            continue
                        if gcd(n, k) != 1:
                            # k shows that n does not work
                            break
                    else:
                        # n works for a,b since no k is found
                        # al n in b,b-1,...,n+1 do not work for this set, so also not for smaller ones
                        lastn = n
                        break  # stop searching for an n
            else:
                # no n works, a,b is not a good pair
                return (a, b)


def print_ab(a, b):
    # Do a check 'by hand'
    for n in range(a, b+1):
        print("n: " + str(n))
        for k in range(a, b+1):
            if k == n:
                continue
            if gcd(k, n) != 1:
                print("  k: %i     GCD: %i" % (k, gcd(k, n)))
                break
        else:
            print "HELP!"


a, b = find_ab_fast()
print(a, b)
print_ab(a, b)