Inhaltsverzeichnis

Development of
Algorithmic Constructions

12:44:13
Deutsch
19.Sep 2021


Prime sieving for the polynomial f(n)=4n2+1


0. Abstract

1. Mathematical theory

2. Description of the basic algorithm

3. Programming and algorithms
a) Programing of the basic algorithm
b) little improvement of the basic algorithm
c) Improved programming for speed, Hensel-Lifting
d) 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) 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

6. Sequences of primes and reference to Njas-Sequences
a) Primes of form 4n2 + 1
b) unsorted list of Primes and 1
c) Primitive prime factors of the sequence k2 + 1 in the order that they are found
d) Prime factors of numbers of the form x2 + 1 which themselves are not of this form
e) Primes congruent to 1 or 2 modulo 4; or, primes of form x2+y2; or, -1 is a square mod p
f) number of primes of the form x2 + 1 < 10n
g) number of distinct prime divisors (taken together) of numbers of the form x2+1 for x<=10n
h) Pythagorean primes: primes of form 4n + 1
i) Numbers n such that n2 + 1 is prime

7. Links
a) A Sieve Method for Factoring Numbers of the Form n2 + 1, by Daniel Shanks, 1959
b) On the Conjecture of Hardy and Littlewood concerning the Number of Primes of the form n2+a, by Daniel Shanks, 1960
c) On the Gaussian Primes on the Line Im(x)=1, by M. C. Wunderlich, 1973
d) On Primes Represented by Quadratic Polynomials, by Stephan Baier and Liangyi Zhao, 2007
e) Search for primes of the form n2 + 1 by Marek Wolf, 2010
f) Batemann Horn Conjecture
g) Gaußsche Zahl
h) Gaussian Integer from MathWorld
i) Gaussian Prime from MathWorld

0. Abstract:


The investigation for the distribution of the primes concerning the polynomial f(n)=4n2+1 is very closed combined with the polynomial f(m)=m2+1 because the first polynomial is the result of a substitution by m=2n for f(m).

Nevertheless the order of the primes is different and the construction of the algorithm is slightly a little bit different too. The prime 2 could be negligated and the appearance of the second position of the primes could not be used.

Calculation of the distribution of the primes was done for n up to 240 2014 on Athlon 64 600e processor on one core with 16 Gbyte Ram and 2 Terabyte of disk. The program needed nearly a month for the calculation.
Only the distribution of the primes was logged and the calculated primes were not safed.

1. Mathematical theory


Let f(x) = 4x2 + 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)   <=> 4x2 + 1 = 0                  mod p
   p | f(x+p) <=> 4(x+p)2 + 1 = 0              mod p
              <=> 4(x2 + 2xp + p2) + 1 = 0     mod p
              <=> 4x2 + 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)

   p | f(x)    <=> 4x2 + 1 = 0                 mod p
   p | f(-x)   <=> 4(-x)2 + 1 = 0              mod p
               <=> 4x2 + 1 = 0                 mod p

   Thus if p | f(x)  then p | f(-x)

c) Lemma: If p | f(-x) then also p | f(-x+p)

   This is a simple conclusion of b) and c) and means that
   if p is a divisor of f(x) then p appears periodically concerning the function values of f(x)=4x2+1
   at f(x) and f(-x) with the period length p

d) Lemma: f(x) mod 4 = {1}

   f(0)=1, f(1)=5 = 1 mod 4, f(2)=17 = 1 mod 4, f(3)=37 = 1 mod 4

e) Lemma: If p | f(x) with p is a prime then jacobi (-1, p) = 1
   because the discriminant of f(x)=4x2+1 is -1

   If p divides f(x), then p divides (4 k2 + 1) which implies
   that p is the sum of two squares which implies that p = 1 mod 4
   which implies that jacobi(-1,p) = 1.


f) Lemma: If p is a primitiv prime factor resp. if p | f(x) with the smallest x>0
          then p > x

   The divisor p of f(x) appears periodically in the sequence of f(x) with x=0 up to oo
   respectively if p | f(x) then p | f(x+p) and especially p | f(x-p).
   supposing that p<=x then p would be found earlier by the described algorithm and would be sieved out.
   Therefore if p divides f(x) then p is greater than x

