[seqfan] Re: Ulam-related request

Richard Mathar mathar at strw.leidenuniv.nl
Sat May 30 22:00:17 CEST 2009

cs> Chris Starling chaosorder4 at gmail.com
cs> Sat May 30 03:44:29 CEST 2009
cs> Greetings, Seqfans, Romans, Countrymen:
cs> ...
cs> http://www.research.att.com/~njas/sequences/A001055
cs> Number of ways of factoring n (for n>1 we require that all the factors are
cs> greater than 1).
cs> (Formerly M0095 N0032)
cs> and
cs> http://www.research.att.com/~njas/sequences/A050322
cs> <http://www.research.att.com/%7Enjas/sequences/A050322>
cs> Number of factorizations indexed by prime signatures:
cs> A001055<http://www.research.att.com/%7Enjas/sequences/A001055>
cs> (A025487 <http://www.research.att.com/%7Enjas/sequences/A025487>).
cs> which show the totals, but I can't bear the thought of building this without
cs> breakdown by parts quantity.  I can't seem to find a table of this or
cs> reference to its definite presence in a book.  I'd be quite happy to
cs> <chop, snip, hack, cut, nibble...>

An explicit table for the factorizations into *distinct* factors is
in http://www.strw.leidenuniv.nl/~mathar/progs/A045778.txt  .
This may not be what you want, but it gives some idea of how this is created:
Write down all divisors of the number n, split off this divisor as a factor
in a loop over all divisors d, and then run the algorithm again for 
the new number n/d and all its divisors at least as large as d. This doesn't
require any estimator of how large the set of factorizations actually is,
and is a very basic exercise in programming recurrences.

Richard Mathar

More information about the SeqFan mailing list