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

[Douglas McNeil]

On Tue, Aug 3, 2010 at 9:50 AM, Donald Alan Morrison
<donmorrison at gmail.com> wrote:
> 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?

Slowish, but not because of your algorithm.  After modifying the code
to include a simple brute-force divisors function, letting
sigma=sum(divisors), and some other trivial tweaks, on my notebook I
get:

(1) python accelerated using shedskin (which compiles a subset of
python to c++):  1m 44 s

(2) running same code in pypy (everyone's favourite JIT python
implementation):  3m 36 s

You should be able to get comparable speeds within Sage using Cython
annotations.  With just a few such markups, I got the time down to
11m, and I left lots of optimizations on the table (e.g. I was too
lazy to remind myself how arrays worked.)


Doug

-- 
Department of Earth Sciences
University of Hong Kong