 |
Development of Algorithmic Constructions |
18:13:03
|  | | 28.Jun 2022
|
|
Prime sieving for the polynomial f(n)=n2+1
0. Abstract
1. Description of the basic algorithm
2. Programming and algorithms written in Mupad
a) Programming of the basic algorithm
b) little improvement of the basic algorithm
c) version of the basic algorithm for a better estimation
d) Improved programming for speed I, estimation of the work
e) Improved programming for speed II, second appearance instead the first
f) Improved programming for speed III, Hensel-Lifting
g) Improved programming for speed IV, Hensel-Lifting with a better limit
h) Improved programming for speed V, multiplication instead of division
i) Improved programming for speed VI, Logarithm
j) basic algorithm in the complex field for Gaussian prime elements
3. Programming and algorithms written in C / C++ for download
a) simple and easy understanding implementation
b) improved and easy understanding implementation
c) Used programm for the investigation in C with Heap, 2012
d) Used programm for the investigation in C++ with Heap, 2015
e) Used programm for the investigation in C++, 2020
4. Results of the distribution of the primes
a) Table up to 1012 and table up to 241
b) Graphic of the distribution of the primes
c) Graphic of the proportion between the "reducible" and the "big" primes
d) Graphic of the distribution of all primes concerning their huge
e) Table of the distribution of all primes concerning their second appearance
f) Comparison between the amount of primes between their 2. appearance and the primes of the form p=n2+1
g) Table of the distribution of the primes mod 6 and mod 8
5. Runtime of the algorithm
a) Table of the amount of divisions
b) Table of the use of memory
c) Estimation of the runtime
6. Mathematical theory
7. Sequences of primes and reference to Njas-Sequences
a) Primes of form n2 + 1
b) unsorted list of Primes and 1
c) Primitive prime factors of the sequence k2 + 1 in the order that they are found
d) Prime factors of numbers of the form x2 + 1 which themselves are not of this form
e) Primes congruent to 1 or 2 modulo 4; or, primes of form x2+y2; or, -1 is a square mod p
f) number of primes of the form x2 + 1 < 10n
g) number of distinct prime divisors (taken together) of numbers of the form x2+1 for x<=10n
h) Pythagorean primes: primes of form 4n + 1
i) Numbers n such that n2 + 1 is prime
8. Links
a) A Sieve Method for Factoring Numbers of the Form n2 + 1, by Daniel Shanks, 1959
b) On the Conjecture of Hardy and Littlewood concerning the Number of Primes of the form n2+a, by Daniel Shanks, 1960
c) On the Gaussian Primes on the Line Im(x)=1, by M. C. Wunderlich, 1973
d) On Primes Represented by Quadratic Polynomials, by Stephan Baier and Liangyi Zhao, 2007
e) Search for primes of the form n2 + 1 by Marek Wolf, 2010
f) Batemann Horn Conjecture
g) Gaußsche Zahl
h) Gaussian Integer from MathWorld
i) Gaussian Prime from MathWorld
0. Abstract:
There are several aspects of the following article:
Landau mentioned four "unattackable" problems during the Fifth Congress of Mathematicians in Cambridge in 1912.
One of these is the question, if there are infinitively many primes of the form p=n2+1.
This question is conjoined with the question if there are infinitively many gaussian prime elements of the form p=n+I in the complex plane.
Besides there is still the "unsettled question" "whether the reducible numbers have a definity density" (Shanks)
Daniel Shanks published 1959 a paper in which he elaborated an algorithm with the calculation of the primes up to n=180.000
The following research describes some better algorithms and some numerical results about the distribution of primes resp. of prime ideals concerning the irreducible polynomial f(n)=n²+1.
The main part in this article is the construction of several algorithms. For the illustration the progamming in Mupad was choosen. For the research
a program in C with GMP was written.
Calculation up to 238 was done 2012 in approximately 30 days on Amd Athlon 64 600e Quad-Core processor on one core with 16 Gbyte Ram and 2 Terabyte of disk space.
With some better implementation in C a calucation up to 240 was done 2015 on the same computer.
With the help of a more effectiv datastructure calculation up to 241 was done 2019 on Amd 6300 Six-Core with 32 Gbyte Ram and 2,5 Terabyte of disk space.
I offer three possibilities to understand the algorithms, a descriptive, a programming and a mathematical way.
May the reader choose the best possibility for his own.
1. Description of the basic algorithm
a) A list with the function terms f(x)=x2+1 from x=0 up to x_max is created.
b) The algorithm starts with x=0, f(0)=1, nothing is done, because the function value f(0)=1 is not a prime.
c) The x is increased by one, f(1)=2, 2 is a prime.
As x+kp and p-x+kp with k element of N, resp. 1+2k and 2-1+2k describe the same values,
the prime 2 occurs only one time periodically in this sequence as divisor.
The prime 2 is a singularity, because it divide the discriminant of f(n). All other primes occur twice peridically in the sequence.
All function values f(1+2k) are divided by 2.
d) The x is increased by one.
Let f*(x) is denoted as the function value f(x) which remains after dividing by the primes which occurs before.
if f*(x)=1 nothing is done and the step d) is repeated.
e) If p=f*(x) is a prime, it occurs peridically twice for all function values at f(x+kp) and f(p-x+kp) with k element N with x+kp < x_max and p-x+kp < x_max.
These function values are divided as often as possible by the prime so that the divisor of p is eleminiated.
f) Go to step d) untill x=x_max
Explication by example
a) Create a list from x=0 to x=list_max=100 with f(x)=x2+1
f(0)= 1
f(1)= 2
f(2)= 5
f(3)= 10 = 2*5
f(4)= 17
f(5)= 26 = 2*13
f(6)= 37
f(7)= 50 = 2*52
f(8)= 65 = 5*13
f(9)= 82 = 2*41
f(10)= 101
f(11)= 122 = 2*61
f(12)= 145 = 5*29
f(13)= 170 = 2*5*17
f(14)= 197
f(15)= 226 = 2*113
f(16)= 257
f(17)= 290 = 2*5*29
f(18)= 325 = 52*13
f(19)= 362 = 2*181
f(20)= 401
f(21)= 442 = 2*13*17
f(22)= 485 = 5*97
f(23)= 530 = 2*5*53
f(24)= 577
f(25)= 626 = 2*313
f(26)= 677
f(27)= 730 = 2*5*73
f(28)= 785 = 5*157
f(29)= 842 = 2*421
f(30)= 901 = 17*53
f(31)= 962 = 2*13*37
f(32)= 1025 = 52*41
f(33)= 1090 = 2*5*109
f(34)= 1157 = 13*89
f(35)= 1226 = 2*613
f(36)= 1297
f(37)= 1370 = 2*5*137
f(38)= 1445 = 52*17
f(39)= 1522 = 2*761
f(40)= 1601
f(41)= 1682 = 2*292
f(42)= 1765 = 5*353
f(43)= 1850 = 2*52*37
f(44)= 1937 = 13*149
f(45)= 2026 = 2*1013
f(46)= 2117 = 29*73
f(47)= 2210 = 2*5*13*17
f(48)= 2305 = 5*461
f(49)= 2402 = 2*1201
f(50)= 2501 = 41*61
f(51)= 2602 = 2*1301
f(52)= 2705 = 5*541
f(53)= 2810 = 2*5*281
f(54)= 2917
f(55)= 3026 = 2*17*89
f(56)= 3137
f(57)= 3250 = 2*53*13
f(58)= 3365 = 5*673
f(59)= 3482 = 2*1741
f(60)= 3601 = 13*277
f(61)= 3722 = 2*1861
f(62)= 3845 = 5*769
f(63)= 3970 = 2*5*397
f(64)= 4097 = 17*241
f(65)= 4226 = 2*2113
f(66)= 4357
f(67)= 4490 = 2*5*449
f(68)= 4625 = 53*37
f(69)= 4762 = 2*2381
f(70)= 4901 = 132*29
f(71)= 5042 = 2*2521
f(72)= 5185 = 5*17*61
f(73)= 5330 = 2*5*13*41
f(74)= 5477
f(75)= 5626 = 2*29*97
f(76)= 5777 = 53*109
f(77)= 5930 = 2*5*593
f(78)= 6085 = 5*1217
f(79)= 6242 = 2*3121
f(80)= 6401 = 37*173
f(81)= 6562 = 2 17 193
f(82)= 6725 = 52*269
f(83)= 6890 = 2*5*13*53
f(84)= 7057
f(85)= 7226 = 2*3613
f(86)= 7397 = 13*569
f(87)= 7570 = 2*5*757
f(88)= 7745 = 5*1549
f(89)= 7922 = 2*17*233
f(90)= 8101
f(91)= 8282 = 2*41*101
f(92)= 8465 = 5*1693
f(93)= 8650 = 2*52*173
f(94)= 8837
f(95)= 9026 = 2*4513
f(96)= 9217 = 13*709
f(97)= 9410 = 2*5*941
f(98)= 9605 = 5*17*113
f(99)= 9802 = 2*132*29
f(100)= 10001 = 73*137
(I added the factorization of the results, because it shows the periodical appearance of the primes.)
b) f(0)=1 nothing is done
c) f(1)=2, divide f(1+2k) / 2 with 1+2k<=x_max. k element N
d) f(2)=5, divide f(2+5k) / 5 as often as there is no factor 5 in the result.
You have to divide f(7), f(12), f(17), f(22), f(27), f(32), f(37), f(42), f(47), f(52), f(57), f(62) and so on by 5.
divide f(-2+5k) / 5 as often as there is no factor 5 in the result.
You have to divide f(3), f(8), f(13), f(18), f(23), f(28), f(33), f(38), f(43), f(48), f(53), f(58) and so on by 5.
e) Go for x from 3 to liste_max
if p=f*(x) > 1 (f*(x) is the prime which remains after dividing by f(1), f*(2) up to f*(x_max) )
divide f(x+kp) / p and
divide f(-x+kp) / p
as often as there is no factor p in the result.
You get an unsorted list of primes.
2. a) Programming of the basic algorithm
This is a short implementation for the algorithm concerning the polynom f(n)=n2+1.
Every prime (without the 2) which occurs is sieved out resp. divides periodically at two positions the initialised list. (for the proof see I. c), d) and e) )
The procedure sieving only divides as often as possible the function values in the list by the sieving primes.
- liste_max:=1000;
sieving:=proc (stelle, p)
// remove all presence of p from elements in liste.
// Must be called with initial value of stelle pointing to list element divisible by p.
begin
while (stelle<=liste_max) do
erg:=liste[stelle];
repeat
erg:=erg /p;
until (erg mod p>0) end_repeat;
liste[stelle]:=erg;
stelle:=stelle+p;
end_while;
end_proc;
for x from 1 to liste_max do
liste [x]:=x2+1;
end_for;
for x from 1 to liste_max do
p:=liste[x];
if (p>1) then
print (x, p);
sieving (x+p, p);
if p > 2 then
sieving (p-x, p);
end_if;
end_if;
end_for;
You get as result an unsorted list of primes.
2. b) little improvement of the basic algorithm
The initialization of the list is separated in two loops, the prime number 2 is directly sieved out by the initialization.
Therefore one if statement could be deleted.
- liste_max:=1000;
sieving:=proc (stelle, p)
// remove all presence of p from elements in liste.
// Must be called with initial value of stelle pointing to list element divisible by p.
begin
while (stelle<=liste_max) do
erg:=liste[stelle];
repeat
erg:=erg /p;
until (erg mod p>0) end_repeat;
liste[stelle]:=erg;
stelle:=stelle+p;
end_while;
end_proc;
for x from 2 to liste_max step 2 do
liste [x]:=(x2+1);
end_for;
print (1, 2);
for x from 1 to liste_max step 2 do
// No Division, only a rightshift is needed
liste [x]:=(x2+1)/2;
end_for;
for x from 2 to liste_max do
p:=liste[x];
if (p>1) then
print (x, p);
sieving (x+p, p);
sieving (p-x, p);
end_if;
end_for;
You get as result an unsorted list of primes.
2. c) version of the basic algorithm for a better estimation
The main loop for x from 1 to liste_max is divided into two loops with the same huge.
In the second loop only the second sieving part is made
because the first sieving part is redundant, as the prime p=f(x) > x (for the proof see I. f) )
- liste_max:=1000;
sieving:=proc (stelle, p)
// remove all presence of p from elements in liste.
// Must be called with initial value of stelle pointing to list element divisible by p.
begin
while (stelle<=liste_max) do
erg:=liste[stelle];
repeat
erg:=erg /p;
until (erg mod p>0) end_repeat;
liste[stelle]:=erg;
stelle:=stelle+p;
end_while;
end_proc;
for x from 2 to liste_max step 2 do
liste [x]:=(x2+1);
end_for;
for x from 1 to liste_max step 2 do
// No Division, only a rightshift is needed
liste [x]:=(x2+1)/2;
end_for;
for x from 2 to liste_max/2 do
p:=liste[x];
if (p>1) then
// print (x, p);
sieving (x+p, p);
sieving (p-x, p);
end_if;
end_for;
for x from liste_max/2+1 to liste_max do
p:=liste[x];
if (p>1) then
// print (x, p);
sieving (p-x, p);
end_if;
end_for;
2. d) Improved programming for speed I
Using that every prime p=f(x) > 2x (for the proof see I. g) ) the loop could be divide in two loops,
where the second loop contains only one sieving.
- liste_max:=10000;
sieving:=proc (stelle, p)
begin
while (stelle<=liste_max) do
erg:=liste[stelle];
repeat
erg:=erg /p;
anz_div:=anz_div+2;
until (erg mod p>0) end_repeat;
liste[stelle]:=erg;
stelle:=stelle+p;
end_while;
end_proc;
for x from 2 to liste_max step 2 do
liste [x]:=(x2+1);
end_for;
for x from 1 to liste_max step 2 do
// No Division, only a right shift is needed
liste [x]:=(x2+1)/2;
end_for;
for x from 2 to trunc (liste_max/3) do
p:=liste[x];
if (p>1) then
print (x, p);
sieving (x+p, p);
sieving (p-x, p);
end_if;
end_for;
for x from trunc (liste_max/3+1) to liste_max do
p:=liste[x];
if (p>1) then
print (x, p);
sieving (p-x, p);
end_if;
end_for;
This idea is not used in the following described algorithms.
2. e) Improved programming for speed II
Instead of sieving for the first appearance of the prime,
the sieving is made by the second appearance of the prime.
This is an improvement because less primes have to store and the numbers of divisions is less.
liste_max:=1000;
sieving:=proc (stelle, p)
begin
while (stelle<=liste_max) do
erg:=liste[stelle];
repeat
erg:=erg /p;
until (erg mod p>0) end_repeat;
liste[stelle]:=erg;
stelle:=stelle+p;
end_while;
end_proc;
for x from 2 to liste_max step 2 do
liste [x]:=(x2+1);
end_for;
for x from 1 to liste_max step 2 do
// No Division, only a right shift is needed
liste [x]:=(x2+1)/2;
end_for;
for x from 2 to liste_max do
p:=liste[x];
if (p>1) then
// This decide whether the prime occurs for the second time.
if x > p-x then
sieving (x+p, p);
sieving (2*p-x, p);
else
// The primes which occures for the first time are printed
print (x, p);
end_if;
end_if;
end_for;
2. f) Improved programming for speed III, Hensel-Lifting
Mathematical background : Hensel-Lifting for polynomials
if p(x) is a polynomial and if f | p(x1)
then the Hensel-Lifting calculates the x2, x3, ..., xn so that
f2 | p(x2)
f3 | p(x3)
...
fn | p(xn)
Using the Hensel-Lifting only one division is needed instead of one division and a modulo operation in the sieving function.
- liste_max:=1000;
f:=proc (x)
begin
return (x2+1);
end;
fd:=proc (x)
begin
return (2*x);
end;
sieving:=proc (s, p, a)
begin
while (s<=liste_max) do
liste[s]:=liste[s]/p;
s:=s+a;
end_while;
end_proc;
hensel:=proc (x, p)
begin
sieving (x+p, p, p);
sieving (2*p-x, p, p);
s:=x;
a:=p;
inv:=fd(s)^(-1) mod p;
repeat
a:=a*p;
s:=s-f(s)*inv;
s:=s mod a;
sieving (s, p, a);
sieving (a-s, p, a);
until s>liste_max and (a-s)>liste_max end_repeat;
end_proc;
for x from 2 to liste_max step 2 do
liste [x]:=(x2+1);
end_for;
for x from 1 to liste_max step 2 do
// No Division, only a right shift is needed
liste [x]:=(x2+1)/2;
end_for;
// The prime number 2 is eleminated by the initialisation
print (1, 2);
for x from 2 to liste_max-1 do
p:=liste[x];
if (p>1) then
// Second occurance of the prime
if (x > p-x) then
hensel (x, p);
else
// Primes p at position x
// print (x, p);
end_if;
end_if;
end_for;
2. g) Improved programming for speed IV, Hensel-Lifting with a better limit
Instead of the calculation the Hensel-lifting for the primes from the second appearance concerning the polynomial
the limit is decreased so that only the Hensel-lifting is made if the primes occurs for the 3. time up to the max limit
of calculation.
- liste_max:=1000;
f:=proc (x)
begin
return (x2+1);
end;
fd:=proc (x)
begin
return (2*x);
end;
sieving:=proc (s, p, a)
begin
while (s<=liste_max) do
liste[s]:=liste[s]/p;
s:=s+a;
end_while;
end_proc;
hensel:=proc (x, p)
begin
sieving (x+p, p, p);
sieving (2*p-x, p, p);
s:=x;
a:=p;
inv:=fd(s)^(-1) mod p;
repeat
a:=a*p;
s:=s-f(s)*inv;
s:=s mod a;
sieving (s, p, a);
sieving (a-s, p, a);
until s>liste_max and (a-s)>liste_max end_repeat;
end_proc;
for x from 2 to liste_max step 2 do
liste [x]:=(x2+1);
end_for;
for x from 1 to liste_max step 2 do
// No Division, only a right shift is needed
liste [x]:=(x2+1)/2;
end_for;
// The prime number 2 is eleminated by the initialisation
print (1, 2);
for x from 2 to liste_max-1 do
p:=liste[x];
if (p>1) then
// Second occurance of the prime
if (x > p-x) then
// 3. appearance of the prime
if ((2*p-x)<liste_max) then
hensel (x, p);
end_if;
else
// Primes p at position x
// print (x, p);
end_if;
end_if;
end_for;
2. h) Improved programming for speed V, multiplication instead of division
Multiplication is faster as division.
Therefore you can change the initialising and the following sieving.
You need to use the Hensel-lifting in order to determine the power of the factors.
Before : Initialising with f(n) and dividing by the factors.
Better : Initialising with 1 and multiplication by the factors.
2. i) Improved programming for speed V, Logarithm
The divisions of the function value f(n)=n2+1 by the sieving primes is made
by substructions of the logarithm values of the primes from the logarithm of f(n).
By using this replacement you have to pay attention to the error estimation of the logarithm and the maximum amount of substractions / divisions by the primes
- liste_max:=100;
log_base:=10;
// the prime number 2 is eliminated
count_prime:=1;
// return the function value of the polynomial f(x)=x2+1
f:=proc (x)
begin
return (x2+1);
end;
// return the first derivation / f´(x)=2x
fd:=proc (x)
begin
return (2*x);
end;
// intialisation of list with the log value base log_base where x is even
for x from 2 to liste_max step 2 do
liste [x]:=log (log_base, f(x));
end_for;
// intialisation of list with the log value base log_base where x is odd
for x from 3 to liste_max step 2 do
liste [x]:=log (log_base, f(x)/2);
end_for;
// sieving operation / division of p by substraction of the log values
sieving:=proc (s, p, a, log_p)
begin
while (s<=liste_max) do
liste[s]:=liste[s]-log_p;
s:=s+a;
end_while;
end_proc;
// Calculation of the hensel lifting
hensel:=proc (x, p, log_p)
begin
sieving (x+p, p, p, log_p);
sieving (2*p-x, p, p, log_p);
s:=x;
a:=p;
inv:=fd(s)^(-1) mod p;
repeat
a:=a*p;
s:=s-f(s)*inv;
s:=s mod a;
sieving ( s, p, a, log_p);
sieving (a-s, p, a, log_p);
until s>liste_max and (a-s)>liste_max end_repeat;
end_proc;
// main loop
for x from 2 to liste_max do
log_p:=liste[x];
p:=round (log_base^log_p);
if (p > 1) then
if (p > 2*x) then
// First occurance of the primes / primes p at position x
print (x, p);
count_prime:=count_prime+1;
else
// Second occurance of the prime
// 3. appearance of the prime
if ((2*p-x)<liste_max) then
hensel (x, p, log_p);
end_if;
end_if;
end_if;
end_for;
print (count_prime, liste_max);
2. j) basic algorithm in the complex field for Gaussian prime elements
This algorithm is interesting from the mathematical point of view and the additional results.
The sieving is not made in N but in the complex field C, so that every prime has a relationship to
a complex gaussian number and the conjugated complex number p=(a+bi)*(a-bi)=a2+b2
This algorithm is a possible way to generate gaussian primes, although they are not ordered by huge.
- liste_max:=100;
division_complex:=proc (zelle, p)
begin
// first complex division
erg:=zelle/p;
repeat
// complex division
erg_2:=erg/p;
// if complex result a+bI not a and b element of N return
if ((domtype (Re (erg_2)) <> DOM_INT) or (domtype (Im (erg_2)) <> DOM_INT))
then return (erg);
end_if;
erg:=erg_2;
until (FALSE) end_repeat;
end_proc;
// Sieving by the complex argument p
sieving:=proc (stelle, p, prim)
begin
while (stelle<=liste_max) do
liste[stelle]:=division_complex (liste[stelle], p);
stelle:=stelle+prim;
end_while;
end_proc;
for x from 1 to liste_max do
liste [x]:=x+I;
end_for;
for x from 1 to liste_max do
p:=liste[x];
prim:=p*conjugate (p);
if (prim>1) then
print ("x=", x, "prim = ", prim, "=", p,"*", conjugate (p), "=", (Re (p))2, "+", (Im(p))2 );
// First sieving
sieving (x+prim, p, prim);
if (prim>2) then
// Second sieving by the conjugate argument of p
sieving (prim-x, conjugate (p), prim);
end_if;
end_if;
end_for;
x= 1 prim = 2 = (1 + I) * (1 - I) = 1 + 1
x= 2 prim = 5 = (2 + I) * (2 - I) = 4 + 1
x= 4 prim = 17 = (4 + I) * (4 - I) = 16 + 1
x= 5 prim = 13 = (3 - 2 I) * (3 + 2 I) = 9 + 4
x= 6 prim = 37 = (6 + I) * (6 - I) = 36 + 1
x= 9 prim = 41 = (5 - 4 I) * (5 + 4 I) = 25 + 16
x= 10 prim = 101 = (10 + I) * (10 - I) = 100 + 1
x= 11 prim = 61 = (6 - 5 I) * (6 + 5 I) = 36 + 25
x= 12 prim = 29 = (5 - 2 I) * (5 + 2 I) = 25 + 4
x= 14 prim = 197 = (14 + I) * (14 - I) = 196 + 1
x= 15 prim = 113 = (8 - 7 I) * (8 + 7 I) = 64 + 49
x= 16 prim = 257 = (16 + I) * (16 - I) = 256 + 1
x= 19 prim = 181 = (10 - 9 I) * (10 + 9 I) = 100 + 81
x= 20 prim = 401 = (20 + I) * (20 - I) = 400 + 1
x= 22 prim = 97 = (9 - 4 I) * (9 + 4 I) = 81 + 16
x= 23 prim = 53 = (7 - 2 I) * (7 + 2 I) = 49 + 4
x= 24 prim = 577 = (24 + I) * (24 - I) = 576 + 1
x= 25 prim = 313 = (13 - 12 I) * (13 + 12 I) = 169 + 144
x= 26 prim = 677 = (26 + I) * (26 - I) = 676 + 1
x= 27 prim = 73 = (3 - 8 I) * (3 + 8 I) = 9 + 64
x= 28 prim = 157 = (11 + 6 I) * (11 - 6 I) = 121 + 36
x= 29 prim = 421 = (15 - 14 I) * (15 + 14 I) = 225 + 196
x= 33 prim = 109 = (10 - 3 I) * (10 + 3 I) = 100 + 9
x= 34 prim = 89 = (8 - 5 I) * (8 + 5 I) = 64 + 25
x= 35 prim = 613 = (18 - 17 I) * (18 + 17 I) = 324 + 289
x= 36 prim = 1297 = (36 + I) * (36 - I) = 1296 + 1
x= 37 prim = 137 = (4 - 11 I) * (4 + 11 I) = 16 + 121
x= 39 prim = 761 = (20 - 19 I) * (20 + 19 I) = 400 + 361
x= 40 prim = 1601 = (40 + I) * (40 - I) = 1600 + 1
x= 42 prim = 353 = (17 - 8 I) * (17 + 8 I) = 289 + 64
x= 44 prim = 149 = (10 + 7 I) * (10 - 7 I) = 100 + 49
x= 45 prim = 1013 = (23 - 22 I) * (23 + 22 I) = 529 + 484
x= 48 prim = 461 = (19 + 10 I) * (19 - 10 I) = 361 + 100
x= 49 prim = 1201 = (25 - 24 I) * (25 + 24 I) = 625 + 576
x= 51 prim = 1301 = (26 - 25 I) * (26 + 25 I) = 676 + 625
x= 52 prim = 541 = (21 - 10 I) * (21 + 10 I) = 441 + 100
x= 53 prim = 281 = (16 - 5 I) * (16 + 5 I) = 256 + 25
x= 54 prim = 2917 = (54 + I) * (54 - I) = 2916 + 1
x= 56 prim = 3137 = (56 + I) * (56 - I) = 3136 + 1
x= 58 prim = 673 = (23 + 12 I) * (23 - 12 I) = 529 + 144
x= 59 prim = 1741 = (30 - 29 I) * (30 + 29 I) = 900 + 841
x= 60 prim = 277 = (14 - 9 I) * (14 + 9 I) = 196 + 81
x= 61 prim = 1861 = (31 - 30 I) * (31 + 30 I) = 961 + 900
x= 62 prim = 769 = (25 - 12 I) * (25 + 12 I) = 625 + 144
x= 63 prim = 397 = (19 - 6 I) * (19 + 6 I) = 361 + 36
x= 64 prim = 241 = (15 + 4 I) * (15 - 4 I) = 225 + 16
x= 65 prim = 2113 = (33 - 32 I) * (33 + 32 I) = 1089 + 1024
x= 66 prim = 4357 = (66 + I) * (66 - I) = 4356 + 1
x= 67 prim = 449 = (7 - 20 I) * (7 + 20 I) = 49 + 400
x= 69 prim = 2381 = (35 - 34 I) * (35 + 34 I) = 1225 + 1156
x= 71 prim = 2521 = (36 - 35 I) * (36 + 35 I) = 1296 + 1225
x= 74 prim = 5477 = (74 + I) * (74 - I) = 5476 + 1
x= 77 prim = 593 = (8 - 23 I) * (8 + 23 I) = 64 + 529
x= 78 prim = 1217 = (31 + 16 I) * (31 - 16 I) = 961 + 256
x= 79 prim = 3121 = (40 - 39 I) * (40 + 39 I) = 1600 + 1521
x= 80 prim = 173 = (13 - 2 I) * (13 + 2 I) = 169 + 4
x= 81 prim = 193 = (12 - 7 I) * (12 + 7 I) = 144 + 49
x= 82 prim = 269 = (10 - 13 I) * (10 + 13 I) = 100 + 169
x= 84 prim = 7057 = (84 + I) * (84 - I) = 7056 + 1
x= 85 prim = 3613 = (43 - 42 I) * (43 + 42 I) = 1849 + 1764
x= 86 prim = 569 = (20 - 13 I) * (20 + 13 I) = 400 + 169
x= 87 prim = 757 = (9 - 26 I) * (9 + 26 I) = 81 + 676
x= 88 prim = 1549 = (35 + 18 I) * (35 - 18 I) = 1225 + 324
x= 89 prim = 233 = (8 - 13 I) * (8 + 13 I) = 64 + 169
x= 90 prim = 8101 = (90 + I) * (90 - I) = 8100 + 1
x= 92 prim = 1693 = (37 - 18 I) * (37 + 18 I) = 1369 + 324
x= 94 prim = 8837 = (94 + I) * (94 - I) = 8836 + 1
x= 95 prim = 4513 = (48 - 47 I) * (48 + 47 I) = 2304 + 2209
x= 96 prim = 709 = (22 + 15 I) * (22 - 15 I) = 484 + 225
x= 97 prim = 941 = (10 - 29 I) * (10 + 29 I) = 100 + 841
4. a) Results of the distribution of the primes
Legend of the tables:
Column A = exponent concerning base 10 resp. base 2
Column B = is the interval [0,x]
Column C = all primes resp. D+E, the amount of the primes depends of p(x) for the interval [0,x] and is not calculated by primes < x
Column D = primes of the form p=x2+1
Column E = reducible primes with p | x2+1 and p < x2+1, counted by the first appearance resp. for the smallest x.
The numbers in the rows F-K are rounded with 6 digits after the decimal point.
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
|
10^n |
x |
all Primes |
P(x)=x^2+1 |
P(x) | x^2+1 |
C/B |
D/B |
E/B |
C(n) / C(n-1) |
D(n) / D(n-1) |
E(n) / E(n-1) |
|
1 |
10 |
7 |
5 |
2 |
0,700000 |
0,500000 |
0,200000 |
|
|
|
|
2 |
100 |
70 |
19 |
51 |
0,700000 |
0,190000 |
0,510000 |
10,000000 |
3,800000 |
25,500000 |
|
3 |
1.000 |
720 |
112 |
608 |
0,720000 |
0,112000 |
0,608000 |
10,285714 |
5,894737 |
11,921569 |
|
4 |
10.000 |
7.102 |
841 |
6.261 |
0,710200 |
0,084100 |
0,626100 |
9,863889 |
7,508929 |
10,297697 |
|
5 |
100.000 |
70.780 |
6.656 |
64.124 |
0,707800 |
0,066560 |
0,641240 |
9,966207 |
7,914388 |
10,241814 |
|
6 |
1.000.000 |
704.537 |
54.110 |
650.427 |
0,704537 |
0,054110 |
0,650427 |
9,953899 |
8,129507 |
10,143269 |
|
7 |
10.000.000 |
7.026.559 |
456.362 |
6.570.197 |
0,702656 |
0,045636 |
0,657020 |
9,973300 |
8,433968 |
10,101360 |
|
8 |
100.000.000 |
70.122.424 |
3.954.181 |
66.168.243 |
0,701224 |
0,039542 |
0,661682 |
9,979625 |
8,664571 |
10,070968 |
|
9 |
1.000.000.000 |
700.184.485 |
34.900.213 |
665.284.272 |
0,700184 |
0,034900 |
0,665284 |
9,985172 |
8,826155 |
10,054435 |
|
10 |
10.000.000.000 |
6.993.568.566 |
312.357.934 |
6.681.210.632 |
0,699357 |
0,031236 |
0,668121 |
9,988180 |
8,950029 |
10,042640 |
|
11 |
100.000.000.000 |
69.870.544.960 |
2.826.683.630 |
67.043.861.330 |
0,698705 |
0,028267 |
0,670439 |
9,990686 |
9,049502 |
10,034688 |
|
12 |
1.000.000.000.000 |
698.175.242.376 |
25.814.570.672 |
672.360.671.704 |
0,698175 |
0,025815 |
0,672361 |
9,992412 |
9,132458 |
10,028669 |
|
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
|
2^n |
x |
all Primes |
P(x)=x^2+1 |
P(x) | x^2+1 |
C/B |
D/B |
E/B |
C(n) / C(n-1) |
D(n) / D(n-1) |
E(n) / E(n-1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
2 |
2 |
0 |
1,000000 |
1,000000 |
0,000000 |
|
|
|
|
2 |
4 |
3 |
3 |
0 |
0,750000 |
0,750000 |
0,000000 |
1,500000 |
1,500000 |
|
|
3 |
8 |
5 |
4 |
1 |
0,625000 |
0,500000 |
0,125000 |
1,666667 |
1,333333 |
|
|
4 |
16 |
12 |
7 |
5 |
0,750000 |
0,437500 |
0,312500 |
2,400000 |
1,750000 |
5,000000 |
|
5 |
32 |
22 |
10 |
12 |
0,687500 |
0,312500 |
0,375000 |
1,833333 |
1,428571 |
2,400000 |
|
6 |
64 |
46 |
14 |
32 |
0,718750 |
0,218750 |
0,500000 |
2,090909 |
1,400000 |
2,666667 |
|
7 |
128 |
90 |
24 |
66 |
0,703125 |
0,187500 |
0,515625 |
1,956522 |
1,714286 |
2,062500 |
|
8 |
256 |
181 |
43 |
138 |
0,707031 |
0,167969 |
0,539063 |
2,011111 |
1,791667 |
2,090909 |
|
9 |
512 |
364 |
70 |
294 |
0,710938 |
0,136719 |
0,574219 |
2,011050 |
1,627907 |
2,130435 |
|
10 |
1.024 |
736 |
114 |
622 |
0,718750 |
0,111328 |
0,607422 |
2,021978 |
1,628571 |
2,115646 |
|
11 |
2.048 |
1.459 |
212 |
1.247 |
0,712402 |
0,103516 |
0,608887 |
1,982337 |
1,859649 |
2,004823 |
|
12 |
4.096 |
2.920 |
393 |
2.527 |
0,712891 |
0,095947 |
0,616943 |
2,001371 |
1,853774 |
2,026464 |
|
13 |
8.192 |
5.810 |
713 |
5.097 |
0,709229 |
0,087036 |
0,622192 |
1,989726 |
1,814249 |
2,017016 |
|
14 |
16.384 |
11.620 |
1.301 |
10.319 |
0,709229 |
0,079407 |
0,629822 |
2,000000 |
1,824684 |
2,024524 |
|
15 |
32.768 |
23.198 |
2.459 |
20.739 |
0,707947 |
0,075043 |
0,632904 |
1,996386 |
1,890085 |
2,009788 |
|
16 |
65.536 |
46.339 |
4.615 |
41.724 |
0,707077 |
0,070419 |
0,636658 |
1,997543 |
1,876779 |
2,011862 |
|
17 |
131.072 |
92.654 |
8.418 |
84.236 |
0,706894 |
0,064224 |
0,642670 |
1,999482 |
1,824052 |
2,018886 |
|
18 |
262.144 |
185.106 |
15.867 |
169.239 |
0,706123 |
0,060528 |
0,645596 |
1,997820 |
1,884890 |
2,009105 |
|
19 |
524.288 |
369.794 |
29.843 |
339.951 |
0,705326 |
0,056921 |
0,648405 |
1,997742 |
1,880822 |
2,008704 |
|
20 |
1.048.576 |
738.766 |
56.534 |
682.232 |
0,704542 |
0,053915 |
0,650627 |
1,997777 |
1,894381 |
2,006854 |
|
21 |
2.097.152 |
1.476.544 |
106.787 |
1.369.757 |
0,704071 |
0,050920 |
0,653151 |
1,998663 |
1,888899 |
2,007758 |
|
22 |
4.194.304 |
2.949.935 |
203.025 |
2.746.910 |
0,703319 |
0,048405 |
0,654914 |
1,997865 |
1,901215 |
2,005399 |
|
23 |
8.388.608 |
5.894.833 |
387.308 |
5.507.525 |
0,702719 |
0,046171 |
0,656548 |
1,998293 |
1,907686 |
2,004989 |
|
24 |
16.777.216 |
11.782.897 |
739.671 |
11.043.226 |
0,702315 |
0,044088 |
0,658228 |
1,998852 |
1,909775 |
2,005116 |
|
25 |
33.554.432 |
23.550.908 |
1.416.635 |
22.134.273 |
0,701872 |
0,042219 |
0,659653 |
1,998737 |
1,915223 |
2,004330 |
|
26 |
67.108.864 |
47.074.786 |
2.716.922 |
44.357.864 |
0,701469 |
0,040485 |
0,660984 |
1,998852 |
1,917870 |
2,004035 |
|
27 |
134.217.728 |
94.099.962 |
5.218.926 |
88.881.036 |
0,701099 |
0,038884 |
0,662215 |
1,998946 |
1,920897 |
2,003727 |
|
28 |
268.435.456 |
188.106.701 |
10.044.585 |
178.062.116 |
0,700752 |
0,037419 |
0,663333 |
1,999009 |
1,924646 |
2,003376 |
|
29 |
536.870.912 |
376.049.307 |
19.352.155 |
356.697.152 |
0,700446 |
0,036046 |
0,664400 |
1,999128 |
1,926626 |
2,003218 |
|
30 |
1.073.741.824 |
751.784.745 |
37.339.024 |
714.445.721 |
0,700154 |
0,034775 |
0,665379 |
1,999165 |
1,929450 |
2,002948 |
|
31 |
2.147.483.648 |
1.503.000.381 |
72.139.395 |
1.430.860.986 |
0,699889 |
0,033593 |
0,666297 |
1,999243 |
1,932011 |
2,002757 |
|
32 |
4.294.967.296 |
3.004.917.702 |
139.535.723 |
2.865.381.979 |
0,699637 |
0,032488 |
0,667149 |
1,999279 |
1,934251 |
2,002558 |
|
33 |
8.589.934.592 |
6.007.850.623 |
270.187.320 |
5.737.663.303 |
0,699406 |
0,031454 |
0,667952 |
1,999339 |
1,936331 |
2,002408 |
|
34 |
17.179.869.184 |
12.012.007.361 |
523.695.185 |
11.488.312.176 |
0,699191 |
0,030483 |
0,668708 |
1,999385 |
1,938267 |
2,002263 |
|
35 |
34.359.738.368 |
24.017.148.553 |
1.016.029.276 |
23.001.119.277 |
0,698991 |
0,029570 |
0,669421 |
1,999428 |
1,940116 |
2,002132 |
|
36 |
68.719.476.736 |
48.021.305.927 |
1.973.029.796 |
46.048.276.131 |
0,698802 |
0,028711 |
0,670091 |
1,999459 |
1,941903 |
2,002002 |
|
37 |
137.438.953.472 |
96.018.463.670 |
3.834.641.365 |
92.183.822.305 |
0,698626 |
0,027901 |
0,670726 |
1,999497 |
1,943529 |
2,001895 |
|
38 |
274.877.906.944 |
191.991.204.563 |
7.458.662.439 |
184.532.542.124 |
0,698460 |
0,027134 |
0,671325 |
1,999524 |
1,945074 |
2,001789 |
|
39 |
549.755.813.888 |
383.896.376.530 |
14.518.923.631 |
369.377.452.899 |
0,698303 |
0,026410 |
0,671894 |
1,999552 |
1,946585 |
2,001693 |
|
40 |
1.099.511.627.776 |
767.630.202.986 |
28.282.415.900 |
739.347.787.086 |
0,698156 |
0,025723 |
0,672433 |
1,999577 |
1,947969 |
2,001605 |
|
41 |
2.199.023.255.552 |
1.534.954.071.943 |
55.130.064.461 |
1.479.824.007.482 |
0,698016 |
0,025070 |
0,672946 |
1,999601 |
1,949270 |
2,001526 |
|
The quotient between the number of all primes [p=f(x) and p|f(x), counted by their first appearance by increasing x], and x resp.
the green column F = C/B goes probably to ln (2)= 0,693147181.
4. b) Graphic of the distribution of the primes
Legend of the graphic:
The green dots / column F are the values for all primes concerning the polynom x2+1
The orange dots / column G are the values for the primes with p=x2+1
The yellow dots / column H are the values for the primes by the first occurance with p|x2+1 and p smaller than x2+1
The x-axis is the logarithm to the base of 2 and goes up to 240
4. c) Graphic of the proportion between the "reducible" and the "big" primes
A |
B |
C |
D |
E |
F |
|
|
|
|
|
2^n |
x |
P(x) | x^2+1 |
P(x)=x^2+1 |
C/D |
log (B, 3) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
0 |
2 |
0,0000 |
0,6309 |
|
|
|
|
|
2 |
4 |
0 |
3 |
0,0000 |
1,2619 |
|
|
|
|
|
3 |
8 |
1 |
4 |
0,2500 |
1,8928 |
|
|
|
|
|
4 |
16 |
5 |
7 |
0,7143 |
2,5237 |
|
|
|
|
|
5 |
32 |
12 |
10 |
1,2000 |
3,1546 |
|
|
|
|
|
6 |
64 |
32 |
14 |
2,2857 |
3,7856 |
|
|
|
|
|
7 |
128 |
66 |
24 |
2,7500 |
4,4165 |
|
|
|
|
|
8 |
256 |
138 |
43 |
3,2093 |
5,0474 |
|
|
|
|
|
9 |
512 |
294 |
70 |
4,2000 |
5,6784 |
|
|
|
|
|
10 |
1.024 |
622 |
114 |
5,4561 |
6,3093 |
|
|
|
|
|
11 |
2.048 |
1.247 |
212 |
5,8821 |
6,9402 |
|
|
|
|
|
12 |
4.096 |
2.527 |
393 |
6,4300 |
7,5712 |
|
|
|
|
|
13 |
8.192 |
5.097 |
713 |
7,1487 |
8,2021 |
|
|
|
|
|
14 |
16.384 |
10.319 |
1.301 |
7,9316 |
8,8330 |
|
|
|
|
|
15 |
32.768 |
20.739 |
2.459 |
8,4339 |
9,4639 |
|
|
|
|
|
16 |
65.536 |
41.724 |
4.615 |
9,0410 |
10,0949 |
|
|
|
|
|
17 |
131.072 |
84.236 |
8.418 |
10,0067 |
10,7258 |
|
|
|
|
|
18 |
262.144 |
169.239 |
15.867 |
10,6661 |
11,3567 |
|
|
|
|
|
19 |
524.288 |
339.951 |
29.843 |
11,3913 |
11,9877 |
|
|
|
|
|
20 |
1.048.576 |
682.232 |
56.534 |
12,0676 |
12,6186 |
|
|
|
|
|
21 |
2.097.152 |
1.369.757 |
106.787 |
12,8270 |
13,2495 |
|
|
|
|
|
22 |
4.194.304 |
2.746.910 |
203.025 |
13,5299 |
13,8805 |
|
|
|
|
|
23 |
8.388.608 |
5.507.525 |
387.308 |
14,2200 |
14,5114 |
|
|
|
|
|
24 |
16.777.216 |
11.043.226 |
739.671 |
14,9299 |
15,1423 |
|
|
|
|
|
25 |
33.554.432 |
22.134.273 |
1.416.635 |
15,6245 |
15,7732 |
|
|
|
|
|
26 |
67.108.864 |
44.357.864 |
2.716.922 |
16,3265 |
16,4042 |
|
|
|
|
|
27 |
134.217.728 |
88.881.036 |
5.218.926 |
17,0305 |
17,0351 |
|
|
|
|
|
28 |
268.435.456 |
178.062.116 |
10.044.585 |
17,7272 |
17,6660 |
|
|
|
|
|
29 |
536.870.912 |
356.697.152 |
19.352.155 |
18,4319 |
18,2970 |
|
|
|
|
|
30 |
1.073.741.824 |
714.445.721 |
37.339.024 |
19,1340 |
18,9279 |
|
|
|
|
|
31 |
2.147.483.648 |
1.430.860.986 |
72.139.395 |
19,8347 |
19,5588 |
|
|
|
|
|
32 |
4.294.967.296 |
2.865.381.979 |
139.535.723 |
20,5351 |
20,1898 |
|
|
|
|
|
33 |
8.589.934.592 |
5.737.663.303 |
270.187.320 |
21,2359 |
20,8207 |
|
|
|
|
|
34 |
17.179.869.184 |
11.488.312.176 |
523.695.185 |
21,9370 |
21,4516 |
|
|
|
|
|
35 |
34.359.738.368 |
23.001.119.277 |
1.016.029.276 |
22,6382 |
22,0825 |
|
|
|
|
|
36 |
68.719.476.736 |
46.048.276.131 |
1.973.029.796 |
23,3389 |
22,7135 |
|
|
|
|
|
37 |
137.438.953.472 |
92.183.822.305 |
3.834.641.365 |
24,0398 |
23,3444 |
|
|
|
|
|
38 |
274.877.906.944 |
184.532.542.124 |
7.458.662.439 |
24,7407 |
23,9753 |
|
|
|
|
|
39 |
549.755.813.888 |
369.377.452.899 |
14.518.923.631 |
25,4411 |
24,6063 |
|
|
|
|
|
40 |
1.099.511.627.776 |
739.347.787.086 |
28.282.415.900 |
26,1416 |
25,2372 |
|
|
|
|
|
|
4. d) Graphic of the distribution of all primes concerning their huge
2^n |
n=10 |
n=20 |
n=30 |
n=39 |
binary logarithm of the prime |
|
|
|
|
1 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
3 |
1 |
1 |
1 |
1 |
4 |
2 |
2 |
2 |
2 |
5 |
4 |
4 |
4 |
4 |
6 |
6 |
6 |
6 |
6 |
7 |
10 |
10 |
10 |
10 |
8 |
21 |
21 |
21 |
21 |
9 |
38 |
38 |
38 |
38 |
10 |
66 |
66 |
66 |
66 |
11 |
92 |
127 |
127 |
127 |
12 |
76 |
233 |
233 |
233 |
13 |
87 |
432 |
432 |
432 |
14 |
68 |
805 |
805 |
805 |
15 |
65 |
1.511 |
1.511 |
1.511 |
16 |
64 |
2.837 |
2.837 |
2.837 |
17 |
56 |
5.378 |
5.378 |
5.378 |
18 |
55 |
10.186 |
10.186 |
10.186 |
19 |
23 |
19.294 |
19.294 |
19.294 |
20 |
0 |
36.827 |
36.827 |
36.827 |
21 |
0 |
48.789 |
70.157 |
70.157 |
22 |
0 |
46.604 |
133.975 |
133.975 |
23 |
0 |
44.541 |
256.852 |
256.852 |
24 |
0 |
42.639 |
492.882 |
492.882 |
25 |
0 |
41.369 |
946.848 |
946.848 |
26 |
0 |
39.635 |
1.823.129 |
1.823.129 |
27 |
0 |
38.155 |
3.513.599 |
3.513.599 |
28 |
0 |
36.694 |
6.780.412 |
6.780.412 |
29 |
0 |
35.469 |
13.103.462 |
13.103.462 |
30 |
0 |
34.558 |
25.348.870 |
25.348.870 |
31 |
0 |
33.258 |
34.087.506 |
49.090.415 |
32 |
0 |
32.278 |
33.039.675 |
95.167.380 |
33 |
0 |
31.028 |
32.054.166 |
184.662.052 |
34 |
0 |
30.181 |
31.132.063 |
358.630.671 |
35 |
0 |
28.958 |
30.244.146 |
697.097.364 |
36 |
0 |
28.618 |
29.415.874 |
1.356.051.342 |
37 |
0 |
25.664 |
28.635.210 |
2.639.870.329 |
38 |
0 |
27.183 |
27.883.394 |
5.142.823.877 |
39 |
0 |
15.365 |
27.189.203 |
10.025.582.289 |
40 |
0 |
0 |
26.519.512 |
13.574.819.204 |
41 |
0 |
0 |
25.874.372 |
13.247.762.275 |
42 |
0 |
0 |
25.265.740 |
12.936.129.149 |
43 |
0 |
0 |
24.689.787 |
12.638.529.888 |
44 |
0 |
0 |
24.125.789 |
12.354.600.489 |
45 |
0 |
0 |
23.599.360 |
12.083.161.608 |
46 |
0 |
0 |
23.089.555 |
11.823.171.181 |
47 |
0 |
0 |
22.607.976 |
11.574.181.661 |
48 |
0 |
0 |
22.149.632 |
11.335.619.027 |
49 |
0 |
0 |
21.696.082 |
11.106.498.716 |
50 |
0 |
0 |
21.251.111 |
10.886.741.743 |
51 |
0 |
0 |
20.807.352 |
10.675.323.639 |
52 |
0 |
0 |
20.533.816 |
10.472.016.150 |
53 |
0 |
0 |
19.952.893 |
10.276.163.302 |
54 |
0 |
0 |
19.569.826 |
10.087.386.117 |
55 |
0 |
0 |
19.093.140 |
9.905.692.828 |
56 |
0 |
0 |
18.892.638 |
9.730.489.216 |
57 |
0 |
0 |
17.208.655 |
9.561.216.748 |
58 |
0 |
0 |
18.167.763 |
9.397.807.108 |
59 |
0 |
0 |
10.460.543 |
9.239.790.510 |
60 |
0 |
0 |
0 |
9.086.871.013 |
61 |
0 |
0 |
0 |
8.939.247.717 |
62 |
0 |
0 |
0 |
8.796.575.998 |
63 |
0 |
0 |
0 |
8.657.577.119 |
64 |
0 |
0 |
0 |
8.522.899.197 |
65 |
0 |
0 |
0 |
8.392.678.194 |
66 |
0 |
0 |
0 |
8.268.245.924 |
67 |
0 |
0 |
0 |
8.145.305.721 |
68 |
0 |
0 |
0 |
8.021.141.566 |
69 |
0 |
0 |
0 |
7.895.311.485 |
70 |
0 |
0 |
0 |
7.830.607.024 |
71 |
0 |
0 |
0 |
7.645.125.168 |
72 |
0 |
0 |
0 |
7.530.870.899 |
73 |
0 |
0 |
0 |
7.381.754.182 |
74 |
0 |
0 |
0 |
7.335.361.187 |
75 |
0 |
0 |
0 |
6.710.801.165 |
76 |
0 |
0 |
0 |
7.113.815.439 |
77 |
0 |
0 |
0 |
4.113.563.288 |
|
|
|
|
|
4. e) Table of the distribution of all primes concerning their second appearance
A
|
B
|
C
|
D
|
E
|
F
|
G
|
exponent =log2
(x)
|
<=x
|
number of all
primes by their 1. appearance
|
number of all
primes by their 2. appearance
|
C / D
|
ln (B)
|
0.7*B/ln(B)
|
1
|
2
|
2
|
0
|
|
|
2,01
|
2
|
4
|
3
|
1
|
3,0000
|
1,3905
|
2,01
|
3
|
8
|
5
|
2
|
2,5000
|
2,0858
|
2,68
|
4
|
16
|
12
|
3
|
4,0000
|
2,7811
|
4,03
|
5
|
32
|
22
|
7
|
3,1429
|
3,4763
|
6,44
|
6
|
64
|
46
|
10
|
4,6000
|
4,1716
|
10,74
|
7
|
128
|
90
|
19
|
4,7368
|
4,8669
|
18,41
|
8
|
256
|
181
|
33
|
5,4848
|
5,5621
|
32,22
|
9
|
512
|
364
|
58
|
6,2759
|
6,2574
|
57,28
|
10
|
1.024
|
736
|
112
|
6,5714
|
6,9527
|
103,10
|
11
|
2.048
|
1.459
|
203
|
7,1872
|
7,6480
|
187,45
|
12
|
4.096
|
2.920
|
355
|
8,2254
|
8,3432
|
343,66
|
13
|
8.192
|
5.810
|
677
|
8,5820
|
9,0385
|
634,44
|
14
|
16.384
|
11.620
|
1.255
|
9,2590
|
9,7338
|
1.178,25
|
15
|
32.768
|
23.198
|
2.333
|
9,9434
|
10,4290
|
2.199,40
|
16
|
65.536
|
46.339
|
4.375
|
10,5918
|
11,1243
|
4.123,87
|
17
|
131.072
|
92.654
|
8.261
|
11,2158
|
11,8196
|
7.762,58
|
18
|
262.144
|
185.106
|
15.446
|
11,9841
|
12,5148
|
14.662,66
|
19
|
524.288
|
369.794
|
29.212
|
12,6590
|
13,2101
|
27.781,88
|
20
|
1.048.576
|
738.766
|
55.488
|
13,3140
|
13,9054
|
52.785,58
|
21
|
2.097.152
|
1.476.544
|
105.123
|
14,0459
|
14,6006
|
100.543,96
|
22
|
4.194.304
|
2.949.935
|
199.932
|
14,7547
|
15,2959
|
191.947,56
|
23
|
8.388.608
|
5.894.833
|
382.384
|
15,4160
|
15,9912
|
367.204,02
|
24
|
16.777.216
|
11.782.897
|
730.623
|
16,1272
|
16,6864
|
703.807,70
|
25
|
33.554.432
|
23.550.908
|
1.400.694
|
16,8137
|
17,3817
|
1.351.310,79
|
26
|
67.108.864
|
47.074.786
|
2.687.730
|
17,5147
|
18,0770
|
2.598.674,60
|
27
|
134.217.728
|
94.099.962
|
5.167.473
|
18,2101
|
18,7723
|
5.004.854,78
|
28
|
268.435.456
|
188.106.701
|
9.952.863
|
18,8998
|
19,4675
|
9.652.219,94
|
29
|
536.870.912
|
376.049.307
|
19.193.397
|
19,5926
|
20,1628
|
18.638.769,53
|
30
|
1.073.741.824
|
751.784.745
|
37.059.261
|
20,2860
|
20,8581
|
36.034.954,43
|
31
|
2.147.483.648
|
1.503.000.381
|
71.635.400
|
20,9813
|
21,5533
|
69.745.073,09
|
32
|
4.294.967.296
|
3.004.917.702
|
138.633.544
|
21,6753
|
22,2486
|
135.131.079,12
|
33
|
8.589.934.592
|
6.007.850.623
|
268.568.123
|
22,3699
|
22,9439
|
262.072.395,86
|
34
|
17.179.869.184
|
12.012.007.361
|
520.836.610
|
23,0629
|
23,6391
|
508.728.768,44
|
35
|
34.359.738.368
|
24.017.148.553
|
1.010.957.203
|
23,7568
|
24,3344
|
988.387.321,54
|
36
|
68.719.476.736
|
48.021.305.927
|
1.964.003.096
|
24,4507
|
25,0297
|
1.921.864.236,32
|
37
|
137.438.953.472
|
96.018.463.670
|
3.818.594.577
|
25,1450
|
25,7249
|
3.739.843.919,33
|
38
|
274.877.906.944
|
191.991.204.563
|
7.430.384.395
|
25,8387
|
26,4202
|
7.282.853.948,16
|
39
|
549.755.813.888
|
383.896.376.530
|
14.468.881.009
|
26,5326
|
27,1155
|
14.192.228.206,68
|
4. f) Comparison between the amount of primes between their 2. appearance and the primes of the form p=n2+1
legend:
by use of the described algorithm there only remains one prime or none at the position n for f(n)=n^2+1
"big" prime := prime = f(n) = n²+1
"reducible" prime := prime | f(n) = n²+1 and prime < f(n)
every prime has two quadratic roots for the polynomial f(n) = n^2+1, i distinguish between n=first root and n=second root of the prime
example:
n=2; f(2)=5; p=5; first root of 5 is 2, second root of 5 is 3; 5 is a "big" prime.
n=5; f(5)=26; p=13; first root of 13 is n=5, second root of 13 is n=8; 13 is a "reducible" prime.
A |
B |
C |
D |
E |
F |
G |
log (n, 2) |
n |
amount of "big" primes |
amount of "big" primes |
amount of "red." primes |
amount of "red." primes |
C/F |
|
|
for n = first root of p |
for n = sec. root of p |
for n = first root of p |
for n = sec. root of p |
|
22 |
4.194.304 |
203.024 |
211 |
2.746.909 |
199.721 |
1,016538 |
23 |
8.388.608 |
387.307 |
292 |
5.507.525 |
382.092 |
1,013649 |
24 |
16.777.216 |
739.670 |
392 |
11.043.226 |
730.230 |
1,012927 |
25 |
33.554.432 |
1.416.634 |
538 |
22.134.273 |
1.400.156 |
1,011769 |
26 |
67.108.864 |
2.716.921 |
712 |
44.357.863 |
2.687.018 |
1,011129 |
27 |
134.217.728 |
5.218.925 |
956 |
88.881.036 |
5.166.517 |
1,010144 |
28 |
268.435.456 |
10.044.584 |
1.300 |
178.062.115 |
9.951.563 |
1,009347 |
29 |
536.870.912 |
19.352.154 |
1.791 |
356.697.152 |
19.191.605 |
1,008366 |
30 |
1.073.741.824 |
37.339.023 |
2.458 |
714.445.720 |
37.056.803 |
1,007616 |
31 |
2.147.483.648 |
72.139.394 |
3.377 |
1.430.860.986 |
71.632.023 |
1,007083 |
32 |
4.294.967.296 |
139.535.722 |
4.614 |
2.865.381.978 |
138.628.930 |
1,006541 |
33 |
8.589.934.592 |
270.187.319 |
6.232 |
5.737.663.303 |
268.561.891 |
1,006052 |
34 |
17.179.869.184 |
523.695.184 |
8.417 |
11.488.312.175 |
520.828.193 |
1,005505 |
35 |
34.359.738.368 |
1.016.029.275 |
11.539 |
23.001.119.277 |
1.010.945.664 |
1,005029 |
36 |
68.719.476.736 |
1.973.029.795 |
15.866 |
46.048.276.130 |
1.963.987.230 |
1,004604 |
37 |
137.438.953.472 |
3.834.641.364 |
21.728 |
92.183.822.305 |
3.818.572.849 |
1,004208 |
38 |
274.877.906.944 |
7.458.662.438 |
29.842 |
184.532.542.123 |
7.430.354.553 |
1,003810 |
39 |
549.755.813.888 |
14.518.923.630 |
41.168 |
369.377.452.899 |
14.468.839.841 |
1,003461 |
40 |
1.099.511.627.776 |
28.282.415.899 |
56.533 |
739.347.787.085 |
28.194.567.830 |
1,003116 |
The quotient of column G seems to go to 1.
4. g) Table of the distribution of the primes mod 6 and mod 8
A | B | C | D | E | F | G | H | I | exponent =log2 (x) | <=x | number of primes with p=f(x) | number of primes with p=f(x) and p%6=1 | number of primes with p=f(x) and p%6=5 | number of primes with p=f(x) and p%8=1 | number of primes with p=f(x) and p%8=3 | number of primes with p=f(x) and p%8=5 | number of primes with p=f(x) and p%8=7 |
2 | 4 | 3 | 0 | 2 | 1 | 0 | 1 | 0 |
3 | 8 | 4 | 1 | 2 | 1 | 0 | 2 | 0 |
4 | 16 | 7 | 1 | 5 | 2 | 0 | 4 | 0 |
5 | 32 | 10 | 2 | 7 | 4 | 0 | 5 | 0 |
6 | 64 | 14 | 4 | 9 | 7 | 0 | 6 | 0 |
7 | 128 | 24 | 9 | 14 | 11 | 0 | 12 | 0 |
8 | 256 | 43 | 15 | 27 | 21 | 0 | 21 | 0 |
9 | 512 | 70 | 24 | 45 | 36 | 0 | 33 | 0 |
10 | 1.024 | 114 | 41 | 72 | 60 | 0 | 53 | 0 |
11 | 2.048 | 212 | 70 | 141 | 109 | 0 | 102 | 0 |
12 | 4.096 | 393 | 127 | 265 | 194 | 0 | 198 | 0 |
13 | 8.192 | 713 | 231 | 481 | 360 | 0 | 352 | 0 |
14 | 16.384 | 1.301 | 436 | 864 | 651 | 0 | 649 | 0 |
15 | 32.768 | 2.459 | 843 | 1.615 | 1.244 | 0 | 1.214 | 0 |
16 | 65.536 | 4.615 | 1.547 | 3.067 | 2.330 | 0 | 2.284 | 0 |
17 | 131.072 | 8.418 | 2.854 | 5.563 | 4.246 | 0 | 4.171 | 0 |
18 | 262.144 | 15.867 | 5.323 | 10.543 | 7.938 | 0 | 7.928 | 0 |
19 | 524.288 | 29.843 | 10.013 | 19.829 | 14.955 | 0 | 14.887 | 0 |
20 | 1.048.576 | 56.534 | 18.839 | 37.694 | 28.171 | 0 | 28.362 | 0 |
21 | 2.097.152 | 106.787 | 35.392 | 71.394 | 53.338 | 0 | 53.448 | 0 |
22 | 4.194.304 | 203.025 | 67.653 | 135.371 | 101.119 | 0 | 101.905 | 0 |
23 | 8.388.608 | 387.308 | 128.939 | 258.368 | 193.235 | 0 | 194.072 | 0 |
24 | 16.777.216 | 739.671 | 246.669 | 493.001 | 369.273 | 0 | 370.397 | 0 |
25 | 33.554.432 | 1.416.635 | 472.296 | 944.338 | 708.167 | 0 | 708.467 | 0 |
26 | 67.108.864 | 2.716.922 | 905.507 | 1.811.414 | 1.358.369 | 0 | 1.358.552 | 0 |
27 | 134.217.728 | 5.218.926 | 1.739.916 | 3.479.009 | 2.608.736 | 0 | 2.610.189 | 0 |
28 | 268.435.456 | 10.044.585 | 3.348.644 | 6.695.940 | 5.023.043 | 0 | 5.021.541 | 0 |
29 | 536.870.912 | 19.352.155 | 6.451.988 | 12.900.166 | 9.675.253 | 0 | 9.676.901 | 0 |
30 | 1.073.741.824 | 37.339.024 | 12.447.471 | 24.891.552 | 18.667.885 | 0 | 18.671.138 | 0 |
31 | 2.147.483.648 | 72.139.395 | 24.049.063 | 48.090.331 | 36.067.539 | 0 | 36.071.855 | 0 |
32 | 4.294.967.296 | 139.535.723 | 46.514.862 | 93.020.860 | 69.768.975 | 0 | 69.766.747 | 0 |
33 | 8.589.934.592 | 270.187.320 | 90.058.651 | 180.128.668 | 135.092.284 | 0 | 135.095.035 | 0 |
34 | 17.179.869.184 | 523.695.184 | 174.558.447 | 349.136.736 | 261.845.638 | 0 | 261.849.545 | 0 |
35 | 34.359.738.368 | 1.016.029.274 | 338.653.157 | 677.376.116 | 508.003.536 | 0 | 508.025.737 | 0 |
36 | 68.719.476.736 | 1.973.029.782 | 657.637.459 | 1.315.392.322 | 986.505.253 | 0 | 986.524.528 | 0 |
A | B | C | D | E | F | G | H | I |
exponent =log2 (x) | <=x | number of primes with p|f(x) | number of primes with p=f(x) and p%6=1 | number of primes with p=f(x) and p%6=5 | number of primes with p=f(x) and p%8=1 | number of primes with p=f(x) and p%8=3 | number of primes with p=f(x) and p%8=5 | number of primes with p=f(x) and p%8=7 |
2 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
4 | 16 | 5 | 2 | 3 | 2 | 0 | 3 | 0 |
5 | 32 | 12 | 8 | 4 | 5 | 0 | 7 | 0 |
6 | 64 | 32 | 19 | 13 | 14 | 0 | 18 | 0 |
7 | 128 | 66 | 36 | 30 | 28 | 0 | 38 | 0 |
8 | 256 | 138 | 73 | 65 | 63 | 0 | 75 | 0 |
9 | 512 | 294 | 146 | 148 | 141 | 0 | 153 | 0 |
10 | 1.024 | 622 | 328 | 294 | 311 | 0 | 311 | 0 |
11 | 2.048 | 1.247 | 664 | 583 | 631 | 0 | 616 | 0 |
12 | 4.096 | 2.527 | 1.311 | 1.216 | 1.271 | 0 | 1.256 | 0 |
13 | 8.192 | 5.097 | 2.646 | 2.451 | 2.548 | 0 | 2.549 | 0 |
14 | 16.384 | 10.319 | 5.341 | 4.978 | 5.161 | 0 | 5.158 | 0 |
15 | 32.768 | 20.739 | 10.769 | 9.970 | 10.366 | 0 | 10.373 | 0 |
16 | 65.536 | 41.724 | 21.579 | 20.145 | 20.764 | 0 | 20.960 | 0 |
17 | 131.072 | 84.236 | 43.457 | 40.779 | 42.123 | 0 | 42.113 | 0 |
18 | 262.144 | 169.239 | 86.955 | 82.284 | 84.619 | 0 | 84.620 | 0 |
19 | 524.288 | 339.951 | 174.611 | 165.340 | 169.821 | 0 | 170.130 | 0 |
20 | 1.048.576 | 682.232 | 350.420 | 331.812 | 341.126 | 0 | 341.106 | 0 |
21 | 2.097.152 | 1.369.757 | 702.725 | 667.032 | 684.694 | 0 | 685.063 | 0 |
22 | 4.194.304 | 2.746.910 | 1.408.146 | 1.338.764 | 1.373.504 | 0 | 1.373.406 | 0 |
23 | 8.388.608 | 5.507.525 | 2.817.910 | 2.689.615 | 2.753.635 | 0 | 2.753.890 | 0 |
24 | 16.777.216 | 11.043.226 | 5.645.023 | 5.398.203 | 5.520.157 | 0 | 5.523.069 | 0 |
25 | 33.554.432 | 22.134.273 | 11.305.690 | 10.828.583 | 11.067.464 | 0 | 11.066.809 | 0 |
26 | 67.108.864 | 44.357.864 | 22.637.750 | 21.720.114 | 22.179.283 | 0 | 22.178.581 | 0 |
27 | 134.217.728 | 88.881.036 | 45.319.449 | 43.561.587 | 44.442.896 | 0 | 44.438.140 | 0 |
28 | 268.435.456 | 178.062.116 | 90.718.105 | 87.344.011 | 89.028.573 | 0 | 89.033.543 | 0 |
29 | 536.870.912 | 356.697.152 | 181.617.979 | 175.079.173 | 178.349.404 | 0 | 178.347.748 | 0 |
30 | 1.073.741.824 | 714.445.721 | 363.493.073 | 350.952.648 | 357.229.433 | 0 | 357.216.288 | 0 |
31 | 2.147.483.648 | 1.430.860.986 | 727.560.774 | 703.300.212 | 715.429.492 | 0 | 715.431.494 | 0 |
32 | 4.294.967.296 | 2.865.381.979 | 1.456.149.236 | 1.409.232.743 | 1.432.663.671 | 0 | 1.432.718.308 | 0 |
33 | 8.589.934.592 | 5.737.663.303 | 2.914.225.614 | 2.823.437.689 | 2.868.806.516 | 0 | 2.868.856.787 | 0 |
34 | 17.179.869.184 | 11.488.312.175 | 5.832.117.965 | 5.656.194.210 | 5.744.168.119 | 0 | 5.744.144.056 | 0 |
35 | 34.359.738.368 | 23.001.119.272 | 11.671.204.537 | 11.329.914.735 | 11.500.598.218 | 0 | 11.500.521.054 | 0 |
36 | 68.719.476.736 | 46.048.276.101 | 23.355.396.026 | 22.692.880.075 | 23.024.208.905 | 0 | 23.024.067.196 | 0 |
5. a) Table of the amount of divisions
The values from 2 up to 224 are not listed because the used algorithm had
a first level cache segment in order to speed up the algorithm and
therefore the resulting values were not right.
A |
B |
C |
D |
E |
2^n |
x |
amount of divisons |
B*log( log (B; 3); 3) |
C/B |
25 |
33.554.432 |
83.524.162 |
84.246.004 |
2,49 |
26 |
67.108.864 |
161.330.817 |
170.887.811 |
2,40 |
27 |
134.217.728 |
332.155.442 |
346.386.366 |
2,47 |
28 |
268.435.456 |
662.288.896 |
701.658.821 |
2,47 |
29 |
536.870.912 |
1.348.539.023 |
1.420.466.101 |
2,51 |
30 |
1.073.741.824 |
2.728.193.442 |
2.874.066.288 |
2,54 |
31 |
2.147.483.648 |
5.532.461.967 |
5.812.227.625 |
2,58 |
32 |
4.294.967.296 |
11.199.801.794 |
11.748.575.126 |
2,61 |
33 |
8.589.934.592 |
22.682.503.676 |
23.737.750.633 |
2,64 |
34 |
17.179.869.184 |
45.891.918.142 |
47.942.335.660 |
2,67 |
35 |
34.359.738.368 |
92.828.721.324 |
96.791.273.397 |
2,70 |
36 |
68.719.476.736 |
187.668.985.522 |
195.344.667.920 |
2,73 |
37 |
137.438.953.472 |
379.269.618.308 |
394.117.011.261 |
2,76 |
38 |
274.877.906.944 |
766.168.931.008 |
794.906.542.041 |
2,79 |
39 |
549.755.813.888 |
1.547.202.551.607 |
1.602.811.459.228 |
2,81 |
40 |
1.099.511.627.776 |
3.123.330.927.170 |
3.230.961.451.946 |
2,84 |
41 |
2.199.023.255.552 |
6.303.055.060.506 |
6.511.348.556.497 |
2,87 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5. b) Table of the use of memory
The first column gives the amount of memory if the primes are stored for the first appearance,
the second column gives the amount of memory if the primes are stored for the second appearance.
n |
kbyte |
kbyte |
B(n+1)/B(n) |
C(n+1)/C(n) |
218 |
1472 |
1400 |
|
|
220 |
2000 |
1740 |
1,36 |
1,24 |
222 |
5520 |
2940 |
2,76 |
1,69 |
224 |
12800 |
9196 |
2,32 |
3,13 |
226 |
37000 |
25946 |
2,89 |
2,82 |
228 |
131000 |
83940 |
3,54 |
3,24 |
230 |
481000 |
300000 |
3,67 |
3,57 |
232 |
1800000 |
1125000 |
3,74 |
3,75 |
5. c) Estimation of the runtime and efficiency
An upper limit for the runtime is O(N*ln(ln(N)) where N is the huge of the field.
The algorithm finds approximately 0.7*N primes in a disorder by huge.
For comparison to the sieve of Eratosthenes:
The runtime of the sieve of Eratosthenes is also O(N*ln(ln(N)), by finding approximately N/ln(N) primes in order by huge.
For comparison to the sieve of Atkin:
The runtime of the sieve of Atkin is O(N/log log (N)), by finding approximately N/ln(N) primes in order by huge.
6. Mathematical theory
Let f(x) = x2 + 1 with x element of N
The following lemmas explain the mathematical background which is used for the described algorithms.
a) Lemma: If p | f(x) then also p | f(x+p)
p | f(x) <=> x2 + 1 = 0 mod p
p | f(x+p) <=> (x+p)2 + 1 = 0 mod p
<=> x2 + 2xp + p2 + 1 = 0 mod p
<=> x2 + 1 = 0 mod p
Thus if p | f(x) then p | f(x+p)
Example: p=42+1=17 so 17 | (4+17)2+1 = 442 = 2*13*17
b) Lemma: If p | f(x) then also p | f(-x)
p | f(x) <=> x2 + 1 = 0 mod p
p | f(-x) <=> (-x)2 + 1 = 0 mod p
<=> x2 + 1 = 0 mod p
Thus if p | f(x) then p | f(-x)
Example: p=42+1=17 so 17 | (-4)2+1 = 17
c) Lemma: If p | f(-x) then also p | f(-x+p)
This is a simple conclusion of b) and c) and means that
if p is a divisor of f(x) then p appears periodically concerning the function values of f(x)=x2+1
at f(x) and f(-x) with the period length p
Example: p=(-4)2+1=17 so 17 | (-4+17)2+1 = 170 =2*5*17
d) Lemma: f(x) mod 8 = {1, 2, 5}
f(0)=1, f(1)=2, f(2)=5, f(3)=10 = 2 mod 8, f(4)=17 = 1 mod 8,
f(5)=26 = 2 mod 8, f(6)=37 = 1 mod 8, f(7)=50 = 2 mod 8
e) Lemma: If p | f(x) with p is a prime then jacobi (-1, p) = 1
because the discriminant of f(x)=x2+1 is -1
If p divides f(x), then p divides (4 k2 + 1) which implies
that p is the sum of two squares which implies that p = 1 mod 4
which implies that jacobi(-1,p) = 1.
f) Lemma: If p is a primitiv prime factor resp. if p | f(x) with the smallest x>0
then p > x
The divisor p of f(x) appears periodically in the sequence of f(x) with x=0 up to oo
respectively if p | f(x) then p | f(x+p) and especially p | f(x-p).
supposing that p<=x then p would be found earlier by the described algorithm and would be sieved out.
Therefore if p divides f(x) then p is greater than x
g) Lemma: If p is a primitiv prime factor resp. if p | f(x) with the smallest x>0
then p > 2x with p>2
f(x)=f(-x)
if p<=2x then p has to appear as divisor in the interval [f(-x), f(x)]
especially in the interval [f(0), f(x)] because the function terms of f(-x) are the same as f(x).
Lemma f) shows that this is not possible.
h) Lemma: Let f'(x+1) the natural number which remains
when f(x+1) is divided as often as possible by f'(x) with x from 0 up to x-1
if f'(x+1)>1 then f'(x+1) is a primitiv prime factor and a Stormer prime
Supposing f'(y) is not a prime, f'(y)=p*q with p, q element N greater than 1
p > 2y, q > 2y (Lemma g))
f(y)=y2+1 > f'(y) = p*q > (2y)(2y) = 4y2 which is a contradiction.
i) Lemma: If f''(x+1) is a natural number which remains when f''(x+1) is divided as often as possible
by the second appearance of the prime f''(x) with x from 0 up to x-1
and f''(x+1) > 1 then f''(x+1) is a prime
proof by induction:
for n=0 f(0)=1
n=1 f(1)=2
n=2 f(2)=5
n=3 f(3)=10=2*5 (second appearance for p=5)
Supposing f''(x) is not equal 1 or not a prime after dividing all prime factors f''(x)
with x from 0 up to x-1
As f(x)=x2+1 is symmetrical to the y-axis, let there be the following construction :
f'(-x) is the natural number which remains when f(-x) is divided as often as possible
by the first appearance of the prime f'(-x) with x from 0 up to -x+1
f''(x) is the natural number which remains when f(x) is divided as often as possible
by the second appearance of the prime f''(x) with x from 0 up to x-1
p | f'(-x) <=> p | f''(p-x) (see Lemma c) )
if f''(p-x) is not equal 1 or a prime, then f'(-x) would also not be equal 1 or a prime,
that would be a contradiction to Lemma h)
j) The Hensel-lifting explains for every p|f(x) where p2|f(y) p3|f(z) ... pn|f(n) can be found.
k) Lemma: if p is a prime without the 2 and with p | f(x)=x2+1 then p | f(y)=4y2+1.
The substitution with x=2y gives this result.
Therefore all primes without the 2 which are divisor of the f(x)=x2+1 are a divisor of f(y)=4y2+1.
Nevertheless the sequence of the primes found by the described algorithm is not the same and
the Lemma i) is not true for the function f(y)=4y2+1
l) With the help of the chinese remainder it is possible to calculate a x
where f(x) is either a prime or the product of new primes
and f(x) is not divisible by the primes found before.
Example:
The first prime values for the polynom fx)=x2+1 are
f(0)=1
f(1)=2
f(2)=5
f(3)=1
f(4)=17
Supposing that the sequence f(5)-f(oo)=1
p1=2
p2=5
p3=17
are the first primes
choose a special x1, x2 and x3 for the primes
x1=2
x2=4
x3=5
(Other values are also possible, f(xi) should not be divisible by pi)
With the help of the chinese remainder theorem you could solve the equitations :
x=0 mod 2 f(0)=1 not divisible by 2
x=4 mod 5 f(4)=17 not divisible by 5
x=5 mod 17 f(5)=26 not divisible by 17
The solution is x=124 mod 170
f(124) is not divisible by the primes 2, 5, 17
f(124)=15377 which is by chance a primes.
By this way you could calculate a special x taking the first primes of the sequence calculated by the algorithm
and you get as result a special f(x) which is either a prime or consists of primes which are not yet in the sequence.
m) Lemma: if x+I is divisible by a+bI then x-I is divisible by a-bI and vice visa.
Proof: (x+I) / (a+bI) = (x+I)(a-bI)/(a2+b2) = (ax+b+aI-bxI)/(a2+b2) = (ax+b)/(a2+b2) + (a-bx)I / (a2+b2) = c + dI with x, a, b, c, d element of Z
(x-I) / (a-bI) = (x-I)(a+bI)/(a2+b2) = (ax+b-aI+bxI)/(a2+b2) = (ax+b)/(a2+b2) - (a-bx)I / (a2+b2) = c - dI
if (a+bI) / (c+dI) = e+fI then
(a-bI) / (c-dI) = e-fI
the proof is analogue to the sentence before.
n) Lemma: The sequence of primes with p = a2 + b2 is infinite.
p(x)= x2+1 = (x+I)(x-I)
Proof: Let p'(x) the prime > 2 for x > 1 which remains
when p(x) is divided as often as possible by f'(x) with x from 0 up to x-1
Then p'(x) could be written according Lemma q) as p*(x)=(a+bI)(a-bI) = a2+b2 with a, b element of Z
As the sequence of reducible primes is infinite (Lemma l)
the sequence of these primes as sum of two quadratic numbers is also infinite.
|
|