practical number
{{short description|Number whose sums of distinct divisors represent all smaller numbers}}
File:Practical number Cuisenaire rods 12.png
In number theory, a practical number or panarithmic number{{harvtxt|Margenstern|1991}} cites {{harvtxt|Robinson|1979}} and {{harvtxt|Heyworth|1980}} for the name "panarithmic numbers". is a positive integer such that all smaller positive integers can be represented as sums of distinct divisors of . 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 sequence of practical numbers {{OEIS|A005153}} begins
{{bi|left=1.6|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....}}
Practical numbers were used by Fibonacci in his Liber Abaci (1202) in connection with the problem of representing rational numbers as Egyptian fractions. Fibonacci does not formally define practical numbers, but he gives a table of Egyptian fraction expansions for fractions with practical denominators.{{harvtxt|Sigler|2002}}.
The name "practical number" is due to {{harvtxt|Srinivasan|1948}}. He noted that "the subdivisions of money, weights, and measures involve numbers like 4, 12, 16, 20 and 28 which are usually supposed to be so inconvenient as to deserve replacement by powers of 10." His partial classification of these numbers was completed by {{harvtxt|Stewart|1954}} and {{harvtxt|Sierpiński|1955}}. This characterization makes it possible to determine whether a number is practical by examining its prime factorization. Every even perfect number and every power of two is also a practical number.
Practical numbers have also been shown to be analogous with prime numbers in many of their properties.{{harvtxt|Hausman|Shapiro|1984}}; {{harvtxt|Margenstern|1991}}; {{harvtxt|Melfi|1996}}; {{harvtxt|Saias|1997}}.
Characterization of practical numbers
The original characterisation by {{harvtxt|Srinivasan|1948}} stated that a practical number cannot be a deficient number, that is one of which the sum of all divisors (including 1 and itself) is less than twice the number unless the deficiency is one. If the ordered set of all divisors of the practical number is with and , then Srinivasan's statement can be expressed by the inequality
In other words, the ordered sequence of all divisors
This partial characterization was extended and completed by {{harvtxt|Stewart|1954}} and {{harvtxt|Sierpiński|1955}} who showed that it is straightforward to determine whether a number is practical from its prime factorization.
A positive integer greater than one with prime factorization (with the primes in sorted order
:
where
The condition stated above is necessary and sufficient for a number to be practical. In one direction, this condition is necessary in order to be able to represent
More strongly, if the factorization of
- By induction on
j\in[1,\alpha_k] , it can be shown thatp_k^j\leq 1+\sigma(n/p_k^{\alpha_k-(j-1)}) . Hencep_k^{\alpha_k}\leq 1+\sigma(n/p_k) . - Since the internals
[q p_k^{\alpha_k}, q p_k^{\alpha_k}+\sigma(n/p_k)] cover[1,\sigma(n)] for1\leq q\leq \sigma(n/p_k^{\alpha_k}) , there are such aq and somer\in[0,\sigma(n/p_k)] such thatm=q p_k^{\alpha_k}+r . - Since
q\le\sigma(n/p_k^{\alpha_k}) andn/p_k^{\alpha_k} can be shown by induction to be practical, we can find a representation of q as a sum of divisors ofn/p_k^{\alpha_k} . - Since
r\le \sigma(n/p_k) , and sincen/p_k can be shown by induction to be practical, we can find a representation of r as a sum of divisors ofn/p_k . - The divisors representing r, together with
p_k^{\alpha_k} times each of the divisors representing q, together form a representation of m as a sum of divisors ofn .
Properties
- The only odd practical number is 1, because if
n is an odd number greater than 2, then 2 cannot be expressed as the sum of distinct divisors {{nowrap|ofn .}} More strongly, {{harvtxt|Srinivasan|1948}} observes that other than 1 and 2, every practical number is divisible by 4 or 6 (or both). - The product of two practical numbers is also a practical number.{{sfnp|Margenstern|1991}} Equivalently, the set of all practical numbers is closed under multiplication. More strongly, the least common multiple of any two practical numbers is also a practical number.
- From the above characterization by Stewart and Sierpiński it can be seen that if
n is a practical number andd is one of its divisors thenn\cdot d must also be a practical number. Furthermore, a practical number multiplied by power combinations of any of its divisors is also practical. - In the set of all practical numbers there is a primitive set of practical numbers. A primitive practical number is either practical and squarefree or practical and when divided by any of its prime factors whose factorization exponent is greater than 1 is no longer practical. The sequence of primitive practical numbers {{OEIS|A267124|}} begins
{{bi|left=3.2|1, 2, 6, 20, 28, 30, 42, 66, 78, 88, 104, 140, 204, 210, 220, 228, 260, 272, 276, 304, 306, 308, 330, 340, 342, 348, 364, 368, 380, 390, 414, 460 ...}}
- Every positive integer has a practical multiple. For instance, for every integer
n , its multiple2^{\lfloor\log_2 n\rfloor}n is practical.{{sfnp|Eppstein|2021}} - Every odd prime has a primitive practical multiple. For instance, for every odd prime
p , its multiple2^{\lfloor\log_2 p\rfloor}p is primitive practical. This is because2^{\lfloor\log_2 p\rfloor}p is practical{{sfnp|Eppstein|2021}} but when divided by 2 is no longer practical. A good example is a Mersenne prime of the form2^p-1 . Its primitive practical multiple is2^{p-1}(2^p-1) which is an even perfect number.
Relation to other classes of numbers
Several other notable sets of integers consist only of practical numbers:
- From the above properties with
n a practical number andd one of its divisors (that is,d|n ) thenn\cdot d must also be a practical number therefore six times every power of 3 must be a practical number as well as six times every power of 2. - Every power of two is a practical number. Powers of two trivially satisfy the characterization of practical numbers in terms of their prime factorizations: the only prime in their factorizations, p1, equals two as required.
- Every even perfect number is also a practical number. This follows from Leonhard Euler's result that an even perfect number must have the form
2^{k-1}(2^k-1) . The odd part of this factorization equals the sum of the divisors of the even part, so every odd prime factor of such a number must be at most the sum of the divisors of the even part of the number. Therefore, this number must satisfy the characterization of practical numbers. A similar argument can be used to show that an even perfect number when divided by 2 is no longer practical. Therefore, every even perfect number is also a primitive practical number. - Every primorial (the product of the first
i primes, for somei ) is practical. For the first two primorials, two and six, this is clear. Each successive primorial is formed by multiplying a prime numberp_i by a smaller primorial that is divisible by both two and the next smaller prime,p_{i-1} . By Bertrand's postulate,p_i<2p_{i-1} , so each successive prime factor in the primorial is less than one of the divisors of the previous primorial. By induction, it follows that every primorial satisfies the characterization of practical numbers. Because a primorial is, by definition, squarefree it is also a primitive practical number. - Generalizing the primorials, any number that is the product of nonzero powers of the first
k primes must also be practical. This includes Ramanujan's highly composite numbers (numbers with more divisors than any smaller positive integer) as well as the factorial numbers.{{harvtxt|Srinivasan|1948}}.
Practical numbers and Egyptian fractions
If
Fibonacci, in his 1202 book Liber Abaci lists several methods for finding Egyptian fraction representations of a rational number. Of these, the first is to test whether the number is itself already a unit fraction, but the second is to search for a representation of the numerator as a sum of divisors of the denominator, as described above. This method is only guaranteed to succeed for denominators that are practical. Fibonacci provides tables of these representations for fractions having as denominators the practical numbers 6, 8, 12, 20, 24, 60, and 100.
{{harvtxt|Vose|1985}} showed that every rational number
According to a September 2015 conjecture by Zhi-Wei Sun,{{citation |first=Zhi-Wei|last=Sun|url=http://maths.nju.edu.cn/~zwsun/UnitFraction.pdf |title=A Conjecture on Unit Fractions Involving Primes |access-date=2016-11-22 |archive-date=2018-10-19 |archive-url=https://web.archive.org/web/20181019140138/http://maths.nju.edu.cn/~zwsun/UnitFraction.pdf |url-status=dead }} every positive rational number has an Egyptian fraction representation in which every denominator is a practical number. The conjecture was proved by {{harvs|first=David|last=Eppstein|author-link=David Eppstein|year=2021|txt}}.
Analogies with prime numbers
One reason for interest in practical numbers is that many of their properties are similar to properties of the prime numbers.
Indeed, theorems analogous to Goldbach's conjecture and the twin prime conjecture are known for practical numbers: every positive even integer is the sum of two practical numbers, and there exist infinitely many triples of practical numbers
Let
{{harvtxt|Margenstern|1991}} conjectured that
Improving on an estimate of {{harvtxt|Tenenbaum|1986}}, {{harvtxt|Saias|1997}} found that
{{harvtxt|Weingartner|2015}} proved Margenstern's conjecture. We have{{harvtxt|Weingartner|2015}} and Remark 1 of {{harvtxt|Pomerance|Weingartner|2021}}
where
where
As with prime numbers in an arithmetic progression, given two natural numbers
we have{{harvtxt|Weingartner|2021}}
|\{ n \le x: n \text{ practical and } n\equiv a \bmod q \}|=\frac{c_{q,a} x}{\log x} +O_q\left(\frac{x}{(\log x)^2}\right).
The constant factor
If
For example, about 38.26% of practical numbers have a last decimal digit of 0, while the last digits of 2, 4, 6, 8 each occur with the same relative frequency of 15.43%.
The number of prime factors, the number of divisors, and the sum of divisors
The Erdős–Kac theorem implies that for a large random integer
As a consequence, most large integers
The average value of the sum-of-divisors function
Notes
{{reflist|30em}}
References
{{refbegin|30em}}
- {{citation|title=Egyptian fractions with denominators from sequences closed under doubling|first=David|last=Eppstein|journal=Journal of Integer Sequences|volume=24|page=21.8.8|url=https://cs.uwaterloo.ca/journals/JIS/VOL24/Eppstein/eppstein2.html|arxiv=2109.12217|year=2021}}
- {{citation
| last1 = Erdős | first1 = Paul | author1-link = Paul Erdős
| last2 = Loxton | first2 = J. H.
| doi = 10.1017/S144678870001243X
| journal = Journal of the Australian Mathematical Society, Series A
| pages = 319–331
| issue = 3
| title = Some problems in partitio numerorum
| volume = 27
| year = 1979| doi-access = free
}}.
- {{citation
| last = Heyworth | first = M. R.
| issue = 1
| journal = New Zealand Math. Mag.
| pages = 24–28
| title = More on panarithmic numbers
| volume = 17
| year = 1980}}. As cited by {{harvtxt|Margenstern|1991}}.
- {{citation
| last1 = Hausman | first1 = Miriam | last2 = Shapiro | first2 = Harold N.
| title = On practical numbers
| journal = Communications on Pure and Applied Mathematics
| volume = 37
| year = 1984
| issue = 5
| pages = 705–713
| mr = 0752596
| doi = 10.1002/cpa.3160370507}}.
- {{citation
| last = Margenstern | first = Maurice
| issue = 18
| journal = Comptes Rendus de l'Académie des Sciences, Série I
| pages = 895–898
| title = Résultats et conjectures sur les nombres pratiques
| volume = 299
| year = 1984}}. As cited by {{harvtxt|Margenstern|1991}}.
- {{citation
| last = Margenstern | first = Maurice
| title = Les nombres pratiques: théorie, observations et conjectures
| journal = Journal of Number Theory
| volume = 37
| year = 1991
| issue = 1
| pages = 1–36
| mr = 1089787
| doi = 10.1016/S0022-314X(05)80022-8| doi-access = free
}}.
- {{citation
| author-link = Giuseppe Melfi | last = Melfi | first = Giuseppe
| title = A survey on practical numbers
| journal = Rend. Sem. Mat. Univ. Pol. Torino
| volume = 53
| year = 1995
| issue = 4
| pages = 347–359
}}.
- {{citation
| last = Melfi | first = Giuseppe
| title = On two conjectures about practical numbers
| journal = Journal of Number Theory
| volume = 56
| year = 1996
| issue = 1
| pages = 205–210
| mr = 1370203
| doi = 10.1006/jnth.1996.0012| doi-access = free
}}.
- {{citation
| last1 = Mitrinović | first1 = Dragoslav S.
| last2 = Sándor | first2 = József
| last3 = Crstici | first3 = Borislav
| contribution = III.50 Practical numbers
| isbn = 978-0-7923-3823-9
| pages = 118–119
| publisher = Kluwer Academic Publishers
| series = Mathematics and its Applications
| title = Handbook of number theory, Volume 1
| volume = 351
| year = 1996}}.
- {{citation
| last1 = Pomerance | first1 = C.
| last2 = Weingartner | first2 = A.
| journal = Ramanujan Journal
| pages = 981–1000
| title = On primes and practical numbers
| volume = 57
| issue = 3
| year = 2021
| doi = 10.1007/s11139-020-00354-y
| arxiv = 2007.11062
| s2cid = 220686445
}}.
- {{citation
| last = Robinson | first = D. F.
| issue = 2
| journal = New Zealand Math. Mag.
| pages = 47–52
| title = Egyptian fractions via Greek number theory
| volume = 16
| year = 1979}}. As cited by {{harvtxt|Margenstern|1991}} and {{harvtxt|Mitrinović|Sándor|Crstici|1996}}.
- {{citation
| last = Saias | first = Eric
| title = Entiers à diviseurs denses, I
| journal = Journal of Number Theory
| volume = 62
| issue = 1
| year = 1997
| pages = 163–191
| mr = 1430008
| doi = 10.1006/jnth.1997.2057| doi-access = free
}}.
- {{citation
| author-link = Carlo Sanna | last = Sanna | first = Carlo
| title = Practical numbers in Lucas sequences
| journal = Quaestiones Mathematicae
| volume = 42
| year = 2019
| issue = 7
| pages = 977–983
| doi = 10.2989/16073606.2018.1502697
| url = https://doi.org/10.2989/16073606.2018.1502697
| hdl = 2318/1676275
| hdl-access = free
}}.
- {{citation
| title = Fibonacci's Liber Abaci
| last = Sigler | first = Laurence E. (trans.)
| publisher = Springer-Verlag
| year = 2002
| isbn = 0-387-95419-8
| pages = 119–121}}.
- {{citation
| last = Sierpiński | first = Wacław | author-link = Wacław Sierpiński
| doi = 10.1007/BF02410762
| issue = 1
| journal = Annali di Matematica Pura ed Applicata
| pages = 69–74
| title = Sur une propriété des nombres naturels
| volume = 39
| year = 1955| s2cid = 121592840 | doi-access = free
}}.
- {{citation
| last = Srinivasan | first = A. K.
| title = Practical numbers
| journal = Current Science
| volume = 17
| year = 1948
| pages = 179–180
| mr = 0027799
| url = http://www.currentscience.ac.in/Downloads/article_id_017_06_0179_0180_0.pdf
| archive-url = https://web.archive.org/web/20160305195057/http://www.currentscience.ac.in/Downloads/article_id_017_06_0179_0180_0.pdf
| archive-date = 2016-03-05
| url-status = dead}}.
- {{citation
| last = Stewart | first = B. M. | author-link = Bonnie Stewart
| title = Sums of distinct divisors
| journal = American Journal of Mathematics
| volume = 76
| year = 1954
| pages = 779–785
| mr = 0064800
| doi = 10.2307/2372651
| jstor = 2372651
| issue = 4
| publisher = The Johns Hopkins University Press}}.
- {{citation
| last1 = Tenenbaum | first1 = G. | author1-link = Gérald Tenenbaum
| mr = 0860809
| journal = Ann. Sci. Éc. Norm. Supér. |series=Série 4
| pages = 1–30
| issue = 1
| title = Sur un problème de crible et ses applications
| volume = 19
| year = 1986| doi = 10.24033/asens.1502 | doi-access = free
}}.
- {{citation
| last1 = Tenenbaum | first1 = G. | author1-link = Gérald Tenenbaum
| last2 = Yokota | first2 = H.
| doi = 10.1016/0022-314X(90)90109-5
| mr = 1057319
| journal = Journal of Number Theory
| pages = 150–156
| issue = 2
| title = Length and denominators of Egyptian fractions
| volume = 35
| year = 1990| doi-access = free
}}.
- {{citation
| last1 = Tenenbaum | first1 = G. | author1-link = Gérald Tenenbaum
| last2 = Weingartner | first2 = A.
| doi = 10.1093/qmath/haae002
| mr = 4732950
| journal = The Quarterly Journal of Mathematics
| pages = 161–195
| issue = 1
| title = An Erdős-Kac theorem for integers with dense divisors
| volume = 75
| year = 2024
| arxiv = 2211.05819
}}.
- {{citation
| last = Vose | first = M.
| doi = 10.1112/blms/17.1.21
| mr = 0766441
| journal = Bulletin of the London Mathematical Society
| page = 21
| title = Egyptian fractions
| issue = 1
| volume = 17
| year = 1985}}.
- {{citation
| last = Weingartner | first = A.
| issue = 2
| journal = The Quarterly Journal of Mathematics
| pages = 743–758
| title = Practical numbers and the distribution of divisors
| volume = 66
| year = 2015
| doi = 10.1093/qmath/hav006| arxiv = 1405.2585
}}.
- {{citation
| last = Weingartner | first = A.
| journal = Mathematics of Computation
| pages = 1883–1902
| title = On the constant factor in several related asymptotic estimates
| volume = 88
| issue = 318
| year = 2019
| doi = 10.1090/mcom/3402| arxiv = 1705.06349
| s2cid = 85532616
}}.
- {{citation
| last = Weingartner | first = A.
| journal = International Journal of Number Theory
| pages = 629–638
| title = The constant factor in the asymptotic for practical numbers
| volume = 16
| issue = 3
| year = 2020
| doi = 10.1142/S1793042120500311
| arxiv = 1906.07819
| s2cid = 195069356
}}.
- {{citation
| last = Weingartner | first = A.
| journal = Proceedings of the American Mathematical Society
| pages = 4699–4708
| title = An extension of the Siegel-Walfisz theorem
| volume = 149
| issue = 11
| year = 2021
| doi = 10.1090/proc/15607
| arxiv = 2011.06627
| s2cid = 226956079
}}.
- {{citation
| last = Weingartner | first = A.
| journal = Ramanujan Journal
| pages = 447–453
| title = Somewhat smooth numbers in short intervals
| volume = 60
| issue = 2
| year = 2022
| doi = 10.1007/s11139-022-00552-w
| arxiv = 2105.13568
| s2cid = 235247868
}}.
- {{citation
| last = Weingartner | first = A.
| journal = International Journal of Number Theory
| pages = 2333–2351
| title = The mean number of divisors for rough, dense and practical numbers
| volume = 19
| issue = 10
| year = 2023
| doi = 10.1142/S1793042123501142
| arxiv = 2104.07137
}}.
{{refend}}
External links
- [http://www.dm.unipi.it/gauss-pages/melfi/public_html/pratica.html Tables of practical numbers] {{Webarchive|url=https://web.archive.org/web/20171226180416/http://www.dm.unipi.it/gauss-pages/melfi/public_html/pratica.html |date=2017-12-26 }} compiled by Giuseppe Melfi.
- {{PlanetMath |urlname=PracticalNumber |title=Practical Number}}
- {{Mathworld |urlname=PracticalNumber |title=Practical Number|mode=cs2}}
{{Divisor classes}}
{{Classes of natural numbers}}