cantor.py

tenpows = [10**i for i in range(1000)]

def cantor(hi):
    res = 0
    iters = 0
    while hi > 0:
        if iters % 100 == 0: print 'Progress: %d' % hi
        iters += 1
        hi_s = str(hi)
        memo = {}
        def f(typ, i, lo, x):
            """
            typ 1: number of unspeakable numbers <= hi
            typ 2: sum of unspeakable numbers <= hi
            """
            if i == len(hi_s): return x!=0 and typ==1
            st = (typ, i, lo, x)
            if st in memo: return memo[st]
            res = 0
            p = tenpows[len(hi_s) - i - 1]
            for d in '012345689':
                if not lo and d > hi_s[i]: break
                y = (ord(d)-ord('0'))*p
                if typ == 1:
                    res += f(1, i+1, d<hi_s[i] or lo, (x+y)%7)
                if typ == 2:
                    res += y * f(1, i+1, d<hi_s[i] or lo, (x+y)%7)
                    res +=     f(2, i+1, d<hi_s[i] or lo, (x+y)%7)
            memo[st] = res
            return res
        res += f(2, 0, False, 0)
        hi -= f(1, 0, False, 0)
    print "iterations (i.e. number of ones) =", iters
    print "sum =", res
    return (iters, res)

cantor(7**7)