Saturday, 21 March 2020

Highly Factorable Numbers

The number of OEIS (Online Encyclopaedia of Integer Sequences) entries for number close to 26000 are not numerous (typically no more than ten). So I was surprised today, having turned 25920 days old, to discover that there were 184 entries in the OEIS for the number 25920. Amongst its many properties was the following(OEIS A0338833):


    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, 25920
It'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 
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
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.

No comments:

Post a Comment