Even number

An even number with respect to a bound is a natural number whose prime factorization does not contain any prime numbers that are larger than the bound. Such a number is also called -smooth. ${\displaystyle S}$ ${\displaystyle S}$

A natural number is called power smooth with respect to a bound if its prime factorization only contains prime powers less than or equal . This means that for every prime factor that occurs, the following applies: ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle q}$ ${\displaystyle a_{q}}$

${\displaystyle q^{a_{q}}\leq S}$.

Examples

For example, let's examine the number 720 (prime factorization: 720 = 2 ⁴ 3 ² 5):

• it is 5-smooth, 6-smooth ...
• but not 3-smooth or 4-smooth (because of the 5 as the prime factor, since 5 is greater than 3 and 4)
• it is also 16-power smooth, 17-power smooth ...,
• but not 15-power smooth (since in the prime factorization the 2 occurs to the 4th power (= 16), which means that the limit 15 is exceeded)

In the following we consider the number 8 as a limit .

8-smooth

• are z. B. 3, 4, 5, 12, 14 or 120
• but not 11 or 26

8-power smooth

• are z. B. 3, 4, 5, 12, 56 or 840 (= 2 ³ 3 5 7)
• but not 9 (= 3 ² ) or 16 (= 2 ⁴ )

Hints:

• If a prime number is the next larger prime number and , the set of -even numbers is equal to the set of -even numbers. ${\displaystyle p}$ ${\displaystyle p_{2}}$ ${\displaystyle p\leq n<p_{2}}$ ${\displaystyle n}$ ${\displaystyle p}$
• 2-even numbers correspond to the powers of two .
• Formally, the number 1 can be regarded as "1-smooth".

properties

There is a unique prime factorization for every natural number. That is, for each there exists and primes , as well as multiples such that it holds ${\displaystyle a\in \mathbb {N} }$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle q_{1},\dots ,q_{n}\in \mathbb {P} }$ ${\displaystyle a_{1},\dots ,a_{n}\in \mathbb {N} }$

${\displaystyle a=\prod _{i=1}^{n}q_{i}^{a_{i}}}$

Now let's define

${\displaystyle g(a):=\max\{q_{i};i=1,\dots ,n\}}$

${\displaystyle z(a):=\max\{q_{i}^{a_{i}};i=1,\dots ,n\}}$

For every and the number is -smooth and -potentially smooth, for all and the number is neither -smooth nor -potentially smooth. ${\displaystyle g\geq g(a)}$ ${\displaystyle z\geq z(a)}$ ${\displaystyle a}$ ${\displaystyle g}$ ${\displaystyle z}$ ${\displaystyle g<g(a)}$ ${\displaystyle z<z(a)}$ ${\displaystyle a}$ ${\displaystyle g}$ ${\displaystyle z}$

7 even numbers

Even 7 (or 7 even ) numbers are those that consist exclusively of powers of the prime factors 2, 3, 5 and 7, for example 1372 = 2 ² · 7 ³ .

A term that is often used synonymously is highly composed numbers , with 7-even numbers differing from the actual mathematical concept of the highly composed number , which allows all prime factors and places further conditions on them.

Since the prime numbers 2, 3, 5 and 7 appear in the pre-metric, old measures and weights , which are oriented towards easy divisibility (e.g. 1 Nuremberg apothecary gran = 19600 Nürnberger gran = 980 Nuremberg scruple = 3 Karl pound), this sequence also plays a role in research on historical metrology . (see also Nippur-Elle , Karlspfund , pharmacist weight )

The sequence of the 7 even 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 ... can be found under sequence A002473 in OEIS with the designation "highly composite numbers (2)" ( Highly composite numbers (2): numbers whose prime divisors are all <= 7. )

Procedure

The quadratic sieve , a factoring technique , is based on the prime factorization of quadratic residues . This decomposition can easily be done for even numbers. It is also of interest to determine the greatest smooth factor for many numbers at once (and possibly to analyze their residual factors further). For this purpose,
Daniel Bernstein developed an efficient method that determines every smooth prime factor of every single number for a set of undecomposed natural numbers by means of group-wise multiplications and the most economical organization, without performing test divisions with the prime numbers in question. The method only uses known fast algorithms for multiplication, division without remainder and calculation of the greatest common divisor of two natural numbers.

Sequences of even numbers

For each bound the corresponding -even numbers form a sequence . The On-Line Encyclopedia of Integer Sequences (OEIS) provides these sequences for small barriers: ${\displaystyle S}$ ${\displaystyle S}$

• 02- even numbers: sequence A000079 in OEIS - all powers of two ${\displaystyle 2^{x}}$
• 03 even numbers: Sequence A003586 in OEIS - numbers of the form ${\displaystyle 2^{x}\cdot 3^{y}}$
• 05 even numbers: Sequence A051037 in OEIS - numbers of the form ${\displaystyle 2^{x}\cdot 3^{y}\cdot 5^{z}}$
• 07- even numbers: sequence A002473 in OEIS - ...
• 11- even numbers: Follow A51038 in OEIS
• Even numbers 13: Sequence A80197 in OEIS
• 17- even numbers: sequence A80681 in OEIS
• 19- even numbers: sequence A80682 in OEIS
• 23 even numbers: Sequence A80683 in OEIS

literature

• Carl Pomerance : The role of smooth numbers in number theoretical algorithms. (PDF; 8.3 MB) Proc. Int. Congr. Mathematicians, Zurich 1994, Birkhauser Verlag, Basel, 1995, pp. 411-422
• Andrew Granville : Smooth numbers: computational number theory and beyond. (PDF; 403 kB) In: Algorithmic Number Theory. MSRI Publications 44 (2008) pp. 267-323

Web links

• Eric W. Weisstein : Smooth Number . In: MathWorld (English).

Individual evidence

1. ↑ D. Bernstein: How to find smooth parts of integers. Draft for Math. Comput., PDF file