Showing posts with label primorials. Show all posts
Showing posts with label primorials. Show all posts

Monday, 30 July 2018

Practical Numbers

Today I turned 25320 days old but I accidentally entered 25230 into the OEIS and discovered that it was a practical number, specifically one that formed the central member of a triple of practical numbers. It is a number \(n\) such that \(n-2\), \(n\), \(n+2\) are all practical numbers (OEIS A287682). So in this case, the other members of the triple are 25228 and 25232. This is not a common occurrence as can be seen by the initial members of the sequence:
4, 6, 18, 30, 198, 306, 462, 702, 1482, 2550, 3330, 4422, 5778, 6102, 6498, 9042, 11178, 11778, 14418, 15498, 17298, 17442, 19458, 20862, 21582, 22878, 23322, 23550, 25230, ...
This led me to investigate what characterised a practical number and during that process I realised that I'd wrongly entered my number of the day. However, as it turns out 24320 is also a practical number but not a member of a triplet (the next entry in OEIS A287682 is 26622). I was encouraged to continue my investigations. According to Wikipedia:
In number theory, a practical number or panarithmic number is a positive integer \(n\) such that all smaller positive integers can be represented as sums of distinct divisors of \(n\). For example, 12 is a practical number because all the numbers from 1 to 11 can be expressed as sums of its divisors 1, 2, 3, 4, and 6: as well as these divisors themselves, we have 5 = 3 + 2, 7 = 6 + 1, 8 = 6 + 2, 9 = 6 + 3, 10 = 6 + 3 + 1, and 11 = 6 + 3 + 2.
The practical numbers themselves are rather frequent. OEIS A005153 lists these initial practical numbers:
1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 64, 66, 72, 78, 80, 84, 88, 90, 96, 100, 104, 108, 112, 120, 126, 128, 132, 140, 144, 150, 156, 160, 162, 168, 176, 180, 192, 196, 198, 200, 204, 208, 210, 216, 220, 224, 228, 234, 240, 252, ...
As can be seen, all except 1 are multiples of 2 and this is one condition for a number being practical. The fully rigorous statement of what determines a practical number would be:

A positive integer greater than one with prime factorisation
\(n=p_1^{\alpha_1} \dots p_k^{\alpha_k}\) (with the primes in sorted order) is practical if and only if each of its prime factors \(p_i \) is small enough for \(p_i-1 \) to have a representation as a sum of smaller divisors. For this to be true, the first prime \(p_1 \) must equal 2 and, for every \(i \) from 2 to \( k \), each successive prime \(p_i \) must obey the inequality:$$ p_i\leq1+\sigma(p_1^{\alpha_1}p_2^{\alpha_2}\dots p_{i-1}^{\alpha_{i-1}})=1+\prod_{j=1}^{i-1}\frac{p_j^{\alpha_j+1}-1}{p_j-1}$$where \( \sigma(x) \) denotes the sum of the divisors of \(x\). For example, 2 × 3^2 × 29 × 823 = 429606 is practical, because the inequality above holds for each of its prime factors: 3 ≤ \(\ \sigma \)(2) + 1 = 4, 29 ≤ \( \sigma \)(2 × 3^2) + 1 = 40, and 823 ≤ \(\sigma \)(2 × 3^2 × 29) + 1 = 1171.

on August 1st 2021

With some difficulty I developed some SAGE code to calculate the practical numbers contained in a given range. The example at the end of this post is for the range from 26400 to 26500. It includes multiples of 2 because all powers of 2 are practical numbers along with all perfect numbers and primorials. Such numbers are not merely of interest to recreational mathematicians. They are of interest to professional mathematicians because many of their properties are similar to the properties of the prime numbers.

Sunday, 1 April 2018

Highly Composite Numbers

Today I turned 25200 days old and I was surprised to find that this number has a staggering 347 entries in the Online Encyclopaedia of Integer Sequences (OEIS). Most numbers of this size are lucky to have more than a dozen entries. So what's so special about 25200? Well, it turns out to be a highly composite number, a term first coined by Ramanujan in 1915 and defined as a number that sets a record for the highest number of factors (in this case 90). Here is a table from Wikipedia showing details for the first 38 highly composite numbers (sequence A002182 in the OEIS).
OrderHCN
n
prime
factorization
prime
exponents
prime
factors
d(n)primorial
factorization
1101
22112
34223
461,124
5122,136
6243,148
7362,249
8484,1510
9602,1,1412
101203,1,1516
111802,2,1518
122404,1,1620
133603,2,1624
147204,2,1730
158403,1,1,1632
1612602,2,1,1636
1716804,1,1,1740
1825203,2,1,1748
1950404,2,1,1860
2075603,3,1,1864
21100805,2,1,1972
22151204,3,1,1980
23201606,2,1,11084
24252004,2,2,1990
25277203,2,1,1,1896
26453604,4,1,110100
27504005,2,2,110108
28554404,2,1,1,19120
29831603,3,1,1,19128
301108805,2,1,1,110144
311663204,3,1,1,110160
322217606,2,1,1,111168
332772004,2,2,1,110180
343326405,3,1,1,111192
354989604,4,1,1,111200
365544005,2,2,1,111216
376652806,3,1,1,112224
387207204,2,1,1,1,110240
All highly composite numbers are products of primorials as can be see from rightmost column of the table. In the case of 25200, the primorial factorisation is \( 2^2 \times 30 \times 210 \). There is a formula for calculating the number of factors for a number n:$$ \text{If }n=\prod_{i=1}^k p_i \, c^i \text{ then } d(n)=\prod_{i=1}^k (c^i+1)$$For example: $$ 25200=2^4\cdot 3^2\cdot 5^2\cdot 7 $$ $$ d(25200)=(4+1) \cdot (2+1) \cdot (2+1) \cdot (1+1) = 5 \cdot 3 \cdot 3 \cdot 2 = 90 $$The sequence of indices is non-increasing when the prime factor bases are placed in ascending order (4, 2, 2, 1 in the case of 25200). The final index is always 1 except in the cases of 4 and 36 where it is 2, thus making 1, 2 and 4 the only square, highly composite numbers.