• Images
• Videos
• Documents
• Books
• Articles

Examples

• The number 20 has four multiplicative partitions: 2 × 2 × 5, 2 × 10, 4 × 5, and 20.
• 3 × 3 × 3 × 3, 3 × 3 × 9, 3 × 27, 9 × 9, and 81 are the five multiplicative partitions of 81 = 34. Because it is the fourth power of a prime, 81 has the same number (five) of multiplicative partitions as 4 does of additive partitions.
• The number 30 has five multiplicative partitions: 2 × 3 × 5 = 2 × 15 = 6 × 5 = 3 × 10 = 30.
• In general, the number of multiplicative partitions of a squarefree number with i {\displaystyle i} prime factors is the i {\displaystyle i} th Bell number, B i {\displaystyle B_{i}} .

Application

Hughes & Shallit (1983) describe an application of multiplicative partitions in classifying integers with a given number of divisors. For example, the integers with exactly 12 divisors take the forms p 11 {\displaystyle p^{11}} , p ⋅ q 5 {\displaystyle p\cdot q^{5}} , p 2 ⋅ q 3 {\displaystyle p^{2}\cdot q^{3}} , and p ⋅ q ⋅ r 2 {\displaystyle p\cdot q\cdot r^{2}} , where p {\displaystyle p} , q {\displaystyle q} , and r {\displaystyle r} are distinct prime numbers; these forms correspond to the multiplicative partitions 12 {\displaystyle 12} , 2 ⋅ 6 {\displaystyle 2\cdot 6} , 3 ⋅ 4 {\displaystyle 3\cdot 4} , and 2 ⋅ 2 ⋅ 3 {\displaystyle 2\cdot 2\cdot 3} respectively. More generally, for each multiplicative partition k = ∏ t i {\displaystyle k=\prod t_{i}} of the integer k {\displaystyle k} , there corresponds a class of integers having exactly k {\displaystyle k} divisors, of the form

∏ p i t i − 1 , {\displaystyle \prod p_{i}^{t_{i}-1},}

where each p i {\displaystyle p_{i}} is a distinct prime. This correspondence follows from the multiplicative property of the divisor function.³

Bounds on the number of partitions

Oppenheim (1926) credits MacMahon (1923) with the problem of counting the number of multiplicative partitions of n {\displaystyle n} ;⁴⁵ this problem has since been studied by others under the Latin name of factorisatio numerorum. If the number of multiplicative partitions of n {\displaystyle n} is a n {\displaystyle a_{n}} , McMahon and Oppenheim observed that its Dirichlet series generating function f ( s ) {\displaystyle f(s)} has the product representation⁶⁷ f ( s ) = ∑ n = 1 ∞ a n n s = ∏ k = 2 ∞ 1 1 − k − s . {\displaystyle f(s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}=\prod _{k=2}^{\infty }{\frac {1}{1-k^{-s}}}.}

The sequence of numbers a n {\displaystyle a_{n}} begins

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 7, 2, 2, 2, 9, 1, 2, 2, ... (sequence A001055 in the OEIS).

Oppenheim also claimed an upper bound on a n {\displaystyle a_{n}} , of the form⁸ a n ≤ n ( exp ⁡ log ⁡ n log ⁡ log ⁡ log ⁡ n log ⁡ log ⁡ n ) − 2 + o ( 1 ) , {\displaystyle a_{n}\leq n\left(\exp {\frac {\log n\log \log \log n}{\log \log n}}\right)^{-2+o(1)},} but as Canfield, Erdős & Pomerance (1983) showed, this bound is erroneous and the true bound is⁹ a n ≤ n ( exp ⁡ log ⁡ n log ⁡ log ⁡ log ⁡ n log ⁡ log ⁡ n ) − 1 + o ( 1 ) . {\displaystyle a_{n}\leq n\left(\exp {\frac {\log n\log \log \log n}{\log \log n}}\right)^{-1+o(1)}.}

Both of these bounds are not far from linear in n {\displaystyle n} : they are of the form n 1 − o ( 1 ) {\displaystyle n^{1-o(1)}} . However, the typical value of a n {\displaystyle a_{n}} is much smaller: the average value of a n {\displaystyle a_{n}} , averaged over an interval x ≤ n ≤ x + N {\displaystyle x\leq n\leq x+N} , is a ¯ = exp ⁡ ( 4 log ⁡ N 2 e log ⁡ log ⁡ N ( 1 + o ( 1 ) ) ) , {\displaystyle {\bar {a}}=\exp \left({\frac {4{\sqrt {\log N}}}{{\sqrt {2e}}\log \log N}}{\bigl (}1+o(1){\bigr )}\right),} a bound that is of the form n o ( 1 ) {\displaystyle n^{o(1)}} .¹⁰

Additional results

