[seqfan] Re: A083207 On an observation of Frank Buss.
Donald Alan Morrison
donmorrison at gmail.com
Tue Aug 3 03:50:29 CEST 2010
I've verified the function works correctly for all 10,000 terms in the
b-file (domain: 1 < n < 43465 ):
http://www2.research.att.com/~njas/sequences/b083207.txt
Computation took 1 hour, 26 minutes, 5.17 seconds =)
Was that fast or slow?
On Mon, Aug 2, 2010 at 6:19 PM, Donald Alan Morrison
<donmorrison at gmail.com> wrote:
> 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