Smooth number
A smooth number in a barrier is a natural number whose prime factorization not primes occur that are greater than the limit. We call such a number as - smooth.
A natural number is called potency- smooth with respect to a barrier, if present in their prime factorization only prime powers less than or equal. That is, for each prime factor, the occurrences of the following applies:
Examples
Let us examine, for example, the number 720 ( prime factorization: 720 = 24 · 32 · 5):
- She is 5 - smooth, six - smooth, ...
- But not 3 or 4 smooth - smooth ( because of the 5 as a prime factor )
- It is also 16- potency smooth, 17- potency smooth, ...
- But not 15 - potency smooth ( as in the prime factorization of the 2 in the 4.Potenz (= 16 ) occurs, so that the limit is exceeded 15)
8- smooth
- Are, for example, 3, 4, 5, 12, 14, or 120
- But not 11 or 26
8- potency smooth
- Are, for example, 3, 4, 5, 12, 56, or 840 ( = 23 x 3 x 5 x 7)
- But not 9 ( = 32) or 16 ( = 24)
Notes:
- When a prime number, the next larger prime number and the amount of smooth - numbers is equal to the amount of smooth - numbers.
- 2- smooth numbers correspond to the powers of two.
- As a " one - smooth" can be considered the number one formally.
Properties
For every natural number there is a unique prime factorization. That means for every exists and primes, and multiplicities so that the following holds
Now we define
For each and the number a is g - smooth and z- potency smooth for everyone and is the number a neither smooth nor g - z- potency smooth.
7- smooth numbers
7- smooth ( smooth or 7 ) numbers are those which consist solely of powers of prime factors 2, 3, 5 and 7, for example 1372 = 22 · 73
An often interchangeably used term is highly composite numbers, where 7 - smooth numbers differ from the actual mathematical concept of high Composite number that allows all prime factors and other conditions is to it.
Since the primes 2, 3, 5 and 7 in the oriented on light divisibility out vormetrischen, old weights and measures occur ( eg 1 Nuremberg pharmacist Gran = 19600 Nuremberg Graen = 980 Nuremberg scruples = 3 Karl pounds ), plays this episode in research the historical metrology a role. (see Nippur cubit, Karl pounds, pharmacists weight)
The numbers of the 7- smooth numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42 ... found sequence A002473 in OEIS under the designation " highly composite numbers (2)" (Highly composite numbers (2): numbers Whose prime divisors are all < = 7 )
Method
The quadratic sieve, a factorization is based on the factorization of quadratic residues. This decomposition can be performed easily for smooth numbers. It is also of interest to determine for many numbers at once its greatest smooth divisor (and possibly to analyze their residual factors on). Daniel Bernstein developed an efficient method for this purpose that any smooth prime factor determined for a set of unsegmented natural numbers by means of group-wise multiplications and most economical organization of each individual number without performing test division with the primes in question. The method uses only well-known fast algorithms for multiplication, division without remainder and computing the greatest common divisor of two natural numbers.
Follow smooth numbers
For each barrier, the corresponding - smooth numbers form a sequence. Under the On- Line Encyclopedia of Integer Sequences ( OEIS ) this effect for small barriers are available:
- 2- smooth numbers: sequence A000079 in OEIS - all powers of two
- 3- smooth numbers: sequence A003586 in OEIS - numbers of the form
- 5 - smooth numbers: sequence A051037 in OEIS - numbers of the form
- 7- smooth numbers: sequence A002473 in OEIS - ...
- 11- smooth numbers: A51038 sequence in OEIS
- 13 - smooth numbers: A80197 sequence in OEIS
- 17- smooth numbers: A80681 sequence in OEIS
- 19 - smooth numbers: A80682 sequence in OEIS
- 23- smooth numbers: A80683 sequence in OEIS