g) Lemma: If p is a primitiv prime factor resp. if p | f(x) with the smallest x>0
          then p > 2x  with p>2

   f(x)=f(-x)
   if p<=2x then p has to appear as divisor in the interval [f(-x), f(x)]
   especially in the interval [f(0), f(x)] because the function terms of f(-x) are the same as f(x).
   Lemma f) shows that this is not possible.


h) Lemma: Let f*(y) the natural number which remains
          when f(y) is divided as often as possible by f*(x) with x from 0 up to y-1
          if f*(x)>1 then f*(x) is a primitiv prime factor and a Stormer prime

   Supposing f*(y) is not a prime, f*(y)=p*q  with p, q element N greater than 1
   p > 2y, q > 2y (Lemma g))

   f(y)=y2+1 > f*(y) = p*q > (2y)(2y) = 4y2 which is a contradiction.

i) Lemma: If f*(y) is the natural number which remains when f(y) is divided as often as possible
          by the second appearance of the prime f*(x) with x from 0 up to y-1
          and f*(y) > 1 then f*(y) is a prime

   This proof is missing.

j) The Hensel-lifting explains for every p|f(x) where p2|f(y) p3|f(z) ... pn|f(n) can be found.

k) Lemma: if p is a prime without the 2 and with p | f(x)=x2+1 then p | f(y)=4y2+1.

   The substitution with x=2y gives this result.
   Therefore all primes without the 2 which are divisor of the f(x)=x2+1 are a divisor of f(y)=4y2+1.
   Nevertheless the sequence of the primes found by the described algorithm is not the same and
   the Lemma i) is not true for the function f(y)=4y2+1

l) With the help of the chinese remainder it is possible to calculate a x
   where f(x) is either a prime or the product of new primes
   and f(x) is not divisible by the primes found before.

   Example:
   The first prime values for the polynom fx)=x2+1 are

   f(0)=1
   f(1)=2
   f(2)=5
   f(3)=1
   f(4)=17

   Supposing that the sequence f(5)-f(oo)=1

   p1=2
   p2=5
   p3=17

   are the first primes

   choose a special x1, x2 and x3 for the primes

   x1=2
   x2=4
   x3=5

   (Other values are also possible, f(xi) should not be divisible by pi)

   With the help of the chinese remainder theorem you could solve the equitations :

   x=0 mod 2  f(0)=1  not divisible by 2
   x=4 mod 5  f(4)=17 not divisible by 5
   x=5 mod 17 f(5)=26 not divisible by 17

   The solution is x=124 mod 170

   f(124) is not divisible by the primes 2, 5, 17
   f(124)=15377 which is by chance a primes.

   By this way you could calculate a special x taking the first primes of the sequence calculated by the algorithm
   and you get as result a special f(x) which is either a prime or consists of primes which are not yet in the sequence.

m) Lemma: if x+I is divisible by a+bI then x-I is divisible by a-bI and vice visa.

   Proof: (x+I) / (a+bI) = (x+I)(a-bI)/(a2+b2) = (ax+b+aI-bxI)/(a2+b2) = (ax+b)/(a2+b2) + (a-bx)I / (a2+b2) = c + dI     with x, a, b, c, d element of Z
          (x-I) / (a-bI) = (x-I)(a+bI)/(a2+b2) = (ax+b-aI+bxI)/(a2+b2) = (ax+b)/(a2+b2) - (a-bx)I / (a2+b2) = c - dI

   if (a+bI) / (c+dI) = e+fI then
      (a-bI) / (c-dI) = e-fI

   the proof is analogue to the sentence before.

n) Lemma: The sequence of primes with p = a2 + b2 is infinite.

   p(x)= x2+1 = (x+I)(x-I)

   Proof: Let p*(x) the prime > 2 for x > 1 which remains
   when p(x) is divided as often as possible by f*(x) with x from 0 up to x-1
   Then p*(x) could be written according Lemma q) as p*(x)=(a+bI)(a-bI) = a2+b2 with a, b element of Z

   As the sequence of reducible primes is infinite (Lemma l)
   the sequence of these primes as sum of two quadratic numbers is also infinite.


2. Description of the basic algorithm


