Unordered Factorization

Author

Eric W. Weisstein
November 4, 2003

This notebook downloaded from http://mathworld.wolfram.com/notebooks/NumberTheory/UnorderedFactorization.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/UnorderedFactorization.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Additional Authors

Knopfmacher, A. and Mays, M.  "Ordered and Unordered Factorizations of Integers.''  Mathematica J. 10, 72–89, 2006.

Enumeration

UnorderedFactorizations[m_,1]:={{}}
UnorderedFactorizations[1,n_]:={{}}
UnorderedFactorizations[m_,n_?PrimeQ]:=If[m<n,{},{{n}}]
UnorderedFactorizations[m_,n_]:=UnorderedFactorizations[m,n]=Module[{d},
Flatten[Function[d,Append[#,d]&/@UnorderedFactorizations[d,n/d]]/@Select[Divisors[n],1<#≤m&],1]
]
UnorderedFactorizations[1]:={{1}}
UnorderedFactorizations[n_]:=UnorderedFactorizations[n,n]

UnorderedFactorizations/@Range[10]//ColumnForm

Counts

Length/@UnorderedFactorizations/@Range[100]

Harris and Subbarao Formula

d[a_]:=Times@@Select[a^(1/Range[Ceiling[Log[2,a]]]),IntegerQ]
U[1]:=1
U[n_]:=U[n]=Plus@@(Log[d[#]]U[n/#]&/@Rest[Divisors[n]])/Log[n]

U0[1]:=1
U0[n_]:=U0[n]=FullSimplify[Plus@@(Log[d[#]]U[n/#]&/@Rest[Divisors[n]])/Log[n]]

U0/@Range[100]//Timing

Round[U/@Range[100]]//Timing

<<Utilities`Simplify`

U/@Range[100]//LogSimplify//Timing

Maximum Number of Parts

Prepend[Max/@Map[Length,UnorderedFactorizations/@Range[2,110],{2}],1]

Distinct Parts

DistinctUnorderedFactorizations[m_,1]={{}};
DistinctUnorderedFactorizations[1,n_]={};
DistinctUnorderedFactorizations[0,n_]={};
DistinctUnorderedFactorizations[m_,n_?PrimeQ]:=If[m<n,{},{{n}}]
DistinctUnorderedFactorizations[m_,n_]:=DistinctUnorderedFactorizations[m,n]=Module[{d},Flatten[Function[d,Append[#,d]&/@DistinctUnorderedFactorizations[d-1,n/d]]/@Select[Divisors[n],1<#<=m&],1]]
DistinctUnorderedFactorizations[n_]:=DistinctUnorderedFactorizations[n,n]

{UnorderedFactorizations[24],DistinctUnorderedFactorizations[24]}

DistinctUnorderedFactorizations/@Range[10]//ColumnForm

Length/@DistinctUnorderedFactorizations/@Range[100]

Maximum Number of Parts

Prepend[Max/@Map[Length,DistinctUnorderedFactorizations/@Range[2,110],{2}],1]

l=Prepend[Max/@Map[Length,DistinctOrderedFactorizations/@Range[2,10^4],{2}],1];//Timing

Take[FoldList[Plus,0,Length/@Split[FoldList[Max,0,l]]],{2,-2}]