|
Development of Algorithmic Constructions |
04:11:31
| | | 18.Apr 2024
|
|
Prime sieving for the polynomial f(n)=n2+n+1
0. Abstract
1. Mathematical theory
2. Description of the basic algorithm
3. Programming and algorithms
a) Programing of the basic algorithm
b) Improved programming for speed in MuPad
c) Improved Programming for memory in MuPad
d) basic algorithm in the complex field
e) Used programm for the investigation in C with Heap
4. Results of the distribution of the primes
a) Table up to 1012 and table up to 240
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) Table of the memory requirements
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) Estimation of the runtime and efficiency
6. Sequences of primes and reference to Njas-Sequences
a) Primes of form n2 + n + 1
b) Prime divisors of {n2+n+1} which do not occur in that sequence
c) a(n) = number of distinct prime divisors (taken together) of numbers of the form x2+x+1 for x<=10n.
d) Sequence of all primes with p | n2+n+1 and p=1 by arising n
e) Sequence of all primes p | n2+n+1 by arising n
e) Generalized cuban primes: primes of the form x2 + xy + y2; or primes of the form x2 + 3*y2; or primes == 0 or 1 mod 3.
0. Abstract:
Similar to the quadratic polynom f(n)=n2+1 there are listed some algorithms
how to sieve the primes p(n)=n2+n+1 and the reducible primes with p | n2+n+1.
The distribution of both sort of the primes concerning this polynom is listed up to n=1012
respectively up to n=240.
The short programs are written in MuPad in order to indicate the basic ideas.
The program to determine the distribution of primes up to 1012 was written in C,
ran 2014 4 weeks on one core of Amd600 processor, used 2.1 gbyte Ram and 220 gbyte disc space.
The improved algorithm ran August 2015 on one core of Amd Fx (tm) 6300 with a raid 0 system with 4 hard disk 13 days
up to n=240 and used 6,5 gbyte Ram and 220 gbyte hard disc.
The algorithm is more effectiv than the sieve of Erathosthenes, the density of
primes and reducible primes is higher, but the sieved primes do not appear in a sort order.
The question if there are infinite primes of the form p(n)=n2+n+1 is not answered,
but regarding the distribution of all prime numbers, the primes p(n)=n2+n+1 and the reducible primes together,
it is very likely that the distribution of these primes is linear.
1. mathematical theory
Let f(x) = x2+x+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 + x+ 1 = 0 mod p
p | f(x+p) <=> (x+p)2 + (x+p) + 1 = 0 mod p
<=> x2 + 2xp + p2 + x + p + 1 = 0 mod p
<=> x2 + x +1 = 0 mod p
Thus if p | f(x) then p | f(x+p)
b) Lemma: If p | f(x) then also p | f(-x-1)
p | f(x) <=> x2 + x +1 = 0 mod p
p | f(-x-1) <=> (-x-1)2 -x-1 + 1 = 0 mod p
<=> x2+2x+1 -x-1 + 1 = 0 mod p
<=> x2 + x + 1 = 0 mod p
Thus if p | f(x) then p | f(-x-1)
c) Lemma: If p | f(-x-1) then also p | f(-x-1+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+x+1
at f(x) and f(-x-1) with the period length p
d) the prime number 3 divides only one time the polynom f(1+3k)
because 3 | f(-x-1+3k) with x=1 and k element N
<=> 3 | f(-1-1+3k)
<=> 3 | f(1+3k)
e) Lemma: if p | f(x) => p | f(x2)
f(x2) = f(x) (x2-x+1)
f) For every prime p with p=1 mod 6 there exist a x with p | f(x) and
there exist a x element N with p | f(x) (without the 3) so that p = 1 mod 6
p=1 mod 6 <=> p=/=3 and there exist on x element N with p | f(x)
"=>" p= 1 mod 6 => p odd and 3 | p-1
=> (Fp)* include an element with order 3
Let x element N, so that x' element Fp* has the order 3
=> x'3=1 and x=/=1
=> p|x3-1 and p does not divide x-1
=> p| x2+x+1 because x3-1=(x-1)(x2+x+1)
"<=" x2+x+1 is odd => p=/=2
it will do to show that 3 | p-1
if p|x-1 then p | ggt (x-1, x2+x+1) | 3 is a contradiction
=> p does not divide x-1
=> x'=/= 1 in Fp
x'=/= 0, since p does not divide x
=> x' has the order 3 in Fp*
since p|x2+x+1 | x3-1
=> 3 | p-1
with p=/=2 it follows that p=1 mod 6
g) Lemma: If p | f(x) with p is a prime then jacobi (-3, p) = 1
because the discriminant of f(x)=x2+x+1 is -3
h) 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(p-x-1).
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
i) The Hensel-lifting explains for every p|f(x) where p2|f(y) p3|f(z) ... pn|f(n) can be found.
j) 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.
2. Description of the basic algorithm
a) A list with the function terms f(x)=x2+x+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)=3, 3 is a prime.
As x+kp and p-x-1+kp with k element of N, resp. 1+3k and 3-1-1+3k describe the same values,
the prime 3 occurs only one time periodically in this sequence as divisor.
The prime 3 is a singularity, all other primes occur twice peridically in the sequence.
All function values f(1+3k) are divided by 3.
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-1+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
You get an unsorted list of primes as result.
Explication by example
a) Create a list from x=1 to x=list_max=100 with f(x)=x2+x+1
f(1)= 3
f(2)= 7
f(3)= 13
f(4)= 21 = 3*7
f(5)= 31
f(6)= 43
f(7)= 57 = 3*19
f(8)= 73
f(9)= 91 = 7*13
f(10)= 111 = 3*37
f(11)= 133 = 7*19
f(12)= 157
f(13)= 183 = 3*61
f(14)= 211
f(15)= 241
f(16)= 273 = 3*7*13
f(17)= 307
f(18)= 343 = 73
f(19)= 381 = 3*127
f(20)= 421
f(21)= 463
f(22)= 507 = 3*132
f(23)= 553 = 7*79
f(24)= 601
f(25)= 651 = 3*7*31
f(26)= 703 = 19*37
f(27)= 757
f(28)= 813 = 3*271
f(29)= 871 = 13*67
f(30)= 931 = 72*19
f(31)= 993 = 3*331
f(32)= 1057 = 7*151
f(33)= 1123
f(34)= 1191 = 3*397
f(35)= 1261 = 13*97
f(36)= 1333 = 31*43
f(37)= 1407 = 3*7*67
f(38)= 1483
f(39)= 1561 = 7*223
f(40)= 1641 = 3*547
f(41)= 1723
f(42)= 1807 = 13*139
f(43)= 1893 = 3*631
f(44)= 1981 = 7*283
f(45)= 2071 = 19*109
f(46)= 2163 = 3*7*103
f(47)= 2257 = 37*61
f(48)= 2353 = 13*181
f(49)= 2451 = 3*19*43
f(50)= 2551
f(51)= 2653 = 7*379
f(52)= 2757 = 3*919
f(53)= 2863 = 7*409
f(54)= 2971
f(55)= 3081 = 3*13*79
f(56)= 3193 = 31*103
f(57)= 3307
f(58)= 3423 = 3*7*163
f(59)= 3541
f(60)= 3661 = 7*523
f(61)= 3783 = 3*13*97
f(62)= 3907
f(63)= 4033 = 37*109
f(64)= 4161 = 3*19*73
f(65)= 4291 = 7*613
f(66)= 4423
f(67)= 4557 = 3*72*31
f(68)= 4693 = 13 192
f(69)= 4831
f(70)= 4971 = 3*1657
f(71)= 5113
f(72)= 5257 = 7*751
f(73)= 5403 = 3*1801
f(74)= 5551 = 7*13*61
f(75)= 5701
f(76)= 5853 = 3*1951
f(77)= 6007
f(78)= 6163
f(79)= 6321 = 3*72*43
f(80)= 6481
f(81)= 6643 = 7*13*73
f(82)= 6807 = 3*2269
f(83)= 6973 = 19*367
f(84)= 7141 = 37*193
f(85)= 7311 = 3*2437
f(86)= 7483 = 7*1069
f(87)= 7657 = 13*19*31
f(88)= 7833 = 3*7*373
f(89)= 8011
f(90)= 8191
f(91)= 8373 = 3*2791
f(92)= 8557 = 43*199
f(93)= 8743 = 7*1249
f(94)= 8931 = 3*13*229
f(95)= 9121 = 7*1303
f(96)= 9313 = 67*139
f(97)= 9507 = 3*3169
f(98)= 9703 = 31*313
f(99)= 9901
f(100)= 10101 = 3*7*13*37
b) f(1)=3, divide f(1+3k) / 3 with 1+k*3<=liste_max, k element N
c) f(2)=7, divide f(2+7k) / 7 as often as there is no factor 7 in the result.
You have to devide f(9), f(16), f(23), f(30), f(37), f(44), f(51), f(58), f(65), f(72), f(79), f(86), f(93) and f(100) by 7.
Divide f(7-2-1+7k) / 7 as often as there is no factor 7 in the result.
You have to divide f(4), f(11), f(18), f(25), f(32), f(39), f(46), f(53), f(60), f(67), f(74), f(81), f(88), f(95) on by 7.
d) Go for x from 3 to liste_max
if p=f*(x) > 1
divide f(x+pk) / p and
divide f(p-x-1+pk) / p
as often as there is no factor p in the result.
You get an unsorted list of primes as result.
3. a) Programming in MuPad for f(n)=n2+n+1:
This is a short implementation for the algorithm for the polynomial f(n)=n2+n+1.
As the prime 3 is a singularity, it is already sieved out by the initialisation of the list.
Every other prime which occurs is sieved out resp. divides periodically at two positions the initialised list. (for the proof see I. a), b) and c) )
The procedure sieving only divides as often as possible the function values of the list by the sieving primes.
- // numbers of the examined list
liste_max:=1000;
// number of primes which are found. It starts with 1 because of the 3 .
anz_prim:=1;
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 1 to liste_max do
if x mod 3 = 1 then
liste [x]:=(x2+x+1)/3;
else
liste [x]:=x2+x+1;
end_if;
end_for;
for x from 2 to liste_max do
p:=liste[x];
if (p>1) then
print (x, p);
anz_prim:=anz_prim+1;
sieving (x, p);
sieving (p-x-1, p);
end_if;
end_for;
You get an unsorted list of primes as result.
3. b) Improved Programming in MuPad for f(n)=n2+n+1:
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. h) )
- // numbers of the examined list
liste_max:=1000;
// number of primes which are found. It starts with 1 because of the 3 .
anz_prim:=1;
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 1 to liste_max do
if x mod 3 = 1 then
liste [x]:=(x2+x+1)/3;
else
liste [x]:=x2+x+1;
end_if;
end_for;
for x from 2 to liste_max/2 do
p:=liste[x];
if (p>1) then
print (x, p);
sieving (x, p);
sieving (p-x-1, 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-1, p);
end_if;
end_for;
You get an unsorted list of primes as result.
3. c) Improved Programming for memory in MuPad for f(n)=n2+n+1:
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.
- // numbers of the examined list
liste_max:=1000;
// number of primes which are found. It starts with 1 because of the 3 .
anz_prim:=1;
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 1 to liste_max do
if x mod 3 = 1 then
liste [x]:=(x2+x+1)/3;
else
liste [x]:=x2+x+1;
end_if;
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);
sieving (2*p-x-1, p);
else
// The primes which occures for the first time are printed
print (x, p);
end_if;
end_if;
end_for;
You get an unsorted list of primes as result.
3. d) basic algorithm in the complex field
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 number and the conjugated complex number p=(a+bi√3)*(a-bi√3)=a2+3b2
This algorithm is a possible way to generate these prime elments, although they are not ordered by huge.
// numbers of the examined list
liste_max:=100;
// square root of 3
root_3:=sqrt (3);
division_complex:=proc (zelle, p)
begin
c:=Re (p);
d:=Im (p);
erg_div:=(c*c+3*d*d);
repeat
// complex division with adjoined square root 3
// (a+b*srqt(3)*I)/(c+d*sqrt(3)*I)=(a+b*sqrt (3)*I)(c-d*sqrt(3)*I)/(c2+3*d2)
// =[ac+3*bd+(-ad+bc)*sqrt(3)*I]/(c2+3*d2)
a:=Re (zelle);
b:=Im (zelle);
erg_re:=(a*c+3*b*d)/erg_div;
erg_im:=(-a*d+b*c)/erg_div;
// if complex result 2*erg_re or 2*erg_im not element of N return
if ((domtype (2*erg_re) <> DOM_INT) or (domtype (2*erg_im) <> DOM_INT))
then
return (a+b*I);
end_if;
// If complex division o.k.
zelle:=erg_re+erg_im*I;
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;
// the adjoined square root of 3 is not initialized,
// but is implemented in the complex division
for x from 1 to liste_max do
liste [x]:=1/2+x+I/2;
end_for;
for x from 1 to liste_max do
p:=liste[x];
prim:=(Re (p))2+3*(Im(p))2;
if (prim>1) then
print ("x=", x, "prim = ", prim, "=", p,"*", root_3, "*", conjugate (p),"*", root_3);
sieving (x+prim, p, prim);
if prim>3 then
sieving (prim-x-1, conjugate (p), prim);
end_if;
end_if;
end_for;
x= 1, prim = 3 = ( 3/2 + 1/2 I√3 ) * ( 3/2 - 1/2 I√3)
x= 2, prim = 7 = ( 5/2 + 1/2 I√3 ) * ( 5/2 - 1/2 I√3 )
x= 3, prim = 13 = ( 7/2 + 1/2 I√3 ) * ( 7/2 - 1/2 I√3 )
x= 5, prim = 31 = ( 11/2 + 1/2 I√3 ) * ( 11/2 - 1/2 I√3 )
x= 6, prim = 43 = ( 13/2 + 1/2 I√3 ) * ( 13/2 - 1/2 I√3 )
x= 7, prim = 19 = ( 4 - I√3 ) * ( 4 + I√3 )
x= 8, prim = 73 = ( 17/2 + 1/2 I√3 ) * ( 17/2 - 1/2 I√3 )
x= 10, prim = 37 = ( 11/2 - 3/2 I√3 ) * ( 11/2 + 3/2 I√3 )
x= 12, prim = 157 = ( 25/2 + 1/2 I√3 ) * ( 25/2 - 1/2 I√3 )
x= 13, prim = 61 = ( 7 - 2 I√3 ) * ( 7 + 2 I√3 )
x= 14, prim = 211 = ( 29/2 + 1/2 I√3 ) * ( 29/2 - 1/2 I√3 )
x= 15, prim = 241 = ( 31/2 + 1/2 I√3 ) * ( 31/2 - 1/2 I√3 )
x= 17, prim = 307 = ( 35/2 + 1/2 I√3 ) * ( 35/2 - 1/2 I√3 )
x= 19, prim = 127 = ( 10 - 3 I√3 ) * ( 10 + 3 I√3 )
x= 20, prim = 421 = ( 41/2 + 1/2 I√3 ) * ( 41/2 - 1/2 I√3 )
x= 21, prim = 463 = ( 43/2 + 1/2 I√3 ) * ( 43/2 - 1/2 I√3 )
x= 23, prim = 79 = ( 17/2 - 3/2 I√3 ) * ( 17/2 + 3/2 I√3 )
x= 24, prim = 601 = ( 49/2 + 1/2 I√3 ) * ( 49/2 - 1/2 I√3 )
x= 27, prim = 757 = ( 55/2 + 1/2 I√3 ) * ( 55/2 - 1/2 I√3 )
x= 28, prim = 271 = ( 29/2 - 9/2 I√3 ) * ( 29/2 + 9/2 I√3 )
x= 29, prim = 67 = ( 8 - I√3 ) * ( 8 + I√3 )
x= 31, prim = 331 = ( 16 - 5 I√3 ) * ( 16 + 5 I√3 )
x= 32, prim = 151 = ( 23/2 + 5/2 I√3 ) * ( 23/2 - 5/2 I√3 )
x= 33, prim = 1123 = ( 67/2 + 1/2 I√3 ) * ( 67/2 - 1/2 I√3 )
x= 34, prim = 397 = ( 35/2 - 11/2 I√3 ) * ( 35/2 + 11/2 I√3 )
x= 35, prim = 97 = ( 19/2 + 3/2 I√3 ) * ( 19/2 - 3/2 I√3 )
x= 38, prim = 1483 = ( 77/2 + 1/2 I√3 ) * ( 77/2 - 1/2 I√3 )
x= 39, prim = 223 = ( 14 + 3 I√3 ) * ( 14 - 3 I√3 )
x= 40, prim = 547 = ( 41/2 - 13/2 I√3 ) * ( 41/2 + 13/2 I√3 )
x= 41, prim = 1723 = ( 83/2 + 1/2 I√3 ) * ( 83/2 - 1/2 I√3 )
x= 42, prim = 139 = ( 23/2 - 3/2 I√3 ) * ( 23/2 + 3/2 I√3 )
x= 43, prim = 631 = ( 22 - 7 I√3 ) * ( 22 + 7 I√3 )
x= 44, prim = 283 = ( 16 - 3 I√3 ) * ( 16 + 3 I√3 )
x= 45, prim = 109 = ( 19/2 + 5/2 I√3 ) * ( 19/2 - 5/2 I√3 )
x= 46, prim = 103 = ( 10 - I√3 ) * ( 10 + I√3 )
x= 48, prim = 181 = ( 13 + 2 I√3 ) * ( 13 - 2 I√3 )
x= 50, prim = 2551 = ( 101/2 + 1/2 I√3 ) * ( 101/2 - 1/2 I√3 )
x= 51, prim = 379 = ( 37/2 - 7/2 I√3 ) * ( 37/2 + 7/2 I√3 )
x= 52, prim = 919 = ( 53/2 - 17/2 I√3 ) * ( 53/2 + 17/2 I√3 )
x= 53, prim = 409 = ( 19 + 4 I√3 ) * ( 19 - 4 I√3 )
x= 54, prim = 2971 = ( 109/2 + 1/2 I√3 ) * ( 109/2 - 1/2 I√3 )
x= 57, prim = 3307 = ( 115/2 + 1/2 I√3 ) * ( 115/2 - 1/2 I√3 )
x= 58, prim = 163 = ( 17/2 - 11/2 I√3 ) * ( 17/2 + 11/2 I√3 )
x= 59, prim = 3541 = ( 119/2 + 1/2 I√3 ) * ( 119/2 - 1/2 I√3 )
x= 60, prim = 523 = ( 43/2 + 9/2 I√3 ) * ( 43/2 - 9/2 I√3 )
x= 62, prim = 3907 = ( 125/2 + 1/2 I√3 ) * ( 125/2 - 1/2 I√3 )
x= 65, prim = 613 = ( 47/2 - 9/2 I√3 ) * ( 47/2 + 9/2 I√3 )
x= 66, prim = 4423 = ( 133/2 + 1/2 I√3 ) * ( 133/2 - 1/2 I√3 )
x= 69, prim = 4831 = ( 139/2 + 1/2 I√3 ) * ( 139/2 - 1/2 I√3 )
x= 70, prim = 1657 = ( 71/2 - 23/2 I√3 ) * ( 71/2 + 23/2 I√3 )
x= 71, prim = 5113 = ( 143/2 + 1/2 I√3 ) * ( 143/2 - 1/2 I√3 )
x= 72, prim = 751 = ( 26 - 5 I√3 ) * ( 26 + 5 I√3 )
x= 73, prim = 1801 = ( 37 - 12 I√3 ) * ( 37 + 12 I√3 )
x= 75, prim = 5701 = ( 151/2 + 1/2 I√3 ) * ( 151/2 - 1/2 I√3 )
x= 76, prim = 1951 = ( 77/2 - 25/2 I√3 ) * ( 77/2 + 25/2 I√3 )
x= 77, prim = 6007 = ( 155/2 + 1/2 I√3 ) * ( 155/2 - 1/2 I√3 )
x= 78, prim = 6163 = ( 157/2 + 1/2 I√3 ) * ( 157/2 - 1/2 I√3 )
x= 80, prim = 6481 = ( 161/2 + 1/2 I√3 ) * ( 161/2 - 1/2 I√3 )
x= 82, prim = 2269 = ( 83/2 - 27/2 I√3 ) * ( 83/2 + 27/2 I√3 )
x= 83, prim = 367 = ( 35/2 + 9/2 I√3 ) * ( 35/2 - 9/2 I√3 )
x= 84, prim = 193 = ( 25/2 + 7/2 I√3 ) * ( 25/2 - 7/2 I√3 )
x= 85, prim = 2437 = ( 43 - 14 I√3 ) * ( 43 + 14 I√3 )
x= 86, prim = 1069 = ( 31 - 6 I√3 ) * ( 31 + 6 I√3 )
x= 88, prim = 373 = ( 19 - 2 I√3 ) * ( 19 + 2 I√3 )
x= 89, prim = 8011 = ( 179/2 + 1/2 I√3 ) * ( 179/2 - 1/2 I√3 )
x= 90, prim = 8191 = ( 181/2 + 1/2 I√3 ) * ( 181/2 - 1/2 I√3 )
x= 91, prim = 2791 = ( 46 - 15 I√3 ) * ( 46 + 15 I√3 )
x= 92, prim = 199 = ( 14 - I√3 ) * ( 14 + I√3 )
x= 93, prim = 1249 = ( 67/2 - 13/2 I√3 ) * ( 67/2 + 13/2 I√3 )
x= 94, prim = 229 = ( 11 - 6 I√3 ) * ( 11 + 6 I√3 )
x= 95, prim = 1303 = ( 34 + 7 I√3 ) . * 34 - 7 I√3 )
x= 97, prim = 3169 = ( 49 - 16 I√3 ) * ( 49 + 16 I√3 )
x= 98, prim = 313 = ( 35/2 - 3/2 I√3 ) * ( 35/2 + 3/2 I√3 )
x= 99, prim = 9901 = ( 199/2 + 1/2 I√3 ) * ( 199/2 - 1/2 I√3 )
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+x+1
Column E = reducible primes with p | x2+x+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+x+1 |
P(x) | x^2+x+1 |
C/B |
D/B |
E/B |
C(n) / C(n-1) |
D(n) / D(n-1) |
E(n) / E(n-1) |
|
1 |
10 |
8 |
6 |
2 |
0,800000 |
0,600000 |
0,200000 |
|
|
|
|
2 |
100 |
74 |
32 |
42 |
0,740000 |
0,320000 |
0,420000 |
9,250000 |
5,333333 |
21,000000 |
|
3 |
1.000 |
734 |
189 |
545 |
0,734000 |
0,189000 |
0,545000 |
9,918919 |
5,906250 |
12,976190 |
|
4 |
10.000 |
7.233 |
1.410 |
5.823 |
0,723300 |
0,141000 |
0,582300 |
9,854223 |
7,460317 |
10,684404 |
|
5 |
100.000 |
71.653 |
10.751 |
60.902 |
0,716530 |
0,107510 |
0,609020 |
9,906401 |
7,624823 |
10,458870 |
|
6 |
1.000.000 |
712.026 |
88.118 |
623.908 |
0,712026 |
0,088118 |
0,623908 |
9,937142 |
8,196261 |
10,244458 |
|
7 |
10.000.000 |
7.090.655 |
745.582 |
6.345.073 |
0,709066 |
0,074558 |
0,634507 |
9,958421 |
8,461177 |
10,169886 |
|
8 |
100.000.000 |
70.686.855 |
6.456.835 |
64.230.020 |
0,706869 |
0,064568 |
0,642300 |
9,969016 |
8,660127 |
10,122818 |
|
9 |
1.000.000.000 |
705.173.825 |
56.988.601 |
648.185.224 |
0,705174 |
0,056989 |
0,648185 |
9,976025 |
8,826089 |
10,091624 |
|
10 |
10.000.000.000 |
7.038.475.146 |
510.007.598 |
6.528.467.548 |
0,703848 |
0,051001 |
0,652847 |
9,981192 |
8,949291 |
10,071917 |
|
11 |
100.000.000.000 |
70.278.276.834 |
4.615.215.645 |
65.663.061.189 |
0,702783 |
0,046152 |
0,656631 |
9,984872 |
9,049308 |
10,057959 |
|
12 |
1.000.000.000.000 |
701.910.715.473 |
42.147.956.485 |
659.762.758.988 |
0,701911 |
0,042148 |
0,659763 |
9,987591 |
9,132392 |
10,047700 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
|
2^n |
x |
all Primes |
P(x)=x^2+x+1 |
P(x) | x^2+x+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 |
7 |
6 |
1 |
0,875000 |
0,750000 |
0,125000 |
2,333333 |
2,000000 |
|
|
4 |
16 |
12 |
9 |
3 |
0,750000 |
0,562500 |
0,187500 |
1,714286 |
1,500000 |
3,000000 |
|
5 |
32 |
23 |
14 |
9 |
0,718750 |
0,437500 |
0,281250 |
1,916667 |
1,555556 |
3,000000 |
|
6 |
64 |
46 |
22 |
24 |
0,718750 |
0,343750 |
0,375000 |
2,000000 |
1,571429 |
2,666667 |
|
7 |
128 |
95 |
38 |
57 |
0,742188 |
0,296875 |
0,445313 |
2,065217 |
1,727273 |
2,375000 |
|
8 |
256 |
189 |
66 |
123 |
0,738281 |
0,257813 |
0,480469 |
1,989474 |
1,736842 |
2,157895 |
|
9 |
512 |
375 |
108 |
267 |
0,732422 |
0,210938 |
0,521484 |
1,984127 |
1,636364 |
2,170732 |
|
10 |
1.024 |
751 |
196 |
555 |
0,733398 |
0,191406 |
0,541992 |
2,002667 |
1,814815 |
2,078652 |
|
11 |
2.048 |
1.490 |
352 |
1.138 |
0,727539 |
0,171875 |
0,555664 |
1,984021 |
1,795918 |
2,050450 |
|
12 |
4.096 |
2.968 |
654 |
2.314 |
0,724609 |
0,159668 |
0,564941 |
1,991946 |
1,857955 |
2,033392 |
|
13 |
8.192 |
5.923 |
1.174 |
4.749 |
0,723022 |
0,143311 |
0,579712 |
1,995620 |
1,795107 |
2,052290 |
|
14 |
16.384 |
11.799 |
2.167 |
9.632 |
0,720154 |
0,132263 |
0,587891 |
1,992065 |
1,845826 |
2,028216 |
|
15 |
32.768 |
23.581 |
3.951 |
19.630 |
0,719635 |
0,120575 |
0,599060 |
1,998559 |
1,823258 |
2,037998 |
|
16 |
65.536 |
47.003 |
7.364 |
39.639 |
0,717209 |
0,112366 |
0,604843 |
1,993257 |
1,863832 |
2,019307 |
|
17 |
131.072 |
93.873 |
13.780 |
80.093 |
0,716194 |
0,105133 |
0,611061 |
1,997170 |
1,871266 |
2,020561 |
|
18 |
262.144 |
187.285 |
25.776 |
161.509 |
0,714436 |
0,098328 |
0,616108 |
1,995089 |
1,870537 |
2,016518 |
|
19 |
524.288 |
373.890 |
48.561 |
325.329 |
0,713139 |
0,092623 |
0,620516 |
1,996369 |
1,883962 |
2,014309 |
|
20 |
1.048.576 |
746.565 |
91.980 |
654.585 |
0,711980 |
0,087719 |
0,624261 |
1,996750 |
1,894113 |
2,012071 |
|
21 |
2.097.152 |
1.491.178 |
174.691 |
1.316.487 |
0,711049 |
0,083299 |
0,627750 |
1,997385 |
1,899228 |
2,011178 |
|
22 |
4.194.304 |
2.978.399 |
331.924 |
2.646.475 |
0,710106 |
0,079137 |
0,630969 |
1,997346 |
1,900064 |
2,010255 |
|
23 |
8.388.608 |
5.949.603 |
632.763 |
5.316.840 |
0,709248 |
0,075431 |
0,633817 |
1,997584 |
1,906349 |
2,009027 |
|
24 |
16.777.216 |
11.887.260 |
1.208.189 |
10.679.071 |
0,708536 |
0,072014 |
0,636522 |
1,997992 |
1,909386 |
2,008537 |
|
25 |
33.554.432 |
23.751.260 |
2.314.216 |
21.437.044 |
0,707843 |
0,068969 |
0,638874 |
1,998043 |
1,915442 |
2,007388 |
|
26 |
67.108.864 |
47.460.078 |
4.435.345 |
43.024.733 |
0,707210 |
0,066092 |
0,641118 |
1,998213 |
1,916565 |
2,007027 |
|
27 |
134.217.728 |
94.842.057 |
8.521.876 |
86.320.181 |
0,706628 |
0,063493 |
0,643135 |
1,998354 |
1,921356 |
2,006292 |
|
28 |
268.435.456 |
189.538.866 |
16.398.035 |
173.140.831 |
0,706087 |
0,061087 |
0,645000 |
1,998469 |
1,924228 |
2,005798 |
|
29 |
536.870.912 |
378.811.001 |
31.594.046 |
347.216.955 |
0,705590 |
0,058848 |
0,646742 |
1,998593 |
1,926697 |
2,005402 |
|
30 |
1.073.741.824 |
757.129.245 |
60.971.160 |
696.158.085 |
0,705132 |
0,056784 |
0,648348 |
1,998699 |
1,929831 |
2,004966 |
|
31 |
2.147.483.648 |
1.513.336.004 |
117.790.467 |
1.395.545.537 |
0,704702 |
0,054850 |
0,649852 |
1,998782 |
1,931905 |
2,004639 |
|
32 |
4.294.967.296 |
3.024.943.674 |
227.834.670 |
2.797.109.004 |
0,704300 |
0,053047 |
0,651253 |
1,998858 |
1,934237 |
2,004312 |
|
33 |
8.589.934.592 |
6.046.677.752 |
441.146.458 |
5.605.531.294 |
0,703926 |
0,051356 |
0,652570 |
1,998939 |
1,936257 |
2,004045 |
|
34 |
17.179.869.184 |
12.087.378.076 |
855.066.149 |
11.232.311.927 |
0,703578 |
0,049771 |
0,653807 |
1,999011 |
1,938282 |
2,003791 |
|
35 |
34.359.738.368 |
24.163.506.862 |
1.658.944.367 |
22.504.562.495 |
0,703251 |
0,048282 |
0,654969 |
1,999069 |
1,940136 |
2,003556 |
|
36 |
68.719.476.736 |
48.305.814.739 |
3.221.420.579 |
45.084.394.160 |
0,702942 |
0,046878 |
0,656064 |
1,999123 |
1,941850 |
2,003345 |
|
37 |
137.438.953.472 |
96.571.785.730 |
6.260.940.939 |
90.310.844.791 |
0,702652 |
0,045554 |
0,657098 |
1,999175 |
1,943534 |
2,003151 |
|
38 |
274.877.906.944 |
193.068.599.918 |
12.178.042.506 |
180.890.557.412 |
0,702379 |
0,044303 |
0,658076 |
1,999224 |
1,945082 |
2,002977 |
|
39 |
549.755.813.888 |
385.995.468.449 |
23.705.328.837 |
362.290.139.612 |
0,702122 |
0,043120 |
0,659002 |
1,999266 |
1,946563 |
2,002814 |
|
40 |
1.099.511.627.776 |
771.723.207.036 |
46.177.161.928 |
725.546.045.108 |
0,701878 |
0,041998 |
0,659880 |
1,999306 |
1,947965 |
2,002666 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The distribution of the reducible primes of the form p|x2+x+1 is linear.
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+x+1
The orange dots / column G are the values for the primes with p=x2+x+1
The yellow dots / column H are the values for the primes by the first occurance with p|x2+x+1 and p smaller than x2+x+1
The x-axis is the logarithm to the base of 2 and goes up to 2^40
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+x+1 |
P(x)=x^2+x+1 |
C / D |
ln(B) |
|
|
|
|
|
|
1 |
2 |
0 |
2 |
0,0000 |
0,70 |
2 |
4 |
0 |
3 |
0,0000 |
1,39 |
3 |
8 |
1 |
4 |
0,2500 |
2,09 |
4 |
16 |
3 |
7 |
0,4286 |
2,78 |
5 |
32 |
9 |
10 |
0,9000 |
3,48 |
6 |
64 |
24 |
14 |
1,7143 |
4,17 |
7 |
128 |
57 |
24 |
2,3750 |
4,87 |
8 |
256 |
123 |
43 |
2,8605 |
5,56 |
9 |
512 |
267 |
70 |
3,8143 |
6,26 |
10 |
1.024 |
555 |
114 |
4,8684 |
6,95 |
11 |
2.048 |
1.138 |
212 |
5,3679 |
7,65 |
12 |
4.096 |
2.314 |
393 |
5,8880 |
8,34 |
13 |
8.192 |
4.749 |
713 |
6,6606 |
9,04 |
14 |
16.384 |
9.632 |
1.301 |
7,4035 |
9,73 |
15 |
32.768 |
19.630 |
2.459 |
7,9829 |
10,43 |
16 |
65.536 |
39.639 |
4.615 |
8,5892 |
11,12 |
17 |
131.072 |
80.093 |
8.418 |
9,5145 |
11,82 |
18 |
262.144 |
161.509 |
15.867 |
10,1789 |
12,51 |
19 |
524.288 |
325.329 |
29.843 |
10,9014 |
13,21 |
20 |
1.048.576 |
654.585 |
56.534 |
11,5786 |
13,91 |
21 |
2.097.152 |
1.316.487 |
106.787 |
12,3282 |
14,60 |
22 |
4.194.304 |
2.646.475 |
203.025 |
13,0352 |
15,30 |
23 |
8.388.608 |
5.316.840 |
387.308 |
13,7277 |
15,99 |
24 |
16.777.216 |
10.679.071 |
739.671 |
14,4376 |
16,69 |
25 |
33.554.432 |
21.437.044 |
1.416.635 |
15,1324 |
17,38 |
26 |
67.108.864 |
43.024.733 |
2.716.922 |
15,8358 |
18,08 |
27 |
134.217.728 |
86.320.181 |
5.218.926 |
16,5398 |
18,77 |
28 |
268.435.456 |
173.140.831 |
10.044.585 |
17,2372 |
19,47 |
29 |
536.870.912 |
347.216.955 |
19.352.155 |
17,9420 |
20,16 |
30 |
1.073.741.824 |
696.158.085 |
37.339.024 |
18,6442 |
20,86 |
31 |
2.147.483.648 |
1.395.545.537 |
72.139.395 |
19,3451 |
21,55 |
32 |
4.294.967.296 |
2.797.109.004 |
139.535.723 |
20,0458 |
22,25 |
33 |
8.589.934.592 |
5.605.531.294 |
270.187.320 |
20,7468 |
22,94 |
34 |
17.179.869.184 |
11.232.311.927 |
523.695.185 |
21,4482 |
23,64 |
35 |
34.359.738.368 |
22.504.562.495 |
1.016.029.276 |
22,1495 |
24,33 |
36 |
68.719.476.736 |
45.084.394.160 |
1.973.029.796 |
22,8503 |
25,03 |
37 |
137.438.953.472 |
90.310.844.791 |
3.834.641.365 |
23,5513 |
25,72 |
38 |
274.877.906.944 |
180.890.557.412 |
7.458.662.439 |
24,2524 |
26,42 |
39 |
549.755.813.888 |
362.290.139.612 |
14.518.923.631 |
24,9530 |
27,12 |
|
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 |
3 |
3 |
3 |
3 |
6 |
7 |
7 |
7 |
7 |
7 |
11 |
11 |
11 |
11 |
8 |
20 |
20 |
20 |
20 |
9 |
37 |
37 |
37 |
37 |
10 |
69 |
69 |
69 |
69 |
11 |
87 |
126 |
126 |
126 |
12 |
85 |
228 |
228 |
228 |
13 |
78 |
434 |
434 |
434 |
14 |
69 |
806 |
806 |
806 |
15 |
64 |
1.514 |
1.514 |
1.514 |
16 |
64 |
2.845 |
2.845 |
2.845 |
17 |
49 |
5.361 |
5.361 |
5.361 |
18 |
48 |
10.212 |
10.212 |
10.212 |
19 |
55 |
19.308 |
19.308 |
19.308 |
20 |
0 |
36.747 |
36.747 |
36.747 |
21 |
0 |
48.713 |
70.135 |
70.135 |
22 |
0 |
46.650 |
134.065 |
134.065 |
23 |
0 |
44.625 |
256.824 |
256.824 |
24 |
0 |
42.794 |
492.871 |
492.871 |
25 |
0 |
40.982 |
946.880 |
946.880 |
26 |
0 |
39.314 |
1.822.913 |
1.822.913 |
27 |
0 |
38.183 |
3.513.737 |
3.513.737 |
28 |
0 |
36.740 |
6.780.428 |
6.780.428 |
29 |
0 |
35.689 |
13.103.565 |
13.103.565 |
30 |
0 |
34.356 |
25.348.226 |
25.348.226 |
31 |
0 |
33.554 |
34.086.393 |
49.090.715 |
32 |
0 |
32.125 |
33.038.159 |
95.167.496 |
33 |
0 |
31.099 |
32.059.553 |
184.660.541 |
34 |
0 |
30.320 |
31.120.890 |
358.633.265 |
35 |
0 |
29.362 |
30.247.230 |
697.094.862 |
36 |
0 |
28.226 |
29.419.856 |
1.356.047.971 |
37 |
0 |
26.755 |
28.632.263 |
2.639.884.795 |
38 |
0 |
24.195 |
27.894.420 |
5.142.811.282 |
39 |
0 |
25.150 |
27.188.566 |
10.025.585.207 |
40 |
0 |
0 |
26.516.117 |
13.574.841.000 |
41 |
0 |
0 |
25.874.448 |
13.247.668.352 |
42 |
0 |
0 |
25.265.397 |
12.936.010.582 |
43 |
0 |
0 |
24.694.125 |
12.638.687.170 |
44 |
0 |
0 |
24.128.068 |
12.354.516.974 |
45 |
0 |
0 |
23.598.458 |
12.083.229.914 |
46 |
0 |
0 |
23.098.016 |
11.823.189.703 |
47 |
0 |
0 |
22.608.725 |
11.574.269.954 |
48 |
0 |
0 |
22.127.505 |
11.335.480.666 |
49 |
0 |
0 |
21.680.354 |
11.106.684.787 |
50 |
0 |
0 |
21.268.889 |
10.886.634.325 |
51 |
0 |
0 |
20.893.169 |
10.675.271.435 |
52 |
0 |
0 |
20.386.570 |
10.471.790.797 |
53 |
0 |
0 |
19.933.674 |
10.276.116.672 |
54 |
0 |
0 |
19.773.645 |
10.087.589.864 |
55 |
0 |
0 |
19.180.735 |
9.905.740.239 |
56 |
0 |
0 |
18.654.719 |
9.730.442.118 |
57 |
0 |
0 |
17.838.897 |
9.561.161.721 |
58 |
0 |
0 |
16.283.684 |
9.397.801.824 |
59 |
0 |
0 |
17.089.343 |
9.239.837.062 |
60 |
0 |
0 |
0 |
9.087.035.450 |
61 |
0 |
0 |
0 |
8.939.225.150 |
62 |
0 |
0 |
0 |
8.795.971.539 |
63 |
0 |
0 |
0 |
8.657.913.816 |
64 |
0 |
0 |
0 |
8.524.602.270 |
65 |
0 |
0 |
0 |
8.393.416.950 |
66 |
0 |
0 |
0 |
8.264.532.042 |
67 |
0 |
0 |
0 |
8.139.698.249 |
68 |
0 |
0 |
0 |
8.028.276.480 |
69 |
0 |
0 |
0 |
7.928.588.350 |
70 |
0 |
0 |
0 |
7.772.636.163 |
71 |
0 |
0 |
0 |
7.635.428.845 |
72 |
0 |
0 |
0 |
7.610.978.371 |
73 |
0 |
0 |
0 |
7.415.486.920 |
74 |
0 |
0 |
0 |
7.246.828.529 |
75 |
0 |
0 |
0 |
6.956.456.587 |
76 |
0 |
0 |
0 |
6.373.759.060 |
77 |
0 |
0 |
0 |
6.716.145.008 |
|
|
|
|
4. e) Table of the distribution of all primes concerning their second appearance
A |
B |
C |
D |
E |
F |
|
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 |
1 |
2,0000 |
0,6953 |
2,01 |
2 |
4 |
3 |
1 |
3,0000 |
1,3905 |
2,01 |
3 |
8 |
7 |
1 |
7,0000 |
2,0858 |
2,68 |
4 |
16 |
12 |
3 |
4,0000 |
2,7811 |
4,03 |
5 |
32 |
23 |
5 |
4,6000 |
3,4763 |
6,44 |
6 |
64 |
46 |
13 |
3,5385 |
4,1716 |
10,74 |
7 |
128 |
95 |
19 |
5,0000 |
4,8669 |
18,41 |
8 |
256 |
189 |
33 |
5,7273 |
5,5621 |
32,22 |
9 |
512 |
375 |
62 |
6,0484 |
6,2574 |
57,28 |
10 |
1.024 |
751 |
110 |
6,8273 |
6,9527 |
103,10 |
11 |
2.048 |
1.490 |
200 |
7,4500 |
7,6480 |
187,45 |
12 |
4.096 |
2.968 |
360 |
8,2444 |
8,3432 |
343,66 |
13 |
8.192 |
5.923 |
683 |
8,6720 |
9,0385 |
634,44 |
14 |
16.384 |
11.799 |
1.259 |
9,3717 |
9,7338 |
1.178,25 |
15 |
32.768 |
23.581 |
2.307 |
10,2215 |
10,4290 |
2.199,40 |
16 |
65.536 |
47.003 |
4.379 |
10,7337 |
11,1243 |
4.123,87 |
17 |
131.072 |
93.873 |
8.181 |
11,4745 |
11,8196 |
7.762,58 |
18 |
262.144 |
187.285 |
15.460 |
12,1142 |
12,5148 |
14.662,66 |
19 |
524.288 |
373.890 |
29.182 |
12,8124 |
13,2101 |
27.781,88 |
20 |
1.048.576 |
746.565 |
55.355 |
13,4869 |
13,9054 |
52.785,58 |
21 |
2.097.152 |
1.491.178 |
105.075 |
14,1916 |
14,6006 |
100.543,96 |
22 |
4.194.304 |
2.978.399 |
200.024 |
14,8902 |
15,2959 |
191.947,56 |
23 |
8.388.608 |
5.949.603 |
382.213 |
15,5662 |
15,9912 |
367.204,02 |
24 |
16.777.216 |
11.887.260 |
731.138 |
16,2586 |
16,6864 |
703.807,70 |
25 |
33.554.432 |
23.751.260 |
1.400.025 |
16,9649 |
17,3817 |
1.351.310,79 |
26 |
67.108.864 |
47.460.078 |
2.687.701 |
17,6582 |
18,0770 |
2.598.674,60 |
27 |
134.217.728 |
94.842.057 |
5.169.672 |
18,3459 |
18,7723 |
5.004.854,78 |
28 |
268.435.456 |
189.538.866 |
9.953.947 |
19,0416 |
19,4675 |
9.652.219,94 |
29 |
536.870.912 |
378.811.001 |
19.195.216 |
19,7347 |
20,1628 |
18.638.769,53 |
30 |
1.073.741.824 |
757.129.245 |
37.055.503 |
20,4323 |
20,8581 |
36.034.954,43 |
31 |
2.147.483.648 |
1.513.336.004 |
71.632.098 |
21,1265 |
21,5533 |
69.745.073,09 |
32 |
4.294.967.296 |
3.024.943.674 |
138.636.539 |
21,8192 |
22,2486 |
135.131.079,12 |
33 |
8.589.934.592 |
6.046.677.752 |
268.581.346 |
22,5134 |
22,9439 |
262.072.395,86 |
34 |
17.179.869.184 |
12.087.378.076 |
520.826.208 |
23,2081 |
23,6391 |
508.728.768,44 |
35 |
34.359.738.368 |
24.163.506.862 |
1.010.931.350 |
23,9022 |
24,3344 |
988.387.321,54 |
36 |
68.719.476.736 |
48.305.814.739 |
1.963.966.088 |
24,5961 |
25,0297 |
1.921.864.236,32 |
37 |
137.438.953.472 |
96.571.785.730 |
3.818.600.877 |
25,2898 |
25,7249 |
3.739.843.919,33 |
38 |
274.877.906.944 |
193.068.599.918 |
7.430.393.681 |
25,9836 |
26,4202 |
7.282.853.948,16 |
39 |
549.755.813.888 |
385.995.468.449 |
14.469.007.081 |
26,6774 |
27,1155 |
14.192.228.206,68 |
4. f) Table of the requirement of memory
A |
B |
|
|
|
|
|
|
|
|
Blocknr. for x=134217728 |
blocks n=2048 |
|
|
|
|
|
|
|
|
100 |
174.702 |
|
|
|
|
|
|
|
|
200 |
363.103 |
|
|
|
|
|
|
|
|
300 |
547.748 |
|
|
|
|
|
|
|
|
400 |
729.926 |
|
|
|
|
|
|
|
|
500 |
910.278 |
|
|
|
|
|
|
|
|
600 |
1.089.205 |
|
|
|
|
|
|
|
|
700 |
1.266.985 |
|
|
|
|
|
|
|
|
800 |
1.443.776 |
|
|
|
|
|
|
|
|
900 |
1.619.690 |
|
|
|
|
|
|
|
|
1.000 |
1.794.867 |
|
|
|
|
|
|
|
|
1.100 |
1.969.393 |
|
|
|
|
|
|
|
|
1.200 |
2.143.264 |
|
|
|
|
|
|
|
|
1.300 |
2.316.630 |
|
|
|
|
|
|
|
|
1.400 |
2.489.429 |
|
|
|
|
|
|
|
|
1.500 |
2.661.815 |
|
1.600 |
2.833.726 |
1.700 |
3.005.246 |
1.800 |
3.176.390 |
1.900 |
3.347.203 |
2.000 |
3.517.658 |
2.100 |
3.687.748 |
2.200 |
3.857.559 |
2.300 |
4.027.111 |
2.400 |
4.196.347 |
2.500 |
4.365.334 |
2.600 |
4.534.082 |
2.700 |
4.702.632 |
2.800 |
4.869.427 |
2.900 |
5.030.002 |
3.000 |
5.184.215 |
3.100 |
5.332.474 |
3.200 |
5.474.899 |
3.300 |
5.611.803 |
3.400 |
5.743.377 |
3.500 |
5.869.832 |
3.600 |
5.991.378 |
3.700 |
6.108.162 |
|
|
|
|
|
|
|
|
3.800 |
6.220.363 |
|
|
|
|
|
|
|
|
3.900 |
6.328.228 |
|
|
|
|
|
|
|
|
4.000 |
6.431.780 |
|
|
|
|
|
|
|
|
4.100 |
6.531.244 |
|
|
|
|
|
|
|
|
4.200 |
6.624.644 |
|
|
|
|
|
|
|
|
4.300 |
6.710.364 |
|
|
|
|
|
|
|
|
4.400 |
6.788.705 |
|
|
|
|
|
|
|
|
4.500 |
6.859.849 |
|
|
|
|
|
|
|
|
4.600 |
6.924.086 |
|
|
|
|
|
|
|
|
4.700 |
6.981.522 |
|
|
|
|
|
|
|
|
4.800 |
7.032.458 |
|
|
|
|
|
|
|
|
4.900 |
7.077.035 |
|
|
|
|
|
|
|
|
5.000 |
7.114.378 |
|
|
|
|
|
|
|
|
5.100 |
7.142.695 |
|
|
|
|
|
|
|
|
5.200 |
7.162.279 |
|
|
|
|
|
|
|
|
5.300 |
7.173.297 |
|
|
|
|
|
|
|
|
5.400 |
7.176.053 |
|
|
|
|
|
|
|
|
5.500 |
7.170.458 |
|
|
|
|
|
|
|
|
5.600 |
7.154.874 |
|
|
|
|
|
|
|
|
5.700 |
7.129.049 |
|
|
|
|
|
|
|
|
5.800 |
7.093.188 |
|
|
|
|
|
|
|
|
5.900 |
7.047.355 |
|
|
|
|
|
|
|
|
6.000 |
6.989.828 |
|
|
|
|
|
|
|
|
6.100 |
6.920.681 |
|
|
|
|
|
|
|
|
6.200 |
6.839.761 |
|
|
|
|
|
|
|
|
6.300 |
6.745.678 |
|
|
|
|
|
|
|
|
6.400 |
6.638.409 |
|
|
|
|
|
|
|
|
6.500 |
6.516.801 |
|
|
|
|
|
|
|
|
6.600 |
6.380.351 |
|
|
|
|
|
|
|
|
6.700 |
6.227.809 |
|
|
|
|
|
|
|
|
6.800 |
6.058.242 |
|
|
|
|
|
|
|
|
6.900 |
5.870.447 |
|
|
|
|
|
|
|
|
7.000 |
5.662.956 |
|
|
|
|
|
|
|
|
7.100 |
5.434.149 |
|
|
|
|
|
|
|
|
7.200 |
5.182.033 |
|
|
|
|
|
|
|
|
7.300 |
4.904.241 |
|
|
|
|
|
|
|
|
7.400 |
4.597.856 |
|
|
|
|
|
|
|
|
7.500 |
4.259.203 |
|
|
|
|
|
|
|
|
7.600 |
3.883.490 |
|
|
|
|
|
|
|
|
7.700 |
3.464.323 |
|
|
|
|
|
|
|
|
7.800 |
2.992.475 |
|
|
|
|
|
|
|
|
7.900 |
2.453.900 |
|
|
|
|
|
|
|
|
8.000 |
1.824.067 |
|
|
|
|
|
|
|
|
8.100 |
1.049.101 |
|
|
|
|
|
|
|
|
|
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 |
1 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
2 | 4 | 3 | 2 | 0 | 0 | 0 | 2 | 1 |
3 | 8 | 6 | 5 | 0 | 1 | 1 | 2 | 2 |
4 | 16 | 9 | 8 | 0 | 2 | 2 | 3 | 2 |
5 | 32 | 14 | 13 | 0 | 3 | 3 | 5 | 3 |
6 | 64 | 22 | 21 | 0 | 3 | 9 | 6 | 4 |
7 | 128 | 38 | 37 | 0 | 7 | 13 | 8 | 10 |
8 | 256 | 66 | 65 | 0 | 14 | 19 | 15 | 18 |
9 | 512 | 108 | 107 | 0 | 29 | 26 | 22 | 31 |
10 | 1.024 | 196 | 195 | 0 | 53 | 52 | 44 | 47 |
11 | 2.048 | 352 | 351 | 0 | 88 | 90 | 86 | 88 |
12 | 4.096 | 654 | 653 | 0 | 156 | 169 | 161 | 168 |
13 | 8.192 | 1.174 | 1.173 | 0 | 290 | 293 | 291 | 300 |
14 | 16.384 | 2.167 | 2.166 | 0 | 543 | 538 | 546 | 540 |
15 | 32.768 | 3.951 | 3.950 | 0 | 984 | 992 | 991 | 984 |
16 | 65.536 | 7.364 | 7.363 | 0 | 1.811 | 1.835 | 1.892 | 1.826 |
17 | 131.072 | 13.780 | 13.779 | 0 | 3.424 | 3.427 | 3.529 | 3.400 |
18 | 262.144 | 25.776 | 25.775 | 0 | 6.414 | 6.455 | 6.570 | 6.337 |
19 | 524.288 | 48.561 | 48.560 | 0 | 12.133 | 12.117 | 12.219 | 12.092 |
20 | 1.048.576 | 91.980 | 91.979 | 0 | 23.079 | 23.015 | 23.070 | 22.816 |
21 | 2.097.152 | 174.691 | 174.690 | 0 | 43.732 | 43.685 | 43.739 | 43.535 |
22 | 4.194.304 | 331.924 | 331.923 | 0 | 83.281 | 82.940 | 83.012 | 82.691 |
23 | 8.388.608 | 632.763 | 632.762 | 0 | 158.270 | 158.013 | 158.492 | 157.988 |
24 | 16.777.216 | 1.208.189 | 1.208.188 | 0 | 302.228 | 302.062 | 301.836 | 302.063 |
25 | 33.554.432 | 2.314.216 | 2.314.215 | 0 | 578.660 | 578.458 | 578.761 | 578.337 |
26 | 67.108.864 | 4.435.345 | 4.435.344 | 0 | 1.109.274 | 1.108.268 | 1.108.916 | 1.108.887 |
27 | 134.217.728 | 8.521.876 | 8.521.875 | 0 | 2.131.308 | 2.130.666 | 2.130.425 | 2.129.477 |
28 | 268.435.456 | 16.398.035 | 16.398.034 | 0 | 4.099.448 | 4.099.934 | 4.099.185 | 4.099.468 |
29 | 536.870.912 | 31.594.046 | 31.594.045 | 0 | 7.899.540 | 7.899.885 | 7.896.631 | 7.897.990 |
30 | 1.073.741.824 | 60.971.160 | 60.971.159 | 0 | 15.245.091 | 15.244.367 | 15.240.651 | 15.241.051 |
31 | 2.147.483.648 | 117.790.467 | 117.790.466 | 0 | 29.450.169 | 29.451.268 | 29.445.396 | 29.443.634 |
32 | 4.294.967.296 | 227.834.670 | 227.834.669 | 0 | 56.961.774 | 56.958.740 | 56.960.126 | 56.954.030 |
33 | 8.589.934.592 | 441.146.458 | 441.146.457 | 0 | 110.284.505 | 110.284.988 | 110.289.462 | 110.287.503 |
34 | 17.179.869.184 | 855.066.147 | 855.066.146 | 0 | 213.764.051 | 213.759.439 | 213.786.590 | 213.756.067 |
35 | 34.359.738.368 | 1.658.944.363 | 1.658.944.362 | 0 | 414.731.675 | 414.730.777 | 414.752.646 | 414.729.265 |
36 | 68.719.476.736 | 3.221.420.562 | 3.221.420.561 | 0 | 805.352.637 | 805.356.082 | 805.371.847 | 805.339.996 |
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 |
1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 3 | 3 | 0 | 0 | 1 | 2 | 0 |
5 | 32 | 9 | 9 | 0 | 0 | 3 | 2 | 4 |
6 | 64 | 24 | 24 | 0 | 2 | 9 | 5 | 8 |
7 | 128 | 57 | 57 | 0 | 10 | 14 | 15 | 18 |
8 | 256 | 123 | 123 | 0 | 26 | 33 | 31 | 33 |
9 | 512 | 267 | 267 | 0 | 62 | 73 | 67 | 65 |
10 | 1.024 | 555 | 555 | 0 | 129 | 149 | 141 | 136 |
11 | 2.048 | 1.138 | 1.138 | 0 | 285 | 292 | 284 | 277 |
12 | 4.096 | 2.314 | 2.314 | 0 | 588 | 588 | 579 | 559 |
13 | 8.192 | 4.749 | 4.749 | 0 | 1.204 | 1.183 | 1.177 | 1.185 |
14 | 16.384 | 9.632 | 9.632 | 0 | 2.412 | 2.399 | 2.420 | 2.401 |
15 | 32.768 | 19.630 | 19.630 | 0 | 4.897 | 4.867 | 4.978 | 4.888 |
16 | 65.536 | 39.639 | 39.639 | 0 | 9.854 | 9.869 | 9.979 | 9.937 |
17 | 131.072 | 80.093 | 80.093 | 0 | 19.871 | 20.148 | 20.153 | 19.921 |
18 | 262.144 | 161.509 | 161.509 | 0 | 40.183 | 40.410 | 40.584 | 40.332 |
19 | 524.288 | 325.329 | 325.329 | 0 | 81.177 | 81.392 | 81.445 | 81.315 |
20 | 1.048.576 | 654.585 | 654.585 | 0 | 163.363 | 163.917 | 163.622 | 163.683 |
21 | 2.097.152 | 1.316.487 | 1.316.487 | 0 | 328.674 | 328.987 | 329.693 | 329.133 |
22 | 4.194.304 | 2.646.475 | 2.646.475 | 0 | 660.782 | 661.811 | 662.377 | 661.505 |
23 | 8.388.608 | 5.316.840 | 5.316.840 | 0 | 1.328.911 | 1.328.650 | 1.329.738 | 1.329.541 |
24 | 16.777.216 | 10.679.071 | 10.679.071 | 0 | 2.669.628 | 2.670.448 | 2.669.709 | 2.669.286 |
25 | 33.554.432 | 21.437.044 | 21.437.044 | 0 | 5.359.157 | 5.357.746 | 5.361.799 | 5.358.342 |
26 | 67.108.864 | 43.024.733 | 43.024.733 | 0 | 10.755.368 | 10.755.174 | 10.759.787 | 10.754.404 |
27 | 134.217.728 | 86.320.181 | 86.320.181 | 0 | 21.582.656 | 21.577.661 | 21.584.991 | 21.574.873 |
28 | 268.435.456 | 173.140.831 | 173.140.831 | 0 | 43.289.090 | 43.286.790 | 43.285.327 | 43.279.624 |
29 | 536.870.912 | 347.216.955 | 347.216.955 | 0 | 86.804.729 | 86.805.171 | 86.802.964 | 86.804.091 |
30 | 1.073.741.824 | 696.158.085 | 696.158.085 | 0 | 174.025.124 | 174.039.842 | 174.049.099 | 174.044.020 |
31 | 2.147.483.648 | 1.395.545.537 | 1.395.545.537 | 0 | 348.885.816 | 348.876.371 | 348.894.192 | 348.889.158 |
32 | 4.294.967.296 | 2.797.109.004 | 2.797.109.004 | 0 | 699.286.063 | 699.281.097 | 699.287.059 | 699.254.785 |
33 | 8.589.934.592 | 5.605.531.294 | 5.605.531.294 | 0 | 1.401.399.518 | 1.401.355.718 | 1.401.423.021 | 1.401.353.037 |
34 | 17.179.869.184 | 11.232.311.926 | 11.232.311.926 | 0 | 2.808.081.789 | 2.808.053.850 | 2.808.124.668 | 2.808.051.619 |
35 | 34.359.738.368 | 22.504.562.490 | 22.504.562.490 | 0 | 5.626.076.664 | 5.626.143.186 | 5.626.182.086 | 5.626.160.554 |
36 | 68.719.476.736 | 45.084.394.137 | 45.084.394.137 | 0 | 11.271.000.299 | 11.271.101.731 | 11.271.140.413 | 11.271.151.694 |
5. a) Table of the amount of divisions
A |
B |
C |
D |
E |
F |
2^n |
x |
amount of division |
B*ln(ln (B)) |
max divisions |
C / B |
|
|
|
|
|
|
1 |
2 |
1 |
|
1 |
0,50 € |
2 |
4 |
3 |
1 |
2 |
0,75 € |
3 |
8 |
4 |
6 |
2 |
0,50 € |
4 |
16 |
12 |
17 |
3 |
0,75 € |
5 |
32 |
31 |
40 |
3 |
0,97 € |
6 |
64 |
65 |
92 |
3 |
1,02 € |
7 |
128 |
143 |
204 |
4 |
1,12 € |
8 |
256 |
321 |
443 |
4 |
1,25 € |
9 |
512 |
711 |
947 |
5 |
1,39 € |
10 |
1.024 |
1.518 |
2.003 |
5 |
1,48 € |
11 |
2.048 |
3.262 |
4.202 |
6 |
1,59 € |
12 |
4.096 |
6.917 |
8.764 |
7 |
1,69 € |
13 |
8.192 |
14.531 |
18.188 |
7 |
1,77 € |
14 |
16.384 |
30.408 |
37.598 |
7 |
1,86 € |
15 |
32.768 |
63.301 |
77.472 |
8 |
1,93 € |
16 |
65.536 |
131.204 |
159.203 |
8 |
2,00 € |
17 |
131.072 |
271.125 |
326.406 |
9 |
2,07 € |
18 |
262.144 |
558.715 |
667.897 |
9 |
2,13 € |
19 |
524.288 |
1.148.251 |
1.364.333 |
10 |
2,19 € |
20 |
1.048.576 |
2.354.731 |
2.782.815 |
10 |
2,25 € |
21 |
2.097.152 |
4.819.940 |
5.668.646 |
10 |
2,30 € |
22 |
4.194.304 |
9.849.830 |
11.533.737 |
12 |
2,35 € |
23 |
8.388.608 |
20.099.905 |
23.442.897 |
12 |
2,40 € |
24 |
16.777.216 |
40.963.476 |
47.604.676 |
12 |
2,44 € |
25 |
33.554.432 |
83.387.703 |
96.588.418 |
12 |
2,49 € |
26 |
67.108.864 |
169.576.866 |
195.826.776 |
12 |
2,53 € |
27 |
134.217.728 |
344.529.635 |
396.753.388 |
13 |
2,57 € |
28 |
268.435.456 |
699.397.242 |
803.335.467 |
14 |
2,61 € |
29 |
536.870.912 |
1.418.700.083 |
1.625.638.441 |
14 |
2,64 € |
30 |
1.073.741.824 |
2.875.782.055 |
3.287.925.710 |
14 |
2,68 € |
31 |
2.147.483.648 |
5.825.675.142 |
6.646.745.437 |
15 |
2,71 € |
32 |
4.294.967.296 |
11.794.617.237 |
13.430.776.933 |
15 |
2,75 € |
33 |
8.589.934.592 |
23.866.513.465 |
27.127.676.255 |
15 |
2,78 € |
34 |
17.179.869.184 |
48.270.164.941 |
54.771.706.989 |
16 |
2,81 € |
35 |
34.359.738.368 |
97.581.984.305 |
110.546.185.088 |
17 |
2,84 € |
36 |
68.719.476.736 |
197.185.823.454 |
223.041.410.668 |
17 |
2,87 € |
37 |
137.438.953.472 |
398.299.608.337 |
449.874.092.030 |
17 |
2,90 € |
38 |
274.877.906.944 |
804.236.377.051 |
907.128.500.048 |
18 |
2,93 € |
39 |
549.755.813.888 |
1.623.333.569.045 |
1.828.634.195.341 |
18 |
2,95 € |
|
5. b) 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. d) Sequence of all primes with p | n2+n+1 and p=1 by arising n
1, 3, 7, 13, 1, 31, 43, 19, 73, 1, 37, 1, 157, 61, 211, 241, 1, 307, 1, 127, 421, 463, 1, 79, 601, 1, 1, 757, 271, 67, 1, 331, 151, 1123, 397, 97, 1, 1, 1483, 223, 547, 1723, 139, 631, 283, 109, 103, 1, 181, 1, 2551, 379, 919, 409, 2971, 1, 1, 3307, 163, 3541, 523, 1, 3907, 1, 1, 613, 4423, 1, 1, 4831, 1657, 5113, 751, 1801, 1, 5701, 1951, 6007, 6163, 1, 6481, 1, 2269, 367, 193, 2437, 1069, 1, 373, 8011, 8191, 2791, 199, 1249, 229, 1303, 1, 3169, 313, 9901, 1, 10303, 1, 3571, 1, 11131, 1, 1, 1, 571, 12211, 12433, 4219, 991, 1873, 4447, 277, 13807, 1, 14281, 1117, 1, 349, 2179, 5167, 829, 1231, 5419, 337, 541, 811, 17293, 1, 457, 1, 1, 6211, 1, 19183, 499, 1039, 20023, 967, 20593, 1, 7057, 1, 21757, 7351, 1, 22651, 1093, 1789, 23563, 1, 24181, 3499, 8269, 1, 1, 1, 26083, 26407, 1, 27061, 1, 9241, 28057, 28393, 1, 4153, 439, 1, 30103, 823, 10267, 31153, 643, 1, 4603, 1051, 1, 1753, 1, 1621, 2647, 4969, 11719, 35533, 35911, 12097, 1, 37057, 1783, 37831, 1033, 1, 2053, 433, 13267, 5743, 2137, 13669, 41413, 3217, 2011, 42643, 6151, 1, 43891, 607, 1, 6451, 577, 1, 46441, 2467, 1213, 47743, 6883, 853, 1, 1597, 16651, 3877, 1, 1, 709, 7459, 1, 1, 53593, 487, 7789, 1, 1, 55933, 4339, 1, 3019, 8263, 19441, 1, 4561, 19927, 60271, 60763, 2917, 1669, 8893, 1609, 1471, 619, 691, 1, 673, 1, 1087, 3517, 22447, 859, 9769, 1, 1, 1627, 23497, 71023, 1, 3433, 1, 10453, 24571, 74257, 1, 25117, 1549, 5881, 1, 77563, 78121, 26227, 727, 877, 1, 1, 2203, 27361, 82657, 83233, 1, 84391, 1, 1, 86143, 2017, 2239, 661, 1321, 4243, 1, 1237, 1, 7039, 13159, 997, 1, 2539, 733, 7321, 95791, 4591, 5107, 1993, 1, 98911, 1, 33391, 14401, 1663, 4861, 739, 7951, 937, 1, 1, 35317, 1, 1, 2767, 108571, 5749, 5233, 110557, 15889, 1, 3631, 113233, 883, 16369, 1459, 5521, 8971, 117307, 1063, 118681, 17053, 1291, 1327, 121453, 2143, 2857, 123553, 1, 6577, 1381, 1, 1741, 127807, 42841, 1, 769, 1, 1, 1, 1, 1297, 1, 3463, 1021, 136531, 45757, 1747, 1, 1, 1009, 20143, 47251, 4597, 143263, 787, 1, 145543, 6967, 147073, 907, 49537, 11491, 1129, 50311, 21673, 1399, 2689, 154057, 1, 7411, 156421, 1, 1699, 158803, 12277, 1, 23029, 162007, 7753, 163621, 164431, 1, 1, 1, 55897, 1, 1, 4363, 2803, 171811, 8221, 173473, 1, 1, 13537, 1171, 59221, 3643, 1, 8581, 1, 181903, 60919, 5923, 1, 1, 1, 14389, 1693, 188791, 189661, 1, 1, 2113, 1, 3181, 1, 65269, 28099, 10399, 1, 2731, 200257, 3529, 2083, 1, 5227, 29251, 205663, 1861, 207481, 208393, 9967, 1, 1, 70687, 1, 1, 3769, 2371, 1, 1, 11503, 2131, 73477, 1, 1, 74419, 32029, 3691, 75367, 227053, 17539, 10903, 5347, 32983, 1, 12253, 1489, 1, 1, 12457, 11317, 1879, 239611, 1, 6529, 34651, 81181, 1, 245521, 82171, 1, 3709, 1, 250501, 1, 1153, 19501, 1279, 4483, 1, 6961, 1759, 6037, 20047, 87211, 262657, 1, 88237, 37963, 20521, 89269, 268843, 3697, 1, 1, 1, 7027, 14479, 276151, 92401, 1, 7549, 1, 281431, 282493, 3049, 284623, 40813, 1567, 3163, 288907, 96661, 15319, 292141, 13963, 22639, 2221, 2671, 1, 3079, 1, 42979, 23227, 14431, 304153, 1, 102121, 307471, 3391, 103231, 6343, 16417, 104347, 314161, 3061, 1, 10243, 45523, 1, 320923, 322057, 8287, 6619, 1201, 1, 327757, 4909, 110017, 1, 1, 5851, 47809, 335821, 112327, 1, 339307, 1, 341641, 48973, 114661, 1, 26641, 115837, 1, 1933, 1, 2161, 1, 2749, 1, 51001, 1, 51343, 18979, 9277, 9811, 364213, 17401, 366631, 7507, 9463, 1, 371491, 1, 53419, 375157, 17923, 1, 1, 126691, 3931, 1, 6733, 4231, 386263, 129169, 6373, 390001, 1, 392503, 4327, 131671, 1777, 1, 1, 1, 30871, 1, 403861, 2683, 135469, 1, 1579, 1, 58789, 412807, 1423, 415381, 13441, 1531, 1987, 1, 140617, 1, 9871, 1, 1, 3373, 1, 13903, 1, 144541, 33457, 62323, 145861, 62701, 2281, 1429, 6067, 34171, 1, 446893, 64033, 1, 450913, 1831, 151201, 1, 2521, 1, 459007, 1, 11839, 1, 1543, 155269, 66739, 7681, 12049, 471283, 1, 22573, 2389, 68113, 8389, 1, 1453, 3739, 3637, 485113, 23167, 2887, 1, 163567, 492103, 70501, 1, 1447, 38287, 1, 1, 2251, 23971, 1, 5563, 169219, 13759, 1, 170647, 10477, 4723, 1, 1, 519121, 2377, 3457, 74779, 1, 75193, 527803, 176419, 530713, 1, 25411, 41161, 76651, 9439, 6829, 540961, 180811, 1, 1, 26041, 5653, 1, 1, 552793, 6091, 3037, 79609, 558757, 9829, 18121, 1, 26893, 29803, 11587, 189757, 570781, 3511, 14713, 82189, 1, 27541, 579883, 581407, 14947, 1, 11959, 1, 1, 590593, 6367, 45667, 31327, 1, 598303, 1, 200467, 46381, 5869, 202021, 1, 1, 1, 612307, 47221, 1, 617011, 4651, 1, 88819, 47947, 1, 4507, 628057, 29983, 8647, 90403, 16267, 4051, 637603, 213067, 2953, 642403, 1, 17449, 2287, 11383, 10663, 93151, 1999, 1, 15277, 1, 660157, 8377, 4513, 51157, 95239, 1, 669943, 671581, 1, 1, 4003, 1, 1, 681451, 2089, 684757, 1, 1, 98533, 22303, 231019, 10369, 1867, 2557, 699733, 1, 234361, 704761, 1, 1, 3271, 37447, 33961, 9049, 716563, 12601, 55381, 103093, 241117, 14797, 3259, 5647, 56167, 731881, 1, 735307, 1, 246247, 740461, 1, 1, 15217, 747361, 35671, 1, 1, 251431, 5953, 1, 1, 108751, 1, 19609, 766501, 5527, 1, 771763, 110503, 1, 40897, 2311, 260191, 1, 41269, 37423, 60589, 3967, 263737, 792991, 113539, 3361, 1, 800131, 267307, 18691, 805507, 1, 809101, 1, 4441, 4093, 2659, 1, 117133, 63211, 39217, 1, 19237, 276337, 830833, 16993, 21397, 3229, 838141, 279991, 7723, 843643, 1, 847321, 121309, 283669, 44887, 1, 285517, 9433, 860257, 1, 5503, 6229, 1, 66889, 124489, 3001, 1, 1, 292969, 1, 1, 1, 1, 6679, 296731, 1, 68767, 298621, 1, 3733, 6133, 903451, 24469, 1, 5023, 1, 9817, 130699, 1, 23557, 920641, 922561, 1, 15187, 132619, 310087, 71707, 30133, 4657, 133999, 939931, 44851, 1, 25561, 3067, 949651, 2029, 16729, 136501, 73651, 1, 50599, 963343, 1, 9391, 10651, 1, 31393, 975157, 8803, 2293, 981091, 1, 985057, 987043, 329677, 1, 1, 1, 20347, 52579,
6. e) Sequence of all primes p | n2+n+1 by arising n
3, 7, 13, 31, 43, 19, 73, 37, 157, 61, 211, 241, 307, 127, 421, 463, 79, 601, 757, 271, 67, 331, 151, 1123, 397, 97, 1483, 223, 547, 1723, 139, 631, 283, 109, 103, 181, 2551, 379, 919, 409, 2971, 3307, 163, 3541, 523, 3907, 613, 4423, 4831, 1657, 5113, 751, 1801, 5701, 1951, 6007, 6163, 6481, 2269, 367, 193, 2437, 1069, 373, 8011, 8191, 2791, 199, 1249, 229, 1303, 3169, 313, 9901, 10303, 3571, 11131, 571, 12211, 12433, 4219, 991, 1873, 4447, 277, 13807, 14281, 1117, 349, 2179, 5167, 829, 1231, 5419, 337, 541, 811, 17293, 457, 6211, 19183, 499, 1039, 20023, 967, 20593, 7057, 21757, 7351, 22651, 1093, 1789, 23563, 24181, 3499, 8269, 26083, 26407, 27061, 9241, 28057, 28393, 4153, 439, 30103, 823, 10267, 31153, 643, 4603, 1051, 1753, 1621, 2647, 4969, 11719, 35533, 35911, 12097, 37057, 1783, 37831, 1033, 2053, 433, 13267, 5743, 2137, 13669, 41413, 3217, 2011, 42643, 6151, 43891, 607, 6451, 577, 46441, 2467, 1213, 47743, 6883, 853, 1597, 16651, 3877, 709, 7459, 53593, 487, 7789, 55933, 4339, 3019, 8263, 19441, 4561, 19927, 60271, 60763, 2917, 1669, 8893, 1609, 1471, 619, 691, 673, 1087, 3517, 22447, 859, 9769, 1627, 23497, 71023, 3433, 10453, 24571, 74257, 25117, 1549, 5881, 77563, 78121, 26227, 727, 877, 2203, 27361, 82657, 83233, 84391, 86143, 2017, 2239, 661, 1321, 4243, 1237, 7039, 13159, 997, 2539, 733, 7321, 95791, 4591, 5107, 1993, 98911, 33391, 14401, 1663, 4861, 739, 7951, 937, 35317, 2767, 108571, 5749, 5233, 110557, 15889, 3631, 113233, 883, 16369, 1459, 5521, 8971, 117307, 1063, 118681, 17053, 1291, 1327, 121453, 2143, 2857, 123553, 6577, 1381, 1741, 127807, 42841, 769, 1297, 3463, 1021, 136531, 45757, 1747, 1009, 20143, 47251, 4597, 143263, 787, 145543, 6967, 147073, 907, 49537, 11491, 1129, 50311, 21673, 1399, 2689, 154057, 7411, 156421, 1699, 158803, 12277, 23029, 162007, 7753, 163621, 164431, 55897, 4363, 2803, 171811, 8221, 173473, 13537, 1171, 59221, 3643, 8581, 181903, 60919, 5923, 14389, 1693, 188791, 189661, 2113, 3181, 65269, 28099, 10399, 2731, 200257, 3529, 2083, 5227, 29251, 205663, 1861, 207481, 208393, 9967, 70687, 3769, 2371, 11503, 2131, 73477, 74419, 32029, 3691, 75367, 227053, 17539, 10903, 5347, 32983, 12253, 1489, 12457, 11317, 1879, 239611, 6529, 34651, 81181, 245521, 82171, 3709, 250501, 1153, 19501, 1279, 4483, 6961, 1759, 6037, 20047, 87211, 262657, 88237, 37963, 20521, 89269, 268843, 3697, 7027, 14479, 276151, 92401, 7549, 281431, 282493, 3049, 284623, 40813, 1567, 3163, 288907, 96661, 15319, 292141, 13963, 22639, 2221, 2671, 3079, 42979, 23227, 14431, 304153, 102121, 307471, 3391, 103231, 6343, 16417, 104347, 314161, 3061, 10243, 45523, 320923, 322057, 8287, 6619, 1201, 327757, 4909, 110017, 5851, 47809, 335821, 112327, 339307, 341641, 48973, 114661, 26641, 115837, 1933, 2161, 2749, 51001, 51343, 18979, 9277, 9811, 364213, 17401, 366631, 7507, 9463, 371491, 53419, 375157, 17923, 126691, 3931, 6733, 4231, 386263, 129169, 6373, 390001, 392503, 4327, 131671, 1777, 30871, 403861, 2683, 135469, 1579, 58789, 412807, 1423, 415381, 13441, 1531, 1987, 140617, 9871, 3373, 13903, 144541, 33457, 62323, 145861, 62701, 2281, 1429, 6067, 34171, 446893, 64033, 450913, 1831, 151201, 2521, 459007, 11839, 1543, 155269, 66739, 7681, 12049, 471283, 22573, 2389, 68113, 8389, 1453, 3739, 3637, 485113, 23167, 2887, 163567, 492103, 70501, 1447, 38287, 2251, 23971, 5563, 169219, 13759, 170647, 10477, 4723, 519121, 2377, 3457, 74779, 75193, 527803, 176419, 530713, 25411, 41161, 76651, 9439, 6829, 540961, 180811, 26041, 5653, 552793, 6091, 3037, 79609, 558757, 9829, 18121, 26893, 29803, 11587, 189757, 570781, 3511, 14713, 82189, 27541, 579883, 581407, 14947, 11959, 590593, 6367, 45667, 31327, 598303, 200467, 46381, 5869, 202021, 612307, 47221, 617011, 4651, 88819, 47947, 4507, 628057, 29983, 8647, 90403, 16267, 4051, 637603, 213067, 2953, 642403, 17449, 2287, 11383, 10663, 93151, 1999, 15277, 660157, 8377, 4513, 51157, 95239, 669943, 671581, 4003, 681451, 2089, 684757, 98533, 22303, 231019, 10369, 1867, 2557, 699733, 234361, 704761, 3271, 37447, 33961, 9049, 716563, 12601, 55381, 103093, 241117, 14797, 3259, 5647, 56167, 731881, 735307, 246247, 740461, 15217, 747361, 35671, 251431, 5953, 108751, 19609, 766501, 5527, 771763, 110503, 40897, 2311, 260191, 41269, 37423, 60589, 3967, 263737, 792991, 113539, 3361, 800131, 267307, 18691, 805507, 809101, 4441, 4093, 2659, 117133, 63211, 39217, 19237, 276337, 830833, 16993, 21397, 3229, 838141, 279991, 7723, 843643, 847321, 121309, 283669, 44887, 285517, 9433, 860257, 5503, 6229, 66889, 124489, 3001, 292969, 6679, 296731, 68767, 298621, 3733, 6133, 903451, 24469, 5023, 9817, 130699, 23557, 920641, 922561, 15187, 132619, 310087, 71707, 30133, 4657, 133999, 939931, 44851, 25561, 3067, 949651, 2029, 16729, 136501, 73651, 50599, 963343, 9391, 10651, 31393, 975157, 8803, 2293, 981091, 985057, 987043, 329677, 20347, 52579,
|
|