Characterization of Practical Numbers
As Stewart (1954) and Sierpiński (1955) showed, it is straightforward to determine whether a number is practical from its prime factorization. A positive integer with and primes is practical if and only if and, for every i from 2 to k,
where denotes the sum of the divisors of x. For example, 3 ≤ σ(2)+1 = 4, 29 ≤ σ(2 × 32)+1 = 40, and 823 ≤ σ(2 × 32 × 29)+1=1171, so 2 × 32 × 29 × 823 = 429606 is practical. This characterization extends a partial classification of the practical numbers given by Srinivasan (1948).
It is not difficult to prove that this condition is necessary and sufficient for a number to be practical. In one direction, this condition is clearly necessary in order to be able to represent as a sum of divisors of n. In the other direction, the condition is sufficient, as can be shown by induction. More strongly, one can show that, if the factorization of n satisfies the condition above, then any can be represented as a sum of divisors of n, by the following sequence of steps:
- Let, and let .
- Since and can be shown by induction to be practical, we can find a representation of q as a sum of divisors of .
- Since, and since can be shown by induction to be practical, we can find a representation of r as a sum of divisors of .
- The divisors representing r, together with times each of the divisors representing q, together form a representation of m as a sum of divisors of n.
Read more about this topic: Practical Number
Famous quotes containing the words practical and/or numbers:
“War-making is one of the few activities that people are not supposed to view “realistically”; that is, with an eye to expense and practical outcome. In all-out war, expenditure is all-out, unprudent—war being defined as an emergency in which no sacrifice is excessive.”
—Susan Sontag (b. 1933)
“The principle of majority rule is the mildest form in which the force of numbers can be exercised. It is a pacific substitute for civil war in which the opposing armies are counted and the victory is awarded to the larger before any blood is shed. Except in the sacred tests of democracy and in the incantations of the orators, we hardly take the trouble to pretend that the rule of the majority is not at bottom a rule of force.”
—Walter Lippmann (1889–1974)