[seqfan] Re: A122036

Richard Mathar mathar at strw.leidenuniv.nl
Mon Mar 28 12:11:40 CEST 2011


mm> As far as I am concerned, there is no way for anyone alone to compute this
mm> sequence up to  much more than 10^7!

I have computed this sequence up to 5*10^7, as documented,
on a single Intel Core 2 duo .
The observation is that one does not need to scan
all subsets of divisors for each n <= 5*10^7 checking whether
some adds up to n. You only try to find one (with a greedy
algorithm, taking large divisors first) and as soon as one
set of d is found which add to n (putting n into A136446)
move on to the next number.
It's only for the entries that actually end up in A122036 that
one has to scan many sets of divisors (again, not all, because
one uses a recursive algorithm that checks the current partial
sum and does not check further if the partial sum exceeds n).


More information about the SeqFan mailing list