And a last one, with dynamic programming from top to bottom...
def is_zk_bis(a):
if is_prime(a): return False
d = divisors(a)
s = sum(d)
if s & 1 or s < 2*a:
return False
target = s//2 - a
if target < 2 : return True
d = [i for i in d if i <= target]
m_ = {}
def m(i, w):
if w == 0: return 0
if i == 0: return 0
if (i, w) in m_:
return m_[i, w]
res = m(i - 1, w)
di = d[i-1]
if di <= w:
res = max(res, m(i - 1, w - di) + di)
m_[i, w] = res
return res
res = m(len(d), target)
return res == target
faster sometimes:
sage: time is_zk_cython(12345792)
CPU times: user 3.31 s, sys: 0.01 s, total: 3.32 s
Wall time: 3.34 s
True
sage: time is_zk_bis(12345792)
CPU times: user 0.70 s, sys: 0.01 s, total: 0.71 s
Wall time: 0.72 s
True
but not in general:
sage: time r = [is_zk_cython(i) for i in range(10000, 11000)]
CPU times: user 0.62 s, sys: 0.00 s, total: 0.62 s
Wall time: 0.62 s
sage: time r = [is_zk_bis(i) for i in range(10000, 11000)]
CPU times: user 35.92 s, sys: 0.00 s, total: 35.92 s
Wall time: 35.92 s
On Aug 4, 2:34 am, mda_ <donmorri...@gmail.com> wrote:
> Wow, thanks. I didn't see your post just as I sent my retraction.
> I'll definitely play with this some tonight. I'm going to calculate
> very far, then do an intersection with is_squarefree() just out of
> curiousity.
>
> On Aug 3, 5:26 pm, YannLC <yannlaiglecha...@gmail.com> wrote:
>
> > Here is a cython version suitable only for ints.
> > [...]
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
