Ordered and Unordered Factorizations of Integers
嚜燜he Mathematica? Journal
Ordered and Unordered
Factorizations of Integers
Arnold Knopfmacher
Michael Mays
We study the number of ways of writing a positive integer n as a product
of integer factors greater than one. We survey methods from the literature
for enumerating and also generating lists of such factorizations for a given
number n. In addition, we consider the same questions with respect to
factorizations that satisfy constraints, such as having all factors distinct.
We implement all these methods in Mathematica and compare the speeds
of various approaches to generating these factorizations in practice.
? Introduction
To study the number of ways of writing a positive integer n as a product of
integer factors greater than one, there are two basic cases to consider. First, we
can regard rearrangements of factors as different. In the case of n = 12, this gives
the following eight ordered factorizations.
2, 2, 3, 2, 3, 2, 2, 6, 3, 2, 2, 3, 4, 4, 3, 6, 2, 12
Alternatively we can ignore the order of the factors, which then gives the following four unordered factorizations.
3, 2, 2, 4, 3, 6, 2, 12
These two functions, which we denote by HHnL and PHnL, respectively, can be
considered multiplicative analogs of compositions and partitions of integers. A
composition is an ordered set of positive integers that sum to n. For example, we
have eight compositions of n = 4, namely {{4}, {3,1}, {1,3}, {2,2}, {2,2,1}, {1,2,1},
{1,1,2}, {1,1,1,1}}. In general the number of compositions of n, CHnL, is equal to
2n-1 . A partition is a set that sums to n in which order is disregarded. There are
five partitions of four. To count them we can use the function PartitionsP, and
to list them we can use Partitions from the Combinatorica package.
In[1]:=
DiscreteMath&Combinatorica&
In[2]:=
Partitions4
Out[2]=
4, 3, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1
The Mathematica Journal 10:1 ? 2006 Wolfram Media, Inc.
73
Ordered and Unordered Factorizations of Integers
In[3]:=
Out[3]=
PartitionsPRange10
1, 2, 3, 5, 7, 11, 15, 22, 30, 42
In fact the number of compositions and partitions arise as special cases of our
factorization functions, in the sense that if p is a prime number, then
H Hpr L = CHrL = 2r-1 and P H pr L = PartitionsP@rD. For general numbers n with
prime factorizations n = pr11 pr22 # prkk , the enumeration of HHnL and PHnL is more
complicated, as we shall discuss later.
We will also discuss factorizations into distinct parts. In the ordered case,
Hd H12L = 5 since we have the factorizations {{2,6}, {3,4}, {4,3}, {6,2}, {12}}. In the
unordered case, Pd H12L = 3 since there are three cases, {{4,3}, {6,2}, {12}}. If p is a
prime number, then as special cases we have Hd Hpr L = Cd H rL and
P Hpr L = PartitionsQ@rD, where Cd HrL denotes the number of compositions of r
into distinct parts (see Richmond and Knopfmacher [1]), and PartitionsQ is the
Mathematica function for counting partitions into distinct parts.
In[4]:=
Out[4]=
PartitionsQRange10
1, 1, 2, 2, 3, 4, 5, 6, 8, 10
The enumeration and generation of integer partitions and compositions are
problems discussed in standard books on combinatorics. A definitive reference is
Andrews [2]. However, the corresponding problems for ordered and unordered
factorizations have not until now received a comprehensive treatment.
? Ordered Factorizations
For historical reasons, we will discuss formulas to enumerate factorizations
before we discuss methods to generate the corresponding factorizations. In
addition, some of the recursive methods to generate factorizations are extensions
of the corresponding recursions to enumerate factorizations.
﹞ Recursions for Enumerating Ordered Factorizations
We begin with two recurrence formulas given by Hille [3]. The first element of
an ordered factorization of n > 1 can be any number d such that d divides n. By
appending to d all possible ordered factorizations of n 那 d, we obtain the recursion
HH1L = 1; H HnL = ?d?n HHdL for n ? 2. We implement this as follows.
In[5]:=
In[7]:=
Out[7]=
H11 : 1;
H1n_ : H1n TotalH1 DropDivisorsn, 1
TableH1n, n, 1, 12
1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8
The Mathematica Journal 10:1 ? 2006 Wolfram Media, Inc.
74
Arnold Knopfmacher and Michael Mays
Using the M?bius inversion formula, Hille also derived a second recursion,
ij
yz
jj
zz
n zy
n
i n zy
i
i
y
k-1
j
j
j
j
z
H HnL = 2 jjj? H j ???????? z - ? H j ????????????????? z + ÷ + H-1L H j ?????????????????????????????????? zzzzz,
jj
k pi {
k p1 p2 # pk {zz
k pi p j {
pi
pi, p j
k
{
where n = pr11 pr11 pr22 # prkk , which holds for n ? 2.
This finds the list of distinct prime factors of n.
In[8]:=
PrimeFactorListn_ : First FactorIntegern
This recursion requires the initial value ????12? .
In[9]:=
H21 1 2;
The recursion can be rendered elegantly as a oneliner.
In[10]:=
In[11]:=
Out[11]=
H2n_ : H2n 2 Total1 ^Length# H2n Times # &
RestSubsetsPrimeFactorListn
TableH2n, n, 2, 12
1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8
﹞ MacMahon*s Formula for H
MacMahon [4] derived an explicit formula for the value of HHnL as a double sum
over a product. Given n = pr11 pr11 pr22 # prkk ,
q
j-1
j=1
i=0
i
H HnL = ? ? H-1Li jj
k
where q =
In[12]:=
?ki=1 ri ,
k
j yz
z?
i{
h=1
ij rh + j - i - 1 yz
z,
j
rh
{
k
is the sum of the prime exponents of n. We program this by
H3n_ :
Total##
j
i
1 Binomialj, i ApplyTimes,
j1
i0
Binomial# j i 1, # & # &Last FactorIntegern
In[13]:=
Out[13]=
H32^ 5 3^4 5 Timing
0. Second, 102576
﹞ A Recursion for Factorizations with Distinct Parts
Warlimont [5] derived a Dirichlet series generating function for the function
Hd Hk, nL, which denotes the number of ordered factorizations of n into k distinct
parts. Although Warlimont was only interested in this for asymptotic purposes,
his generating function can be used to derive the following recurrence:
k
n
H-1L j
Hd Hk + 1, nL = k ! ? ???????????????????????????????????? ? Hd Jk - j, ????? N,
Hk - 1 - jL!
d
j=0
The Mathematica Journal 10:1 ? 2006 Wolfram Media, Inc.
75
Ordered and Unordered Factorizations of Integers
where the inside sum is taken over all d such that d ? n and for d ? 2, d is a
H j + 1L-st power.
There does not seem to be a simple combinatorial interpretation for this formula. We implement this starting with the appropriate boundary conditions.
In[14]:=
In[17]:=
Hd 1, n_ : 1;
Hd k_, 1 : 0;
Hd 0, n_ : 0
Hd 0, 1 : 1;
Hd 1, 1 : 0;
When n is a prime number we have the following.
In[19]:=
Hd k_, n_? PrimeQ : KroneckerDeltak, 1
Also observe that the number of parts k must satisfy 2k ∫ n.
In[20]:=
Hd k_, n_ ; 2k n : 0
Now we implement the general formula.
In[21]:=
Hd k_, n_ :
k1
Hd k, n k 1 1
j
k 1 j TotalHd k 1 j, n # &
j0
SelectRestDivisorsn, IntegerQ#1j1 &
In[22]:=
Out[22]=
Hd #, 24 & Range0, 4
0, 1, 6, 6, 0
We verify these counts by using the function DistinctOrderedFactoriza?
tions, which is defined in the next subsection.
In[23]:=
Out[23]=
DistinctOrderedFactorizations24
2, 3, 4, 2, 4, 3, 2, 12, 3, 2, 4, 3, 4, 2, 3, 8,
4, 2, 3, 4, 3, 2, 4, 6, 6, 4, 8, 3, 12, 2, 24
To obtain the total number of distinct ordered factorizations, we must sum
Hd @k, nD over all permissible values of the number of parts k.
In[24]:=
Hd n_ : TotalHd #, n & RangeFloorLog2, n
In[25]:=
Hd 36
Out[25]=
13
In practice this recursion is slow. A faster counting method is discussed in a later
section.
﹞ Generating Ordered Factorizations
The first recursion for HHnL suggests a natural recursive approach to generate all
the ordered factorizations of n.
The Mathematica Journal 10:1 ? 2006 Wolfram Media, Inc.
76
Arnold Knopfmacher and Michael Mays
We append to the first factor d in a factorization of n > 1, all possible ordered
factorizations of ????nd? , where d can be any divisor of n.
In[26]:=
OrderedFactorizations1 ;
In[27]:=
OrderedFactorizationsn_?PrimeQ : n
In[28]:=
OrderedFactorizationsn_ :
OrderedFactorizationsn FlattenFunctiond, Prepend#, d &
OrderedFactorizationsn d RestDivisorsn, 1
In[29]:=
OrderedFactorizations24
Out[29]=
2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 6, 2, 3, 2, 2, 2, 3, 4, 2, 4, 3,
2, 6, 2, 2, 12, 3, 2, 2, 2, 3, 2, 4, 3, 4, 2, 3, 8,
4, 2, 3, 4, 3, 2, 4, 6, 6, 2, 2, 6, 4, 8, 3, 12, 2, 24
One way to list all the ordered factorizations with distinct parts is to simply select
these from the list of all ordered factorizations.
In[30]:=
DistinctOrderedFactorizationsn_ :
SelectOrderedFactorizationsn, Unequal # &D
In[31]:=
DistinctOrderedFactorizations24
Out[31]=
2, 3, 4, 2, 4, 3, 2, 12, 3, 2, 4, 3, 4, 2, 3, 8,
4, 2, 3, 4, 3, 2, 4, 6, 6, 4, 8, 3, 12, 2, 24
However, there are faster methods for doing this, which we discuss in a later
section.
? Unordered Factorizations
There do not appear to be any explicit formulas for PHnL in the literature. Also,
the recurrence relations that are known tend to lack simple combinatorial
interpretations.
﹞ A Product Recursion
Harris and Subbarao [6] give the following product recursion for PHnL. For any
positive integer a, let di = a1那i if a is an ith power and di = 1 otherwise. Let
那那 pHn那dL
那那
= n pHnL . To make use of this, we take logs of
d = ∟?
i=1 di . This gives ∟d?n d
那那
the recurrence. First, we define the d values in terms of a given positive integer a.
One approach is to use Product.
In[32]:=
d1a_ :
CeilingLog2,a
IfIntegerQc a1i , c, 1
i1
Alternatively, here is a more elegant construction.
In[33]:=
d2a_ : ApplyTimes , Selecta1RangeCeilingLog2,a , IntegerQ
Then we can define P2.
The Mathematica Journal 10:1 ? 2006 Wolfram Media, Inc.
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- learning to rank
- ordered and unordered factorizations of integers
- unordered list cheatsheet
- unordered data structures sets and maps put your answers
- compsci 105 s1 2017 principles of computer science
- ordered and unordered arrangements
- cse 3318 notes 9 linked lists
- 214 tugboat volume 36 2015 no 3 tex
- combinatorial probabilities
- data structures are containers ordered lists