a) Create a list from x=1 to x=list_max=100 with f(x)=4x2+1

f(1)= 5
f(2)= 17
f(3)= 37
f(4)= 65 = 5*13
f(5)= 101
f(6)= 145 = 5*29
f(7)= 197
f(8)= 257
f(9)= 325 = 52*13
f(10)= 401
f(11)= 485 = 5*97
f(12)= 577
f(13)= 677
f(14)= 785 = 5*157
f(15)= 901 = 17*53
f(16)= 1025 = 52*41
f(17)= 1157 = 13*89
f(18)= 1297
f(19)= 1445 = 5*172
f(20)= 1601
f(21)= 1765 = 5*353
f(22)= 1937 = 13*149
f(23)= 2117 = 29*73
f(24)= 2305 = 5*461
f(25)= 2501 = 41*61
f(26)= 2705 = 5*541
f(27)= 2917
f(28)= 3137
f(29)= 3365 = 5*673
f(30)= 3601 = 13*277
f(31)= 3845 = 5*769
f(32)= 4097 = 17*241
f(33)= 4357
f(34)= 4625 = 53*37
f(35)= 4901 = 132*29
f(36)= 5185 = 5*17*61
f(37)= 5477
f(38)= 5777 = 53*109
f(39)= 6085 = 5*1217
f(40)= 6401 = 37*173
f(41)= 6725 = 52*269
f(42)= 7057
f(43)= 7397 = 13*569
f(44)= 7745 = 5*1549
f(45)= 8101
f(46)= 8465 = 5*1693
f(47)= 8837
f(48)= 9217 = 13*709
f(49)= 9605 = 5*17*113
f(50)= 10001 = 73*137
f(51)= 10405 = 5*2081
f(52)= 10817 = 29*373
f(53)= 11237 = 17*661
f(54)= 11665 = 5*2333
f(55)= 12101
f(56)= 12545 = 5*13*193
f(57)= 12997 = 41*317
f(58)= 13457
f(59)= 13925 = 52*557
f(60)= 14401
f(61)= 14885 = 5*13*229
f(62)= 15377
f(63)= 15877
f(64)= 16385 = 5*29*113
f(65)= 16901
f(66)= 17425 = 52*17*41
f(67)= 17957
f(68)= 18497 = 53*349
f(69)= 19045 = 5*13*293
f(70)= 19601 = 17*1153
f(71)= 20165 = 5*37*109
f(72)= 20737 = 89*233
f(73)= 21317
f(74)= 21905 = 5*13*337
f(75)= 22501
f(76)= 23105 = 5*4621
f(77)= 23717 = 37*641
f(78)= 24337
f(79)= 24965 = 5*4993
f(80)= 25601
f(81)= 26245 = 5*29*181
f(82)= 26897 = 13*2069
f(83)= 27557 = 17*1621
f(84)= 28225 = 52*1129
f(85)= 28901
f(86)= 29585 = 5*61*97
f(87)= 30277 = 13*17*137
f(88)= 30977
f(89)= 31685 = 5*6337
f(90)= 32401
f(91)= 33125 = 54*53
f(92)= 33857
f(93)= 34597 = 29*1193
f(94)= 35345 = 5*7069
f(95)= 36101 = 13*2777
f(96)= 36865 = 5*73*101
f(97)= 37637 = 61*617
f(98)= 38417 = 41*937
f(99)= 39205 = 5*7841
f(100)= 40001 = 13*17*181

b) f(1)=5
Divide f(1+k*5) / 5 with 1+k*5<=liste_max, k element N
Dvide f(-1+k*5) / 5 as often as there is no factor 5 in the result.

c) f(2)=17
Divide f(2+k*17) / 17 as often as there is no factor 17 in the result.
Divide f(-2+k*17) / 17 as often as there is no factor 17 in the result.

d) Go for x from 3 to liste_max if f´(x) > 1
Divide f(x+k*f´(x)) / f´(x) and
Divide f(-x+k*f´(x)) / f´(x) as often as there is no factor f´(x) in the result.
f´(x) is the prime which remains after dividing by f(1), f´(2) up to f´(x-1)

You get an unsorted list of primes.

