Does anybody know of any references (old or "new books/articles/URLs"?)
or simply have heard about the ADDITIVE Eratosthenes' sieve?
The ADDITIVE version of the famous Eratosthenes' sieve is so simple and
so natural that it is quite difficult to believe that the problem is not
known in the History of Mathematics.
REMARK 1. This message is also a [HM]-part of my full NOT-[HM]-ANSWER
in reply to the Carlos Cesar de Araujo [HM]-list message as to
Super-Induction method and EA-Theorems:
Subject: [HM] Principles of induction
Date: 5 Jul 99 06:54:38 -0400 (EDT)
From: Carlos Cesar de Araujo <carlos.cesar@taskmail.com.br>
To: historia-matematica@chasque.apc.org
The question is about the following.
As is known, the classical (multiplicative) Eratosthenes' sieve is an
algorithm for the construction of the prime numbers set, say
P = {2, 3, 5, 7, 11, 13, ...}.
ERATOSTHENES' SIEVE. According to ERATOSTHENES' algorithm, they strike
out ALL MULTIPLES (k+1)p_i, k=1,2,..., where p_i is the i-th current
non-striked off number, in the series of natural numbers:
<1> 2, 3, 4, 5, 6, 7, ...
So, all NON-STRIKED OFF numbers constitute the set of prime numbers,
P = {2, 3, 5, 7, 11, 13, ...}.
Denote, as usually, the complementary set of all STRIKED OFF, non-prime
(composite) numbers by N\P, so that all natural numbers belonging to N\P
are PRODUCTS of prime numbers from P = { 2, 3, 5, 7, 11, 13, ...}.
The following is an almost word-by-word "translation" of the
CLASSICAL MULTIPLICATIVE ERATOSTHENES' algorithm into the ADDITIVE
language.
Consider an INFINITE basic sequence of INCREASING positive integers:
<2> M = {m1, m2, m3, ...},
where m1 > 1, and m_(i+1) > m_i, for all i>=1 (and, maybe, some other
restrictions on the elements).
ADDITIVE ERATOSTHENES'-like SIEVE. They strike out ALL SUMS of
elements of the basic sequence <2> from the series of natural numbers,
<1a> 1, 2, 3, ...
All NON-STRIKED OFF numbers constitute a set, say A(M), of natural
numbers that are not representable by sums of elements of the basic set
<2>, that is the set A(M) is an additive analogue of the prime numbers
set P. Denote the complementary to A(M) set as N\A(M), so that any
natural number belonging to N\A(M) is representable as a SUM of elements
of the basic set M.
By analogy with common prime numbers, introduce the following
DEFINITION 1. For every basic set M, the elements of the
corresponding set A(M) are called as ADDITIVE PRIME (with regard to the
operation of the addition) numbers generated by a given basic set, M.
The ADDITIVE ERATOSTHENES'-like SIEVE has the following interesting
and unexpected applications.
In the paper
{ A.A.Zenkin, Superinduction: A New Method For Proving General
Mathematical Statements With A Computer. - Doklady Mathematics, Vol.55,
No.3, pp. 410-413 (1997). Translated from Doklady Alademii Nauk, Vol
354, No. 5, 1997, pp. 587 - 589.
- The strict complete formulation of the SI-method and some its
applications based on the EA-Theorems with the ONLY n*, are presented in
the paper. }
one EA-Theorem is proved which gives the following ADDITIVE
ERATOSTHENES'-like SIEVE algorithm to construct any invariant sets,
Z(m,r), m=1,2,..., r=2,3,..., of Generalized Waring's Problem (GWP).
According to that algorithm, for given fixed m>=1, r>=2, they strike
out ALL SUMS of the elements of the basic series:
<3> [ (m+1)^r - m^r ], [ (m+2)^r - m^r ], [ (m+3)^r - m^r ], ... ,
in the sequence of natural numbers <1a>. All NON-STRIKED OFF numbers
constitute the corresponding invariant set, Z(m,r). They can say that
the elements of the invariant set, Z(m,r), are "additive primes"
generated by the corresponding basic set <3>. That algorithm is an
effective and constructive way to find all elements (including the ONLY,
MAXIMAL one) of the sets Z(m,r) for any m and r.
Consider the simplest
EXAMPLE: Z(1,2).
Here m=1, r=2, and consequently the basic series <3> has the form:
<3a> 3, 8, 15, 24, 35, 48, 63, 80, 99, 120, 143, ...
Applying the ADDITIVE SIEVE to the series of natural numbers, we
shall obtain:
<4> 1 2 3' 4 5 6' 7 8' 9' 10 11' 12' 13 14' 15' 16' 17' 18' 19' 20' ...
where the natural numbers with the mark " ' " are STRIKED OFF natural
numbers.
For the case m=1, r=2, the corresponding EA-Theorem states:
"IF there exists such natural number n* that Q(n*) holds, then for any
n>n* P(n) is true", or shortly
En*Q(n*) ==> A n>n* P(n)
where
Q(n*) = " n* is a NON-STRIKED OFF number which is followed by NOT LESS
THREE STRIKED OFF numbers";
P(n) = " n is a STRIKED OFF number".
Now, we look at the PICTURE <4> and SEE the VISUAL FACT: Q(13) holds,
since the number n* = 13 is followed by the THREE STRIKED OFF numbers
14,15,16. Thus, THAT VISUAL FACT PROVES the TRUTH of the SINGLE
STATEMENT:
"THERE EXISTS such the number n* that Q(n*) holds", or shortly:
En*Q(n*).
So, from
1) the PROVED SINGLE statement "En*Q(n*)"
AND
2) from the PROVED MATHEMATICAL EA-THEOREM "E n* Q(n*) ==> A n>n*
P(n)",
we deduce the authentic TRUTH of the COMMON STATEMENT "A n>n* P(n)" with
n*=13, by the MODUS PONENS rule of the Classical Aristotle's Logic.
Thus, for m=1, r=2, the set of NON-STRIKED OFF, "additive prime"
numbers is Z(1,2) = {1,2,4,5,7,10,13} -- the famous invariant set of the
Generalized Waring's Problem for the case m=1, r=2, obtained (by
absolutely other way) by the American mathematician G.Pall as far back
as 1933 {see, for example, W.Sierpinski's monograph "Elementary Theory
of Numbers", Warszaw, 1964}. It is obviously that the number n*=13 is
the ONLY threshold number as the maximal element of the FINITE set
Z(1,2) of finite natural numbers, and P(13) is false.
REMARK 2. All said above is also applicable to a lot problems of
ADDITIVE Number Theory, in particular, to the Goldbach-Waring's problem,
to the problem of the summing up of triangle, rectangular, etc.
numbers, any polynomials, and so on {see A.A.Zenkin, "Cognitive Computer
Graphics. Applications to Theory of Natural Numbers". - Moscow, "Nauka",
1991}
REMARK 3. All said above is a part of the large project
"Applications of Cognitive (Semantic) Visualization in Mathematical
Proofs. 1. The logical Nature of the EA-Theorems and the Super-Induction
method." But taking into account the financial distress of the modern
Russian science, I doubt very much of a possibility to advance and to
complete that project. Therefore all suggestions concerning a possible
collaboration as to such the project are welcome.
Best regards,
Alexander Zenkin
############################################
Prof. Alexander A. Zenkin,
Doctor of Physical and Mathematical Sciences,
Leading Research Scientist of the Computer Center
of the Russian Academy of Sciences,
Member of the Philosophical Society of the Russia,
Full-Member of the Painters Unity of the Russia.
e-mail: alexzen@com2com.ru
WEB-Site http://www.com2com.ru/alexzen
"Artistic "PI"-Number Gallery":
http://www.com2com.ru/alexzen/galery/Galery.html
############################################
"Infinitum Actu Non Datur" - Aristotle.
"Drawing is a very useful tool against the uncertainty of words" - Leibniz.