From: David Wilson (davidwwilson(AT)comcast.net)
Date: Fri, 18 May 2007 23:49:00 -0400
A074206(n) gives the number of ordered factorizations of n into integers >= 2.
Starting with that definition, we naturally arrive at the recurrence
a(n) = SUM_{1 <= i < n} a(i) if n > 1.
Kimberling gives this recurrence for A074206(n), and similar recurrences for
A002033(n) = A074206(n+1) (Kimberling) and A067824(n) = 2*A074206(n)
(Wasserman) follow immediately from it.
I have a different recurrence for A074206, which begins with the observation
that the value of A074206(n) depends only on the prime signature of n, that
is, the multiset of exponents in the prime factorization of n. What I have
found is a recurrence for A074206(n) based on prime signatures that can be
evaluated much faster than the above recurrence for extremely large n.
I have attached a program "a074206.pl.txt" that computes A074206(n) based on the
prime signature of n. For example, if we want to compute the number of
ordered factorizations of n with prime factorization of the form p q r^2 s^3
t^7, we run
gen.pl 1 1 2 3 7
which prints
568597568
The internals of gen.pl are obscurely Perlish, but at least serve to show
that I am not using on the standard recurrence. I was hoping to be able to
talk to someone about my methods.
Using this program, I discovered some interesting sequence characterizations
(here p, q, etc, are distinct primes):
A011782(n) = A074206(p^n) = ordered factorizations of p^n
A001792(n) = A074206(p^n q) = ordered factorizations of p^n q
A052141(n) = A074206(p^n q^n)
A000670(n) = ordered factorizations of a product of n distinct primes
A059516(n) = ordered factorizations of a product of squares of n distinct primes
A059576(m,n) = ordered factorizations of p^m q^n