3. a) Programming of the basic algorithm


  • liste_max:=1000;

    siebung:=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
       liste [x]:=4*x2+1;
    end_for;

    for x from 1 to liste_max do
        p:=liste[x]; 
        print (x, p); 
        if (p>1) then
          siebung (x,  p);
          siebung (p-x, p);
        end_if;
    end_for;

3. b) little improvement of the basic algorithm


  • liste_max:=1000;
    anz:=0;

    siebung:=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
       liste [x]:=4*x2+1;
    end_for;

    for x from 1 to liste_max/3 do
        p:=liste[x]; 
        if (p>1) then
          anz:=anz+1;
          siebung (x+p,  p);
          siebung (p-x, p);
        end_if;
    end_for;

    for x from round (liste_max/3)+1 to liste_max do
        p:=liste[x]; 
        if (p>1) then
           anz:=anz+1;
           siebung (p-x, p);
        end_if;
    end_for;
    print (anz);

3. c) Improved programming for speed, Hensel-Lifting



  • liste_max:=1000;
    anz:=0;

    f:=proc (x)
    begin
       return (4*x2+1);
    end;

    fd:=proc (x)
    begin
       return (8*x);
    end;

    siebung:=proc (s, p, a)
    begin
       while (s<=liste_max) do
          liste[s]:=liste[s]/p;
          s:=s+a;
       end_while;
    end_proc;

    hensel:=proc (s, p)
    begin
         a:=p;
         siebung (s, p, a);
         inv:=fd(s)^(-1) mod p;
         repeat
            a:=a*p;
            s:=s-f(s)*inv;
            while (s<0) do
              s:=s+a;
            end_while;
            siebung (s, p, a);
         until s>liste_max end_repeat;
    end_proc;

    for x from 1 to liste_max do
       liste [x]:=f (x);
    end_for;

    for x from 1 to liste_max/3 do
       p:=liste[x];  
    //   print (x, p);
       if (p>1) then
          anz:=anz+1;
          s:=x+p;
          if (s<=liste_max) then
              hensel (s, p);
          end_if;
          s:=p-x;
          if (s<=liste_max) then
              hensel (s, p);
          end_if;
       end_if;
    end_for;

    for x from round (liste_max/3)+1 to liste_max do
       p:=liste[x];  
    //   print (x, p);
       if (p>1) then
          anz:=anz+1;
          s:=p-x;
          if (s<=liste_max) then
              hensel (s, p);
          end_if;
       end_if;
    end_for;
    print ("Anzahl = ", anz);


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=4x2+1
Column E = reducible primes with p | 4x2+1 and p < 4x2+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)=4x^2+1

P(x) | 4x^2+1

C/B

D/B

E/B

C(n) / C(n-1)

D(n) / D(n-1)

E(n) / E(n-1)

 

1

10

9

7

2

0,900000

0,700000

0,200000

   

 

2

100

87

33

54

0,870000

0,330000

0,540000

9,666667

4,714286

27,000000

 

3

1.000

836

208

628

0,836000

0,208000

0,628000

9,609195

6,303030

11,629630

 

4

10.000

8.000

1.558

6.442

0,800000

0,155800

0,644200

9,569378

7,490385

10,257962

 

5

100.000

78.124

12.390

65.734

0,781240

0,123900

0,657340

9,765500

7,952503

10,203974

 

6

1.000.000

766.585

102.204

664.381

0,766585

0,102204

0,664381

9,812414

8,248910

10,107114

 

7

10.000.000

7.556.731

872.120

6.684.611

0,755673

0,087212

0,668461

9,857656

8,533130

10,061412

 

8

100.000.000

74.771.106

7.605.407

67.165.699

0,747711

0,076054

0,671657

9,894636

8,720597

10,047810

 

9

1.000.000.000

741.554.656

67.420.596

674.134.060

0,741555

0,067421

0,674134

9,917663

8,864824

10,036880

 

10

10.000.000.000

7.366.252.759

605.573.968

6.760.678.791

0,736625

0,060557

0,676068

9,933526

8,982032

10,028686

 

11

100.000.000.000

73.261.462.211

5.496.160.249

67.765.301.962

0,732615

0,054962

0,677653

9,945554

9,075952

