[seqfan] Re: A083207 On an observation of Frank Buss.

[Donald Alan Morrison]

SeqFans,

I ported a c version of subset sum to sage/python and converted it to
a zumkeller verification function.  I verified its correctness for the
first 1137 terms ( 1 < n < 5001 ) in 76.04 seconds.  Recall it's the
dynamic programming method where the number of divisors and sigma(n)/2
determines the memory cost (exponentially), and the cpu running time
is supposed to be polynomial, together "pseudo-polynomial".  If you
see a bug, please make fun of me promptly!

def is_zk(a):
    sa = sigma(a)
    if mod(sa,2):
        return False
    hs = sa/2  # "C" in ssNew.c is sigma(a)/2
    d = divisors(a)
    n = len(d)
    S = (n + 1) * [None]
    A = (hs + 1) * [None]
    A[0] = 0
    S[0] = 0
    for i in xrange(1,hs+1):
        A[i] = -1
    for i in xrange(1,n+1):
        S[i] = d[i-1]
    for i in xrange(hs):
        if A[i] != -1:
            for j in xrange(A[i]+1,n+1):
                k = i + S[j]
                if k > hs:
                    continue
                if (A[k] == -1) or (A[k]>j):
                    A[k] = j
    if hs < 51:
        if any(filter(lambda b:b==-1,A[1:hs+1])):
            return False
    if A[hs] == -1:
        return False
    else:
        return a