Factorizations with Relatively Prime Parts

In this final section we investigate an interesting class of restricted factorizations, namely the class of factorizations in which the factors must be relatively prime to each other. Clearly this is a stronger restriction than requiring distinct factors. The asymptotic growth of such factorizations has been studied by Warlimont [5]. We note that in the special case of squarefree integers, all factorizations are necessarily relatively prime and distinct. Thus, for squarefree integers the values of the three functions that count unrestricted or distinct or relatively prime factorizations, all coincide for the ordered and unordered cases respectively.

We will discuss and compare several different approaches to generate the corresponding lists of factorizations.

Ordered Factorizations with Relatively Prime Parts

In the ordered case, factorizations of into relatively prime parts have a natural correspondence to ordered partitions of a set with the elements . The exponential generating function for the number of ordered set partitions is . (These and further results on set partitions that follow can be found in Wilf's book [9].) From this exponential generating function we can easily compute the first few values.

Here is another expression for the number of ordered set partitions (sometimes called ordered Bell numbers) due to Carlitz [10].

In addition there is also this pretty expression as an infinite sum.

Using either of these it is easy to count the number of ordered relatively prime factorizations.

Unordered Factorizations with Relatively Prime Parts

In the unordered case, factorizations of into relatively prime parts now have a natural correspondence to unordered partitions of a set with the elements . The exponential generating function for the number of ordered set partitions is . We use this to easily compute the first few values.

Again there is a pretty expression for the number of partitions of a set (or Bell numbers) as an infinite sum. Now it is easy to count the number of unordered relatively prime factorizations.

Generating Lists of Relatively Prime Factorizations

There are several different approaches that can be used to find the desired lists.

Unordered Relatively Prime Factorizations by Selection

To generate a list of relatively prime factorizations, we need only search among the distinct unordered factorizations and pick out those with relatively prime parts.

Method 1. By Factorization

Our first approach to selecting the relatively prime cases is to factor the numbers in each distinct unordered factorization, and after flattening and sorting, see if this matches the factorization of .

This shows that is admissible as a relatively prime factorization of 60 but is not. We illustrate the method in the case .

We determine the positions of the cases with admissible factorizations. Then we read off these factorizations from the list.

We put this together into one function.

Method 2. By Greatest Common Divisors

A second approach is to check that the factors are relatively prime directly, by finding the greatest common divisors of every pair of factors. However, Bressoud and Wagon [11] give a much more efficient way to test a long list for relative primality of all pairs.

We rewrite our function accordingly.

Method 3: By Generating Set Partitions

The idea here is to generate the partitions of a set with elements and then replace these elements with the appropriate prime powers to obtain a list of relatively prime factorizations. We can recursively compute the lists of set partitions by noting that the partitions of a set with elements can be created by appending the singleton to each list of partitions of elements, or by appending the element to each partition of elements. An implementation of this recursion using ReplaceList is given by Dickau [12] as follows.

Here is an example using Dickau's function.

Now if, for example, , we must substitute , , to obtain the factors in the relatively prime factorizations. Finally, we multiply the factors together to produce the desired result.

Putting this together we have a nice oneliner. This approach is unsurprisingly much faster than the previous ones!

Ordered Relatively Prime Factorizations

Whichever of the three approaches is used to generate the unordered cases, we need only permute the elements of each such unordered factorization to produce the lists of the ordered ones.