10,023446

 

12

1.000.000.000.000

729.280.694.469

50.315.070.934

678.965.623.535

0,729281

0,050315

0,678966

9,954493

9,154586

10,019370

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A

B

C

D

E

F

G

H

I

J

K

 

2^n

x

all Primes

P(x)=4x^2+1

P(x) | 4x^2+1

C/B

D/B

E/B

C(n) / C(n-1)

D(n) / D(n-1)

E(n) / E(n-1)

 

1

2

2

2

0

1,000000

1,000000

0,000000

   

 

2

4

4

3

1

1,000000

0,750000

0,250000

2,000000

1,500000

 

 

3

8

8

6

2

1,000000

0,750000

0,250000

2,000000

2,000000

2,000000

 

4

16

15

9

6

0,937500

0,562500

0,375000

1,875000

1,500000

3,000000

 

5

32

30

13

17

0,937500

0,406250

0,531250

2,000000

1,444444

2,833333

 

6

64

58

23

35

0,906250

0,359375

0,546875

1,933333

1,769231

2,058824

 

7

128

112

42

70

0,875000

0,328125

0,546875

1,931034

1,826087

2,000000

 

8

256

220

69

151

0,859375

0,269531

0,589844

1,964286

1,642857

2,157143

 

9

512

441

113

328

0,861328

0,220703

0,640625

2,004545

1,637681

2,172185

 

10

1.024

855

211

644

0,834961

0,206055

0,628906

1,938776

1,867257

1,963415

 

11

2.048

1.679

392

1.287

0,819824

0,191406

0,628418

1,963743

1,857820

1,998447

 

12

4.096

3.323

712

2.611

0,811279

0,173828

0,637451

1,979154

1,816327

2,028749

 

13

8.192

6.595

1.300

5.295

0,805054

0,158691

0,646362

1,984652

1,825843

2,027959

 

14

16.384

13.045

2.458

10.587

0,796204

0,150024

0,646179

1,978014

1,890769

1,999433

 

15

32.768

25.880

4.614

21.266

0,789795

0,140808

0,648987

1,983902

1,877136

2,008690

 

16

65.536

51.435

8.417

43.018

0,784836

0,128433

0,656403

1,987442

1,824231

2,022853

 

17

131.072

102.141

15.866

86.275

0,779274

0,121048

0,658226

1,985827

1,884995

2,005556

 

18

262.144

203.029

29.842

173.187

0,774494

0,113838

0,660656

1,987733

1,880877

2,007383

 

19

524.288

403.734

56.533

347.201

0,770061

0,107828

0,662233

1,988553

1,894411

2,004775

 

20

1.048.576

803.573

106.786

696.787

0,766347

0,101839

0,664508

1,990353

1,888914

2,006869

 

21

2.097.152

1.599.253

203.024

1.396.229

0,762583

0,096809

0,665774

1,990178

1,901223

2,003810

 

22

4.194.304

3.184.946

387.307

2.797.639

0,759350

0,092341

0,667009

1,991521

1,907691

2,003711

 

23

8.388.608

6.344.870

739.670

5.605.200

0,756367

0,088176

0,668192

1,992144

1,909777

2,003547

 

24

16.777.216

12.645.628

1.416.634

11.228.994

0,753738

0,084438

0,669300

1,993048

1,915224

2,003317

 

25

33.554.432

25.207.257

2.716.921

22.490.336

0,751235

0,080971

0,670264

1,993357

1,917871

2,002881

 

26

67.108.864

50.260.969

5.218.925

45.042.044

0,748947

0,077768

0,671179

1,993909

1,920897

2,002729

 

27

134.217.728

100.239.238

10.044.584

90.194.654

0,746841

0,074838

0,672003

1,994375

1,924646

2,002455

 

28

268.435.456

199.958.544

19.352.154

180.606.390

0,744904

0,072092

0,672811

1,994813

1,926626

2,002407

 

29

536.870.912

398.940.000

37.339.023

361.600.977

0,743084

0,069549

0,673534

1,995114

1,929450

2,002149

 

30

1.073.741.824

796.054.419

72.139.394

723.915.025

0,741383

0,067185

0,674198

1,995424

1,932011