Canfield, Erdős & Pomerance (1983) observe, and Luca, Mukhopadhyay & Srinivas (2010) prove, that most numbers cannot arise as the number a n {\displaystyle a_{n}} of multiplicative partitions of some n {\displaystyle n} : the number of values less than N {\displaystyle N} which arise in this way is N O ( log ⁡ log ⁡ log ⁡ N / log ⁡ log ⁡ N ) {\displaystyle N^{O(\log \log \log N/\log \log N)}} .¹¹¹² Additionally, Luca et al. show that most values of n {\displaystyle n} are not multiples of a n {\displaystyle a_{n}} : the number of values n ≤ N {\displaystyle n\leq N} such that a n {\displaystyle a_{n}} divides n {\displaystyle n} is O ( N / log 1 + o ( 1 ) ⁡ N ) {\displaystyle O(N/\log ^{1+o(1)}N)} .¹³

See also

• Partition (number theory)
• Divisor

Further reading

• Knopfmacher, A.; Mays, M. E. (2005), "A survey of factorization counting functions" (PDF), International Journal of Number Theory, 1 (4): 563–581, doi:10.1142/S1793042105000315

External links

• Weisstein, Eric W., "Unordered Factorization", MathWorld

References

1. Andrews, G. (1976), The Theory of Partitions, Addison-Wesley, chapter 12 /wiki/George_E._Andrews ↩

2. Hughes, John F.; Shallit, Jeffrey (1983), "On the number of multiplicative partitions", American Mathematical Monthly, 90 (7): 468–471, doi:10.2307/2975729, JSTOR 2975729 /wiki/Jeffrey_Shallit ↩

3. Hughes, John F.; Shallit, Jeffrey (1983), "On the number of multiplicative partitions", American Mathematical Monthly, 90 (7): 468–471, doi:10.2307/2975729, JSTOR 2975729 /wiki/Jeffrey_Shallit ↩

4. Oppenheim, A. (1926), "On an arithmetic function", Journal of the London Mathematical Society, 1 (4): 205–211, doi:10.1112/jlms/s1-1.4.205 /wiki/Journal_of_the_London_Mathematical_Society ↩

5. MacMahon, P. A. (1923), "Dirichlet series and the theory of partitions", Proceedings of the London Mathematical Society, 22: 404–411, doi:10.1112/plms/s2-22.1.404 /wiki/Percy_Alexander_MacMahon ↩

6. Oppenheim, A. (1926), "On an arithmetic function", Journal of the London Mathematical Society, 1 (4): 205–211, doi:10.1112/jlms/s1-1.4.205 /wiki/Journal_of_the_London_Mathematical_Society ↩

7. MacMahon, P. A. (1923), "Dirichlet series and the theory of partitions", Proceedings of the London Mathematical Society, 22: 404–411, doi:10.1112/plms/s2-22.1.404 /wiki/Percy_Alexander_MacMahon ↩

8. Oppenheim, A. (1926), "On an arithmetic function", Journal of the London Mathematical Society, 1 (4): 205–211, doi:10.1112/jlms/s1-1.4.205 /wiki/Journal_of_the_London_Mathematical_Society ↩

9. Canfield, E. R.; Erdős, Paul; Pomerance, Carl (1983), "On a problem of Oppenheim concerning 'factorisatio numerorum'", Journal of Number Theory, 17 (1): 1–28, doi:10.1016/0022-314X(83)90002-1 /wiki/Paul_Erd%C5%91s ↩

10. Luca, Florian; Mukhopadhyay, Anirban; Srinivas, Kotyada (2010), "Some results on Oppenheim's 'factorisatio numerorum' function", Acta Arithmetica, 142 (1): 41–50, Bibcode:2010AcAri.142...41L, doi:10.4064/aa142-1-3, MR 2601047 /wiki/Acta_Arithmetica ↩

11. Canfield, E. R.; Erdős, Paul; Pomerance, Carl (1983), "On a problem of Oppenheim concerning 'factorisatio numerorum'", Journal of Number Theory, 17 (1): 1–28, doi:10.1016/0022-314X(83)90002-1 /wiki/Paul_Erd%C5%91s ↩

12. Luca, Florian; Mukhopadhyay, Anirban; Srinivas, Kotyada (2010), "Some results on Oppenheim's 'factorisatio numerorum' function", Acta Arithmetica, 142 (1): 41–50, Bibcode:2010AcAri.142...41L, doi:10.4064/aa142-1-3, MR 2601047 /wiki/Acta_Arithmetica ↩

13. Luca, Florian; Mukhopadhyay, Anirban; Srinivas, Kotyada (2010), "Some results on Oppenheim's 'factorisatio numerorum' function", Acta Arithmetica, 142 (1): 41–50, Bibcode:2010AcAri.142...41L, doi:10.4064/aa142-1-3, MR 2601047 /wiki/Acta_Arithmetica ↩