Inhaltsverzeichnis

Development of
Algorithmic Constructions
04:11:31
Deutsch
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


ABCDEFGHI
exponent =log2 (x) <=xnumber 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
121100001
243200021
386501122
4169802232
532141303353
664222103964
712838370713810
82566665014191518
9512108107029262231
101.024196195053524447
112.048352351088908688
124.0966546530156169161168
138.1921.1741.1730290293291300
1416.3842.1672.1660543538546540
1532.7683.9513.9500984992991984
1665.5367.3647.36301.8111.8351.8921.826
17131.07213.78013.77903.4243.4273.5293.400
18262.14425.77625.77506.4146.4556.5706.337
19524.28848.56148.560012.13312.11712.21912.092
201.048.57691.98091.979023.07923.01523.07022.816
212.097.152174.691174.690043.73243.68543.73943.535
224.194.304331.924331.923083.28182.94083.01282.691
238.388.608632.763632.7620158.270158.013158.492157.988
2416.777.2161.208.1891.208.1880302.228302.062301.836302.063
2533.554.4322.314.2162.314.2150578.660578.458578.761578.337
2667.108.8644.435.3454.435.34401.109.2741.108.2681.108.9161.108.887
27134.217.7288.521.8768.521.87502.131.3082.130.6662.130.4252.129.477
28268.435.45616.398.03516.398.03404.099.4484.099.9344.099.1854.099.468
29536.870.91231.594.04631.594.04507.899.5407.899.8857.896.6317.897.990
301.073.741.82460.971.16060.971.159015.245.09115.244.36715.240.65115.241.051
312.147.483.648117.790.467117.790.466029.450.16929.451.26829.445.39629.443.634
324.294.967.296227.834.670227.834.669056.961.77456.958.74056.960.12656.954.030
338.589.934.592441.146.458441.146.4570110.284.505110.284.988110.289.462110.287.503
3417.179.869.184855.066.147855.066.1460213.764.051213.759.439213.786.590213.756.067
3534.359.738.3681.658.944.3631.658.944.3620414.731.675414.730.777414.752.646414.729.265
3668.719.476.7363.221.420.5623.221.420.5610805.352.637805.356.082805.371.847805.339.996

ABCDEFGHI
exponent =log2 (x) <=xnumber 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
120000000
240000000
381100100
4163300120
5329900324
664242402958
71285757010141518
8256123123026333133
9512267267062736765
101.0245555550129149141136
112.0481.1381.1380285292284277
124.0962.3142.3140588588579559
138.1924.7494.74901.2041.1831.1771.185
1416.3849.6329.63202.4122.3992.4202.401
1532.76819.63019.63004.8974.8674.9784.888
1665.53639.63939.63909.8549.8699.9799.937
17131.07280.09380.093019.87120.14820.15319.921
18262.144161.509161.509040.18340.41040.58440.332
19524.288325.329325.329081.17781.39281.44581.315
201.048.576654.585654.5850163.363163.917163.622163.683
212.097.1521.316.4871.316.4870328.674328.987329.693329.133
224.194.3042.646.4752.646.4750660.782661.811662.377661.505
238.388.6085.316.8405.316.84001.328.9111.328.6501.329.7381.329.541
2416.777.21610.679.07110.679.07102.669.6282.670.4482.669.7092.669.286
2533.554.43221.437.04421.437.04405.359.1575.357.7465.361.7995.358.342
2667.108.86443.024.73343.024.733010.755.36810.755.17410.759.78710.754.404
27134.217.72886.320.18186.320.181021.582.65621.577.66121.584.99121.574.873
28268.435.456173.140.831173.140.831043.289.09043.286.79043.285.32743.279.624
29536.870.912347.216.955347.216.955086.804.72986.805.17186.802.96486.804.091
301.073.741.824696.158.085696.158.0850174.025.124174.039.842174.049.099174.044.020
312.147.483.6481.395.545.5371.395.545.5370348.885.816348.876.371348.894.192348.889.158
324.294.967.2962.797.109.0042.797.109.0040699.286.063699.281.097699.287.059699.254.785
338.589.934.5925.605.531.2945.605.531.29401.401.399.5181.401.355.7181.401.423.0211.401.353.037
3417.179.869.18411.232.311.92611.232.311.92602.808.081.7892.808.053.8502.808.124.6682.808.051.619
3534.359.738.36822.504.562.49022.504.562.49005.626.076.6645.626.143.1865.626.182.0865.626.160.554
3668.719.476.73645.084.394.13745.084.394.137011.271.000.29911.271.101.73111.271.140.41311.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,