2,001972

 

31

2.147.483.648

1.588.702.041

139.535.722

1.449.166.319

0,739797

0,064976

0,674821

1,995720

1,934251

2,001846

 

32

4.294.967.296

3.171.017.355

270.187.319

2.900.830.036

0,738310

0,062908

0,675402

1,995980

1,936331

2,001723

 

33

8.589.934.592

6.330.108.091

523.695.184

5.806.412.907

0,736922

0,060966

0,675955

1,996239

1,938267

2,001638

 

34

17.179.869.184

12.637.730.074

1.016.029.275

11.621.700.799

0,735613

0,059141

0,676472

1,996448

1,940116

2,001528

 

35

34.359.738.368

25.233.098.862

1.973.029.795

23.260.069.067

0,734380

0,057423

0,676957

1,996648

1,941903

2,001434

 

36

68.719.476.736

50.386.282.403

3.834.641.364

46.551.641.039

0,733217

0,055801

0,677416

1,996833

1,943529

2,001354

 

37

137.438.953.472

100.621.550.807

7.458.662.438

93.162.888.369

0,732118

0,054269

0,677849

1,997003

1,945074

2,001280

 

38

274.877.906.944

200.957.079.562

14.518.923.630

186.438.155.932

0,731078

0,052820

0,678258

1,997157

1,946585

2,001206

 

39

549.755.813.888

401.371.984.579

28.282.415.899

373.089.568.680

0,730091

0,051445

0,678646

1,997302

1,947969

2,001144

 

40

1.099.511.627.776

801.714.900.206

55.130.064.460

746.584.835.746

0,729155

0,050141

0,679015

1,997436

1,949270

2,001087

 

           

 

           

 

            
            

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 4x2+1
The orange dots / column G are the values for the primes with p=4x2+1
The yellow dots / column H are the values for the primes by the first occurance with p|4x2+1 and p smaller than 4x2+1
The x-axis is the logarithm to the base of 2 and goes up to 240



4. c) Graphic of the proportion between the "reducible" and the "big" primes


A B C D E
2^n x P(x) | 4x^2+1 P(x)=4x^2+1 C / D





1 2 0 2 0,0000
2 4 1 3 0,3333
3 8 2 6 0,3333
4 16 6 9 0,6667
5 32 17 13 1,3077
6 64 35 23 1,5217
7 128 70 42 1,6667
8 256 151 69 2,1884
9 512 328 113 2,9027
10 1.024 644 211 3,0521
11 2.048 1.287 392 3,2832
12 4.096 2.611 712 3,6671
13 8.192 5.295 1.300 4,0731
14 16.384 10.587 2.458 4,3072
15 32.768 21.266 4.614 4,6090
16 65.536 43.018 8.417 5,1108
17 131.072 86.275 15.866 5,4377
18 262.144 173.187 29.842 5,8035
19 524.288 347.201 56.533 6,1416
20 1.048.576 696.787 106.786 6,5251
21 2.097.152 1.396.229 203.024 6,8772
22 4.194.304 2.797.639 387.307 7,2233
23 8.388.608 5.605.200 739.670 7,5780
24 16.777.216 11.228.994 1.416.634 7,9265
25 33.554.432 22.490.336 2.716.921 8,2779
26 67.108.864 45.042.044 5.218.925 8,6305
27 134.217.728 90.194.654 10.044.584 8,9794
28 268.435.456 180.606.390 19.352.154 9,3326
29 536.870.912 361.600.977 37.339.023 9,6843
30 1.073.741.824 723.915.025 72.139.394 10,0349
31 2.147.483.648 1.449.166.319 139.535.722 10,3856
32 4.294.967.296 2.900.830.036 270.187.319 10,7364
33 8.589.934.592 5.806.412.907 523.695.184 11,0874
34 17.179.869.184 11.621.700.799 1.016.029.275 11,4384
35 34.359.738.368 23.260.069.067 1.973.029.795 11,7890
36 68.719.476.736 46.551.641.039 3.834.641.364 12,1398
37 137.438.953.472 93.162.888.369 7.458.662.438 12,4906
38 274.877.906.944 186.438.155.932 14.518.923.630 12,8410
39 549.755.813.888 373.089.568.680 28.282.415.899 13,1916
40 1.099.511.627.776 746.584.835.746 55.130.064.460 13,5422


