Gilbreath's conjecture in Python I've written some code for testing Gilbreath's conjecture in python (2.x). The conjecture was shown (in the 90s) to be true up to n=1012. My code uses the primesieve module to quickly generate primes and, by ignoring blocks of 0s and 2s, only calculates values in the array when necessary. However, it's quite slow; it makes heavy use of dictionary lookup, addition and deletion, and I expect would benefit from modification of this aspect.

def gilbreath(nMax):
    import primesieve
    def fill(D, j, k):
        if (j, k-1) not in D:
            fill(D, j, k-1)
        D[(j, k)] = abs(D[(j+1, k-1)]-D[(j, k-1)])
        # remove unneeded entries
        if (j-1, k) in D:
            del D[(j, k-1)]
        if (j+1, k) in D:
            del D[(j+1, k-1)]
    primes = primesieve.Iterator()
    D = {}
    depthLeft, depth, maxDepth, nDepth = -1, -1, -1, -1
    for n in xrange(1, nMax+1):
        D[(n, 0)] = int(primes.next_prime())
        j, k = n, 0
        while (D[(j, k)] &gt; 2) or (k &lt;= depthLeft):
            if D[(j, k)] &gt; 2:
                depth = k
            j -= 1
            k += 1
            fill(D, j, k)
            if (j == 1) and D[(j, k)] &gt; 1:
                print "conjecture false at n = %d" %n
        depthLeft = depth
        if depth &gt; maxDepth:
            maxDepth, nDepth = depth, n
    print "max depth %d at n = %d of %d" %(maxDepth, nDepth, nMax)
12% speed-up by simplification

Your code as is takes (with input 10**5):

max depth 96 at n = 92717 of 100000
        4027699 function calls (3764972 primitive calls) in 9.303 seconds


I simplified it by removing the:

    if (j-1, k) in D:
        del D[(j, k-1)]
    if (j+1, k) in D:
        del D[(j+1, k-1)]


And it runs in:

max depth 96 at n = 92717 of 100000
         4027699 function calls (3764972 primitive calls) in 8.129 seconds


So it both runs faster and is less code to maintain, a win-win.