[seqfan] Counting factorizations: A001055 and friends

[hv at crypt.org]

I've pushed new code onto github [1] that focuses on finding records
in A001055:
  number of ways of factoring n with all factors greater than 1
.. as recorded in A033833 and A033834.

If someone can a) advise whether the definition and initial values of
A033833 should be left as is or modified, and b) remind me of the format
and process for uploading a b-file, I'll try to put some of this
information on OEIS over the weekend.

If anyone wishes to recreate the algorithms for Mathematica et al.,
but doesn't want to wade through my perl code, I'm happy to try to
explain the approach if you contact me off-list.

The gory details:

Current values in A033834 are mostly wrong, unless I've horribly
misunderstood something - A033834(n) should be A001055(A033833(n)),
and the given values start to diverge as early as A033834(5) given
as 6, which should be A001055(16) = 5. I do confirm the full list
of 118 results in A033833 (except per my comments about initial values
below), so I'm not sure what happened in the original calculations for 
A033834.

Strangely, A033833 mentions only A028422 (== A001055 - 1), not A001055
itself. Note that my code starts calculating from 2, but agrees with
A033833 for all other values.

Given n has k prime factors, it turns out A001055(n) is the same as 
the number of ways of taking k otherwise indistinguishable balls
each marked with one of the prime factors, and counting the ways 
they can be placed in k indistinguishable buckets; thus for a given 
prime signature, calculating A001055 becomes a problem of composing 
the partitions of the indices in that signature.

This is the approach taken in the code, which lends itself to highly
effective caching, and allowed me to calculate up to the record
A001055(10461394944000) = 5339083623 in 680 CPU seconds, consuming
587MB of RAM. (An earlier less caching-friendly version took over
4 hours to produce what this version does in 12s.)

The same correspondence can be seen in the cross-references available
as special cases for particular types of prime signature:

- A prime power counts only partitions: A001055(p^k) = A000041(k)
- A primorial yields Bell numbers: A001055(A002110(n)) = A000110(n)
- A001055(p^k.q) = A000070(k);
- A001055(p^k.q^2) = A000291(k);
- A001055(p^k.q.r) = A082775(k).

A033833 should also mention A025487: record indices of any function
that is determined solely by the prime signature must be a subsequence
of the latter.

Also maybe of interest: along the way, I condense the partition information
in a way that yields A088887; searching for that also found A140312 which
is a more specialized variant of the same data, and could do with some
additional disambiguating commentary. The current code is not optimized
for it, but I could probably generate some sort of b-file for A088887 if
it were useful. There are other aspects of the relationship between
A000041 and A088887 to be explored, one of which yields this apparently
new sequence:
  1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 7, 8, 11, 11, 17, 17, 23, 23, 30, 36, 44,
  56, 65, 79, 91, 110, 124, 146, 165, 189
.. which I will try to get back to. (The derivation is explained in the
code.)

My results are available in [2], giving records up to 10,461,394,944,000
(216 values).

Hugo

[1] https://github.com/hvds/seq
[2] https://github.com/hvds/seq/blob/master/A001055/records