4. d) 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
122021010
243121020
386152040
4169274050
53213497060
66423914110120
7128421527210210
8256692445360330
95121134172600530
101.0242117014110901020
112.04839212726519401980
124.09671223148136003520
138.1921.30043686465106490
1416.3842.4588431.6151.24401.2140
1532.7684.6141.5473.0672.33002.2840
1665.5368.4172.8545.5634.24604.1710
17131.07215.8665.32310.5437.93807.9280
18262.14429.84210.01319.82914.955014.8870
19524.28856.53318.83937.69428.171028.3620
201.048.576106.78635.39271.39453.338053.4480
212.097.152203.02467.653135.371101.1190101.9050
224.194.304387.307128.939258.368193.2350194.0720
238.388.608739.670246.669493.001369.2730370.3970
2416.777.2161.416.634472.296944.338708.1670708.4670
2533.554.4322.716.921905.5071.811.4141.358.36901.358.5520
2667.108.8645.218.9251.739.9163.479.0092.608.73602.610.1890
27134.217.72810.044.5843.348.6446.695.9405.023.04305.021.5410
28268.435.45619.352.1546.451.98812.900.1669.675.25309.676.9010
29536.870.91237.339.02312.447.47124.891.55218.667.885018.671.1380
301.073.741.82472.139.39424.049.06348.090.33136.067.539036.071.8550
312.147.483.648139.535.72246.514.86293.020.86069.768.975069.766.7470
324.294.967.296270.187.31990.058.651180.128.668135.092.2840135.095.0350
338.589.934.592523.695.183174.558.447349.136.736261.845.6380261.849.5450
3417.179.869.1841.016.029.273338.653.157677.376.116508.003.5360508.025.7370
3534.359.738.3681.973.029.784657.637.4591.315.392.325986.505.2540986.524.5300
3668.719.476.7363.834.641.3461.278.160.8622.556.480.4841.917.306.43201.917.334.9140

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
241100010
382110020
4166332040
532171078090
664351817140210
7128703733340360
82561517675740770
951232816915915701710
101.02464433630832703170
112.0481.28766262563606510
124.0962.6111.3531.2581.29601.3150
138.1925.2952.7492.5462.66602.6290
1416.38410.5875.5055.0825.31505.2720
1532.76821.26610.99310.27310.609010.6570
1665.53643.01822.21620.80221.498021.5200
17131.07286.27544.33241.94343.176043.0990
18262.144173.18788.86584.32286.455086.7320
19524.288347.201178.092169.109173.3910173.8100
201.048.576696.787357.106339.681348.3620348.4250
212.097.1521.396.229714.531681.698698.2600697.9690
224.194.3042.797.6391.431.1071.366.5321.397.96401.399.6750
238.388.6085.605.2002.863.6132.741.5872.801.84902.803.3510
2416.777.21611.228.9945.731.4905.497.5045.614.77805.614.2160
2533.554.43222.490.33611.472.27111.018.06511.243.966011.246.3700
2667.108.86445.042.04422.954.70722.087.33722.523.314022.518.7300
27134.217.72890.194.65445.926.89944.267.75545.096.842045.097.8120
28268.435.456180.606.39091.911.41888.694.97290.303.992090.302.3980
29536.870.912361.600.977183.879.751177.721.226180.806.4060180.794.5710
301.073.741.824723.915.025367.889.425356.025.600361.957.3710361.957.6540
312.147.483.6481.449.166.319736.045.612713.120.707724.566.5610724.599.7580
324.294.967.2962.900.830.0361.472.593.5251.428.236.5111.450.402.31501.450.427.7210
338.589.934.5925.806.412.9072.946.146.8572.860.266.0502.903.179.50402.903.233.4030
3417.179.869.18411.621.700.7995.894.076.1015.727.624.6985.810.874.33805.810.826.4610
3534.359.738.36823.260.069.06411.791.559.39611.468.509.66811.630.035.439011.630.033.6250
3668.719.476.73646.551.641.00723.589.484.63622.962.156.37123.275.792.632023.275.848.3750