A033833 | Highly factorable numbers: numbers with a record number of proper factorisations. |
The sequence, up to and including 25920, runs as follows:
1, 4, 8, 12, 16, 24, 36, 48, 72, 96, 120, 144, 192, 216, 240, 288, 360, 432, 480, 576, 720, 960, 1080, 1152, 1440, 2160, 2880, 4320, 5040, 5760, 7200, 8640, 10080, 11520, 12960, 14400, 15120, 17280, 20160, 25920It's easy at first sight to confuse highly factorable with highly composite. However, the terms are not the same. WolframMathWorld defines the latter as:
Highly composite numbers are numbers such that the divisor function$$d(n)=\sigma_0(n)$$In other words, the number of divisors of \(n\) is greater than for any smaller \(n\).Figure 1 shows a list of the first 38 highly factorisable numbers and their factorisation. Double click the image to enlarge it.
Figure 1 |
As can be seen, 25920 does not appear on the list. This is because highly factorable numbers are characterised by the size of their multiplicative partitions (the number of ways in which a positive integer n can be expressed as a product of integers (each greater than 1). The OEIS comments for the sequence A033833 give examples for the initial terms. See Figure 2.
Figure 2 |
Clearly there is an overlap between between the highly composite and highly factorable numbers but notice that 2 and 6 are missing in the latter. Figure 3 shows a more comprehensive list of the initial highly factorable numbers and their factorisations, obtained from a 1981 paper with Paul Erdos as one of the three contributing authors.
Figure 3 |
Looking at Figure 3, it can be seen that 25920 sets a record as being able to be represented in 1386 different ways. In other words the size of its multiplicative partition is 1386. This article titled "Additive and Multiplicative Partitions" looks, as its title suggests, at the both types of partitions but no formula for calculating the size of multiplicative partitions emerged. This article title "Multiplicative Partitions" attempts an explanation of the topic and begins:
A phenomenal amount of research has been conducted on the additive partition function over the last 100 years, with striking classical results due to Hardy, Ramanujan, and others. In contrast, the topic of multiplicative partitions — sometimes referred to as “factorisatio numerorum” — has received little attention. Counting the number of multiplicative partitions is a natural question since it lies between the two most common questions concerning primes: “Is \(n\) prime?” and “What is the prime factorization of \(n\)?”
However, the algorithms that the paper came up with were a little beyond my comprehension. I was hoping to find a SageMath or a Python program that would generate the size of the multiplicative partition of any given integer. In my post of Monday, 11th November 2019, I made mention of these sorts of partitions in the context of Bell numbers:
Factorisations
That works for numbers like 30 but it's no good when the factors are not square free as in 25920. There is a Dirichlet series generating function \(f(s)\) that can be used for this purpose but I don't understand it: $$f(s)=\sum_{n=1}^{\infty}\frac{a_n}{n^s}=\prod_{k=2}^{\infty}\frac{1}{1-k^{-s}}$$I guess I'll keep investigating this matter and more to this post, if and when I discover something.If a number \(N\) is a square-free positive integer (meaning that it is the product of some number \(n\) of distinct prime numbers), then Bn gives the number of different multiplicative partitions of \(N\). These are factorisations of N into numbers greater than one, treating two factorisations as the same if they have the same factors in a different order. For instance, 30 is the product of the three primes 2, 3, and 5, and has \(B_3\) = 5 factorisations: 30 = 2×15 = 3×10 = 5×6 = 2×3×5
No comments:
Post a Comment