Gilbreath's conjecture in Python
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.