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