Practical number
   HOME

TheInfoList



OR:

In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
, a practical number or panarithmic number is a positive integer n such that all smaller positive integers can be represented as sums of distinct
divisor In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
s 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 sequence of practical numbers begins Practical numbers were used by
Fibonacci Fibonacci (; also , ; – ), also known as Leonardo Bonacci, Leonardo of Pisa, or Leonardo Bigollo Pisano ('Leonardo the Traveller from Pisa'), was an Italian mathematician from the Republic of Pisa, considered to be "the most talented Western ...
in his
Liber Abaci ''Liber Abaci'' (also spelled as ''Liber Abbaci''; "The Book of Calculation") is a historic 1202 Latin manuscript on arithmetic by Leonardo of Pisa, posthumously known as Fibonacci. ''Liber Abaci'' was among the first Western books to describe ...
(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.. The name "practical number" is due to . 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 and . This characterization makes it possible to determine whether a number is practical by examining its prime factorization. Every even
perfect number In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number. T ...
and every
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negative ...
is also a practical number. Practical numbers have also been shown to be analogous with
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s in many of their properties.


Characterization of practical numbers

The original characterisation by stated that a practical number cannot be a
deficient number In number theory, a deficient number or defective number is a number ''n'' for which the sum of divisors of ''n'' is less than 2''n''. Equivalently, it is a number for which the sum of proper divisors (or aliquot sum) is less than ''n''. For ex ...
, 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 n is with d_1=1 and d_j=n, then Srinivasan's statement can be expressed by the inequality 2n\leq1+\sum_^j d_i. In other words, the ordered sequence of all divisors of a practical number has to be a complete sub-sequence. This partial characterization was extended and completed by and 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 n=p_1^...p_k^ (with the primes in sorted order p_1) 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 from 2 to , each successive prime p_i must obey the inequality :p_i\leq1+\sigma(p_1^p_2^\dots p_^)=1+\prod_^\frac, where \sigma(x) denotes the sum of the divisors of ''x''. For example, 2 × 32 × 29 × 823 = 429606 is practical, because the inequality above holds for each of its prime factors: 3 ≤ σ(2) + 1 = 4, 29 ≤ σ(2 × 32) + 1 = 40, and 823 ≤ σ(2 × 32 × 29) + 1 = 1171. 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 p_i-1 as a sum of divisors of n, because if the inequality failed to be true then even adding together all the smaller divisors would give a sum too small to reach p_i-1. In the other direction, the condition is sufficient, as can be shown by induction. More strongly, if the factorization of n satisfies the condition above, then any m \le \sigma(n) can be represented as a sum of divisors of n, by the following sequence of steps: * By induction on j\in ,\alpha_k/math>, it can be shown that p_k^j\leq 1+\sigma(n/p_k^). Hence p_k^\leq 1+\sigma(n/p_k). * Since the internals p_k^, q p_k^+\sigma(n/p_k)/math> cover ,\sigma(n)/math> for 1\leq q\leq \sigma(n/p_k^), there are such a q and some r\in ,\sigma(n/p_k)/math> such that m=q p_k^+r. * Since q\le\sigma(n/p_k^) and n/p_k^ can be shown by induction to be practical, we can find a representation of ''q'' as a sum of divisors of n/p_k^. * Since r\le \sigma(n/p_k), and since n/p_k can be shown by induction to be practical, we can find a representation of ''r'' as a sum of divisors of n/p_k. * The divisors representing ''r'', together with p_k^ times each of the divisors representing ''q'', together form a representation of ''m'' as a sum of divisors of n.


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 More strongly, 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. More strongly the
least common multiple In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bot ...
of any two practical numbers is also a practical number. Equivalently, the set of all practical numbers is closed under multiplication. *From the above characterization by Stewart and Sierpiński it can be seen that if n is a practical number and d is one of its divisors then n\cdot d must also be a practical number. *In the set of all practical numbers there is a primitive set of practical numbers. A primitive practical number is either practical and
squarefree In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, is square-fr ...
or practical and when divided by any of its prime factors whose
factorization In mathematics, factorization (or factorisation, see American and British English spelling differences#-ise, -ize (-isation, -ization), English spelling differences) or factoring consists of writing a number or another mathematical object as a p ...
exponent is greater than 1 is no longer practical. The sequence of primitive practical numbers begins *Every positive integer has a practical multiple. For instance, for every integer n, its multiple 2^n is practical.


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 and d one of its divisors (that is, d, n) then n\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 A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negative ...
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, ''p''1, equals two as required. *Every even
perfect number In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number. T ...
is also a practical number. This follows from
Leonhard Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
's result that an even perfect number must have the form 2^(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. *Every
primorial In mathematics, and more particularly in number theory, primorial, denoted by "#", is a function from natural numbers to natural numbers similar to the factorial function, but rather than successively multiplying positive integers, the function ...
(the product of the first i primes, for some i) is practical. For the first two primorials, two and six, this is clear. Each successive primorial is formed by multiplying a prime number p_i by a smaller primorial that is divisible by both two and the next smaller prime, p_. By
Bertrand's postulate In number theory, Bertrand's postulate is a theorem stating that for any integer n > 3, there always exists at least one prime number p with :n < p < 2n - 2. A less restrictive formulation is: for every n > 1, there is always ...
, p_i<2p_, 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 number __FORCETOC__ A highly composite number is a positive integer with more divisors than any smaller positive integer has. The related concept of largely composite number refers to a positive integer which has at least as many divisors as any smaller ...
s (numbers with more divisors than any smaller positive integer) as well as the
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \t ...
numbers..


Practical numbers and Egyptian fractions

If n is practical, then any
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
of the form m/n with m may be represented as a sum \sum d_i/n where each d_i is a distinct divisor of n. Each term in this sum simplifies to a
unit fraction A unit fraction is a rational number written as a fraction where the numerator is one and the denominator is a positive integer. A unit fraction is therefore the reciprocal of a positive integer, 1/''n''. Examples are 1/1, 1/2, 1/3, 1/4, 1/5, et ...
, so such a sum provides a representation of m/n as an Egyptian fraction. For instance, \frac=\frac+\frac+\frac=\frac12+\frac1+\frac1. Fibonacci, in his 1202 book ''
Liber Abaci ''Liber Abaci'' (also spelled as ''Liber Abbaci''; "The Book of Calculation") is a historic 1202 Latin manuscript on arithmetic by Leonardo of Pisa, posthumously known as Fibonacci. ''Liber Abaci'' was among the first Western books to describe ...
'' 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. showed that every rational number x/y has an Egyptian fraction representation with O(\sqrt) terms. The proof involves finding a sequence of practical numbers n_i with the property that every number less than n_i may be written as a sum of O(\sqrt) distinct divisors of n_i. Then, i is chosen so that n_, and xn_i is divided by y giving quotient q and remainder r. It follows from these choices that \frac=\frac+\frac. Expanding both numerators on the right hand side of this formula into sums of divisors of n_i results in the desired Egyptian fraction representation. use a similar technique involving a different sequence of practical numbers to show that every rational number x/y has an Egyptian fraction representation in which the largest denominator is O(y\log^2 y/\log\log y). According to a September 2015 conjecture by
Zhi-Wei Sun Sun Zhiwei (, born October 16, 1965) is a Chinese mathematician, working primarily in number theory, combinatorics, and group theory. He is a professor at Nanjing University. Biography Sun Zhiwei was born in Huai'an, Jiangsu. Sun and his twi ...
, every positive rational number has an Egyptian fraction representation in which every denominator is a practical number. The conjecture was proved by .


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 A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. Indeed, theorems analogous to
Goldbach's conjecture Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states that every even natural number greater than 2 is the sum of two prime numbers. The conjecture has been shown to hold ...
and the
twin prime conjecture A twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair (41, 43). In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term ''twin pr ...
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 (x-2,x,x+2).
Melfi Melfi (Neapolitan language, Lucano: ) is a town and ''comune'' in the Vulture area of the province of Potenza, in the Southern Italian region of Basilicata. Geographically, it is midway between Naples and Bari. In 2015 it had a population of 17,7 ...
also showed that there are infinitely many practical
Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s ; the analogous question of the existence of infinitely many
Fibonacci prime A Fibonacci prime is a Fibonacci number that is prime, a type of integer sequence prime. The first Fibonacci primes are : : 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, .... Known Fibonacci primes It is not known whet ...
s is open. showed that there always exists a practical number in the interval ^2,(x+1)^2)/math> for any positive real x, a result analogous to
Legendre's conjecture Legendre's conjecture, proposed by Adrien-Marie Legendre, states that there is a prime number between n^2 and (n+1)^2 for every positive integer n. The conjecture is one of Landau's problems (1912) on prime numbers; , the conjecture has neither ...
for primes. Moreover, for all sufficiently large x, the interval -x^,x/math> contains many practical numbers. Let p(x) count how many practical numbers are at conjectured that p(x) is asymptotic to cx/\log x for some constant c, a formula which resembles the
prime number theorem In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying ...
, strengthening the earlier claim of that the practical numbers have density zero in the integers. Improving on an estimate of , found that p(x) has order of magnitude x/\log x. proved Margenstern's conjecture. We have p(x) = \frac\left(1 + O\!\left(\frac\right)\right), where c=1.33607... Thus the practical numbers are about 33.6% more numerous than the prime numbers. The exact value of the constant factor c is given by c= \frac \sum_ \frac \Biggl( \sum_\frac - \log n\Biggr) \prod_ \left(1-\frac\right), where \gamma is the
Euler–Mascheroni constant Euler's constant (sometimes also called the Euler–Mascheroni constant) is a mathematical constant usually denoted by the lowercase Greek letter gamma (). It is defined as the limiting difference between the harmonic series and the natural l ...
and p runs over primes. As with prime numbers in an arithmetic progression, given two natural numbers a and q, we have , \, =\frac +O_q\left(\frac\right). The constant factor c_ is positive if, and only if, there is more than one practical number congruent to a \bmod q . If \gcd(q,a)=\gcd(q,b), then c_=c_. 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%.


Notes


References

* *. *. As cited by . *. *. As cited by . *. *. *. *. *. *. As cited by and . *. *. *. *. *. *. *. *. *. *. *. *. *.


External links


Tables of practical numbers
compiled by Giuseppe Melfi. * * {{Classes of natural numbers Integer sequences Egyptian fractions