[seqfan] Re: A083207 On an observation of Frank Buss.
Donald Alan Morrison
donmorrison at gmail.com
Tue Aug 3 03:19:22 CEST 2010
Ok, my first mistake :) Not counting the sigma and divisors call in
the running time(!)
On Mon, Aug 2, 2010 at 6:16 PM, Donald Alan Morrison
<donmorrison at gmail.com> wrote:
> 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
>
More information about the SeqFan
mailing list