Development ofAlgorithmic Constructions

 12:11:54 19.Sep 2021

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)
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,