Inhaltsverzeichnis

Development of
Algorithmic Constructions

12:43:31
Deutsch
19.Sep 2021


Prime sieving for the polynomial f(n)=2n2+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
c) Improved programming for speed with Hensel-lifting
d) Programming 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) Graphics 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 congruent to {1, 3} mod 8; or, odd primes of form x2+2*y2.
b) Primes of the form 2n2 + 1
c) a(n)= Number of distinct prime divisors (taken together) of numbers of the form 2n2+1 for n<=10^n
d) infinite sequence of primes concerning the polynom f(n)=2n2+1 with 1
e) infinite sequence of primes concerning the polynom f(n)=2n2+1 with the factorisation in the complex field

0. Abstract:


Similar to the quadratic polynomials descriped before there are listed some algorithms
how to sieve the primes p(n)=2n2+1 and the reducible primes with p | 2n2+1.

All primes can be found by regarding the three following polynomials :
f(n)=2n2-1, f(m)=2m2+1 and f(o)=4o2+1

The primes concerning the polynomial f(n)=2n2+1 with p = 2n2+1 and p | 2n2+1 are kind of p = 1 or 3 mod 8. proof

One part in this article is the construction of a program in C for the investigation of the distribution of the primes concerning this polynomial.
Calculation was done 2014 in approximately 30 days on Athlon 64 600e processor on one core with 16 Gbyte Ram and 2 Terabyte of disk.
The results for the primes and the reducible primes for n up to 1012 resp. up to 240 is reported.

1. Mathematical theory


Let f(n) = 2n2+1 with n element of N

The following lemmas explain the mathematical background which is used for the described algorithms.

a) Lemma: If p | f(n) then also p | f(n+p)

   p | f(n)   <=> 2n2 + 1 = 0                    mod p
   p | f(n+p) <=> 2(n+p)2 + 1 = 0                mod p
              <=> 2n2 + 4np + 2p2 + 1 = 0        mod p
              <=> 2n2 + 1  = 0                   mod p

   Thus if p | f(n) then p | f(n+p)

b) Lemma: If p | f(n) then also p | f(-n)

   p | f(n)    <=> 2n2 + 1 = 0                   mod p
   p | f(-n)   <=> 2(-n)2 + 1 = 0                mod p
               <=> 2n2 + 1 = 0                   mod p

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

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

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

d) Lemma: All primes (without the 2) appear as factor on the three polynoms: f(n)=4n2+1, f(n)=2n2+1, f(n)=2n2-1.

   Proof: Let p be a prime, p>2

   Then there is some n element of N and some {f, g, h} such that p divides t(n)
   Assume first that p = 4k+1 for some k element N
   Then -1 is a square in Fp* and hence there is some a element Fp* such that
   a2= -1. 
Put n´:=2^(-1)a element Fp and choose some n element N such that n´= n mod p
then 4n2 = 4n´2 = 4*2^(-2)a2 = a2 = -1 mod p. Hence p divides h (n) = 4n2+1 The remaining primes are of the form 8k+3 or 8k-1. Assume that p = 8k+3 for some k element N Then -2 is a square in Fp and so is -1/2. So there is n element N such that n2 = -1/2 mod p Hence p divides g(n) = 2n2+1. Assume finally that p = 8k-1 Then 2 is a square in Fp and so is 1/2. So there is n element N such that n2 = 1/2 mod p Hence p divides f(n) = 2n2-1. alternativ proof: discriminant of f(m)=4m2+1 is equal -1. discriminant of f(n)=2n2+1 is equal -2 discriminant of f(o)=2o2-1 is equal 2 Therefore discr [f(m)]*discr [f(n)]=discr [f(o)]

2. Description of the basic algorithm


For a more detailed description see the description of the polynom f(n)=n2+1

a) Create a list from n=1 to n=list_max=100 with f(n)=2n2+1

f(1)= 3
f(2)= 9 = 32
f(3)= 19
f(4)= 33 = 3*11
f(5)= 51 = 3*17
f(6)= 73
f(7)= 99 = 32*11
f(8)= 129 = 3*43
f(9)= 163
f(10)= 201 = 3*67
f(11)= 243 = 3^5
f(12)= 289 = 172
f(13)= 339 = 3*113
f(14)= 393 = 3*131
f(15)= 451 = 11*41
f(16)= 513 = 33*19
f(17)= 579 = 3*193
f(18)= 649 = 11*59
f(19)= 723 = 3*241
f(20)= 801 = 32*89
f(21)= 883
f(22)= 969 = 3*17*19
f(23)= 1059 = 3*353
f(24)= 1153
f(25)= 1251 = 32*139
f(26)= 1353 = 3*11*41
f(27)= 1459
f(28)= 1569 = 3*523
f(29)= 1683 = 32*11*17
f(30)= 1801
f(31)= 1923 = 3*641
f(32)= 2049 = 3*683
f(33)= 2179
f(34)= 2313 = 32*257
f(35)= 2451 = 3*19*43
f(36)= 2593
f(37)= 2739 = 3*11*83
f(38)= 2889 = 32*107
f(39)= 3043 = 17*179
f(40)= 3201 = 3*11*97
f(41)= 3363 = 3*19*59
f(42)= 3529
f(43)= 3699 = 33*137
f(44)= 3873 = 3*1291
f(45)= 4051
f(46)= 4233 = 3*17*83
f(47)= 4419 = 32*491
f(48)= 4609 = 11*419
f(49)= 4803 = 3*1601
f(50)= 5001 = 3*1667
f(51)= 5203 = 112*43
f(52)= 5409 = 32*601
f(53)= 5619 = 3 1873
f(54)= 5833 = 19*307
f(55)= 6051 = 3*2017
f(56)= 6273 = 32*17*41
f(57)= 6499 = 67*97
f(58)= 6729 = 3*2243
f(59)= 6963 = 3*11*211
f(60)= 7201 = 19*379
f(61)= 7443 = 32*827
f(62)= 7689 = 3*11*233
f(63)= 7939 = 17*467
f(64)= 8193 = 3*2731
f(65)= 8451 = 33*313
f(66)= 8713
f(67)= 8979 = 3*41*73
f(68)= 9249 = 3*3083
f(69)= 9523 = 89*107
f(70)= 9801 = 34*112
f(71)= 10083 = 3*3361
f(72)= 10369
f(73)= 10659 = 3*11*17*19
f(74)= 10953 = 32*1217
f(75)= 11251
f(76)= 11553 = 3*3851
f(77)= 11859 = 3*59*67
f(78)= 12169 = 43*283
f(79)= 12483 = 32*19*73
f(80)= 12801 = 3*17*251
f(81)= 13123 = 11*1193
f(82)= 13449 = 3*4483
f(83)= 13779 = 32*1531
f(84)= 14113 = 11*1283
f(85)= 14451 = 3*4817
f(86)= 14793 = 3*4931
f(87)= 15139
f(88)= 15489 = 32*1721
f(89)= 15843 = 3*5281
f(90)= 16201 = 17*953
f(91)= 16563 = 3*5521
f(92)= 16929 = 34*11*19
f(93)= 17299
f(94)= 17673 = 3*43*137
f(95)= 18051 = 3*11*547
f(96)= 18433
f(97)= 18819 = 33*17*41
f(98)= 19209 = 3*19*337
f(99)= 19603
f(100)= 20001 = 3*59*113

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

c) f(2)= 9 respectively f´(2)=1 (Nothing to do)

d) f(3)=19, divide f(3+k*19) / 19 as often as there is no factor 19 in the result.
Divide f(-3+k*19) / 19 as often as there is no factor 19 in the result.

e) Go for x from 4 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) Programing of the basic algorithm


This is a short implementation for the algorithm concerning the polynom f(n)=2n2+1.
Every prime which occurs is sieved out resp. divides periodically at two positions the initialised list.
The procedure sieving only divides as often as possible the function values in the list by the sieving primes.

  • 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]:=2*x2+1;
    end_for;

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

You get as result an unsorted list of primes.

3. b) Improved programming for speed


The main loop for x from 1 to liste_max is divided into two loops.
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

  • 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]:=2*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);
          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 with Hensel-lifting


The Hensel-lifting explains for which n and f´(n)=p
f(n) | p2, f(n) | p3, f(n) | p4 and so on.
Only one division instead of two are needed.

  • liste_max:=1000;
    anz:=0;

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

    fd:=proc (x)
    begin
       return (4*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);

3. d) Programming in the complex field



f(x)=2x2+1 = [ √2x + I ] * [ √2x - I ]
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 with adjoined square root 2.

        liste_max:=100;

        siebung:=proc (stelle, x, p, liste)
        begin
         
           dr:=r[x];
           if liste=1 then
              di:=i[x];
           else
              di:=-i[x];
           end_if;
           d:=dr2+di2;
           
           while stelle<=liste_max do
              rl:=r[stelle];
              il:=i[stelle];

              while TRUE do
                  //  -I2=+
                  a:=(rl*dr+il*di)/d;
                  b:=(il*dr-rl*di)/d;
                  if (is (a, Type::Integer)=TRUE or is (b, Type::Integer)=TRUE) then
                     rl:=a;
                     il:=b;
                  else
                    break;
                  end_if;
              end_while;

              r[stelle]:=rl;
              i[stelle]:=il;   
              stelle:=stelle+p;
           end_while;
        end_proc;

        for x from 1 to liste_max-1 do
           r[x]:=2^(1/2)*x;
           i[x]:=1;
        end_for;

        for x from 1 to liste_max-1 do
           // r[x]2-(i[x]*I)2
           p:=r[x]2+i[x]2;
           if p>1 then 
              a:=r[x];
              b:=i[x];
              print ("x=",x,"prim=",p,"=(",a,"+",b*I,")*(",a,"+",b*I,")=",a2,"+",b2);      
              siebung (x+p, x, p, 1);
              siebung (p-x, x, p, 2);
           end_if;
        end_for;

You get as result the factorisation of the primes in the complex field of adjoined square root 2.

4. a) Table up to 1012 and table up to 240


Primes as divisor p(x) | 2x2+1, this means that the prime is a divisor of p(x)=2x2+1 and occurs the first time,
instead of the primes p(x)=2x2+1, which means that there is a prime, which is a result of 2x2+1 for a special x.

A

B

C

D

E

F

G

H

I

J

K

 

10^n

x

all Primes

P(x)=2x^2+1

P(x) | 2x^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

8

4

4

0,800000

0,400000

0,400000

   

 

2

100

76

19

57

0,760000

0,190000

0,570000

9,500000

4,750000

14,250000

 

3

1.000

760

117

643

0,760000

0,117000

0,643000

10,000000

6,157895

11,280702

 

4

10.000

7.445

841

6.604

0,744500

0,084100

0,660400

9,796053

7,188034

10,270607

 

5

100.000

73.477

6.606

66.871

0,734770

0,066060

0,668710

9,869308

7,854935

10,125833

 

6

1.000.000

726.948

54.629

672.319

0,726948

0,054629

0,672319

9,893545

8,269603

10,053970

 

7

10.000.000

7.218.256

462.547

6.755.709

0,721826

0,046255

0,675571

9,929536

8,467060

10,048368

 

8

100.000.000

71.801.859

4.027.074

67.774.785

0,718019

0,040271

0,677748

9,947259

8,706302

10,032224

 

9

1.000.000.000

715.087.632

35.630.373

679.457.259

0,715088

0,035630

0,679457

9,959180

8,847708

10,025222

 

10

10.000.000.000

7.127.665.635

319.422.804

6.808.242.831

0,712767

0,031942

0,680824

9,967541

8,964902

10,020119

 

11

100.000.000.000

71.089.166.879

2.895.004.512

68.194.162.367

0,710892

0,028950

0,681942

9,973696

9,063237

10,016412

 

12

1.000.000.000.000

709.344.259.821

26.471.105.994

682.873.153.827

0,709344

0,026471

0,682873

9,978233

9,143718

10,013660

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A

B

C

D

E

F

G

H

I

J

K

 

2^n

x

all Primes

P(x)=2x^2+1

P(x) | 2x^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

1

1

0

0,500000

0,500000

0,000000

   

 

2

4

3

2

1

0,750000

0,500000

0,250000

3,000000

2,000000

 

 

3

8

6

3

3

0,750000

0,375000

0,375000

2,000000

1,500000

3,000000

 

4

16

11

4

7

0,687500

0,250000

0,437500

1,833333

1,333333

2,333333

 

5

32

24

8

16

0,750000

0,250000

0,500000

2,181818

2,000000

2,285714

 

6

64

50

12

38

0,781250

0,187500

0,593750

2,083333

1,500000

2,375000

 

7

128

99

22

77

0,773438

0,171875

0,601563

1,980000

1,833333

2,026316

 

8

256

194

37

157

0,757813

0,144531

0,613281

1,959596

1,681818

2,038961

 

9

512

388

70

318

0,757813

0,136719

0,621094

2,000000

1,891892

2,025478

 

10

1.024

776

120

656

0,757813

0,117188

0,640625

2,000000

1,714286

2,062893

 

11

2.048

1.540

223

1.317

0,751953

0,108887

0,643066

1,984536

1,858333

2,007622

 

12

4.096

3.073

392

2.681

0,750244

0,095703

0,654541

1,995455

1,757848

2,035687

 

13

8.192

6.099

714

5.385

0,744507

0,087158

0,657349

1,984705

1,821429

2,008579

 

14

16.384

12.160

1.293

10.867

0,742188

0,078918

0,663269

1,993769

1,810924

2,018013

 

15

32.768

24.225

2.372

21.853

0,739288

0,072388

0,666901

1,992188

1,834493

2,010951

 

16

65.536

48.262

4.484

43.778

0,736420

0,068420

0,667999

1,992239

1,890388

2,003295

 

17

131.072

96.117

8.450

87.667

0,733315

0,064468

0,668846

1,991567

1,884478

2,002536

 

18

262.144

191.661

15.902

175.759

0,731129

0,060661

0,670467

1,994039

1,881893

2,004848

 

19

524.288

382.127

29.956

352.171

0,728849

0,057137

0,671713

1,993765

1,883788

2,003715

 

20

1.048.576

762.133

57.002

705.131

0,726827

0,054361

0,672465

1,994449

1,902858

2,002240

 

21

2.097.152

1.520.931

108.191

1.412.740

0,725236

0,051589

0,673647

1,995624

1,898021

2,003514

 

22

4.194.304

3.035.027

205.398

2.829.629

0,723607

0,048971

0,674636

1,995506

1,898476

2,002937

 

23

8.388.608

6.058.303

392.498

5.665.805

0,722206

0,046789

0,675417

1,996128

1,910914

2,002314

 

24

16.777.216

12.094.615

751.210

11.343.405

0,720895

0,044776

0,676120

1,996370

1,913921

2,002082

 

25

33.554.432

24.149.710

1.439.421

22.710.289

0,719717

0,042898

0,676819

1,996732

1,916137

2,002070

 

26

67.108.864

48.226.395

2.764.920

45.461.475

0,718629

0,041201

0,677429

1,996976

1,920856

2,001801

 

27

134.217.728

96.316.171

5.316.867

90.999.304

0,717611

0,039614

0,677998

1,997167

1,922973

2,001680

 

28

268.435.456

192.381.714

10.237.140

182.144.574

0,716678

0,038136

0,678541

1,997398

1,925408

2,001604

 

29

536.870.912

384.295.122

19.746.417

364.548.705

0,715805

0,036781

0,679025

1,997566

1,928900

2,001425

 

30

1.073.741.824

767.729.885

38.119.892

729.609.993

0,715004

0,035502

0,679502

1,997761

1,930471

2,001406

 

31

2.147.483.648

1.533.851.929

73.682.997

1.460.168.932

0,714255

0,034311

0,679944

1,997906

1,932928

2,001301

 

32

4.294.967.296

3.064.705.816

142.607.233

2.922.098.583

0,713557

0,033203

0,680354

1,998045

1,935416

2,001206

 

33

8.589.934.592

6.123.796.529

276.272.479

5.847.524.050

0,712904

0,032162

0,680741

1,998168

1,937296

2,001139

 

34

17.179.869.184

12.237.071.081

535.760.398

11.701.310.683

0,712291

0,031185

0,681106

1,998282

1,939246

2,001071

 

35

34.359.738.368

24.454.319.674

1.039.909.544

23.414.410.130

0,711714

0,030265

0,681449

1,998380

1,940997

2,001007

 

36

68.719.476.736

48.871.362.246

2.020.283.544

46.851.078.702

0,711172

0,029399

0,681773

1,998476

1,942749

2,000951

 

37

137.438.953.472

97.672.370.547

3.928.018.222

93.744.352.325

0,710660

0,028580

0,682080

1,998560

1,944291

2,000901

 

38

274.877.906.944

195.211.920.067

7.643.397.852

187.568.522.215

0,710177

0,027807

0,682370

1,998640

1,945866

2,000851

 

39

549.755.813.888

390.172.411.497

14.883.784.616

375.288.626.881

0,709719

0,027073

0,682646

1,998712

1,947273

2,000808

 

40

1.099.511.627.776

779.868.595.785

29.003.055.988

750.865.539.797

0,709286

0,026378

0,682908

1,998779

1,948634

2,000768

 

           

 

           

 

            
            

4. b) Graphics of the distribution of the primes


The green dots / column F are the values for all primes concerning the polynom 2x2+1
The orange dots / column G are the values for the primes with p=2x2+1
The yellow dots / column H are the values for the primes by the first occurance with p|2x2+1 and p smaller than 2x2+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 E D E
2^n x P(x) | 2x^2+1 P(x)=2x^2+1 C / D





1 2 0 1 0,0000
2 4 1 2 0,5000
3 8 3 3 1,0000
4 16 7 4 1,7500
5 32 16 8 2,0000
6 64 38 12 3,1667
7 128 77 22 3,5000
8 256 157 37 4,2432
9 512 318 70 4,5429
10 1.024 656 120 5,4667
11 2.048 1.317 223 5,9058
12 4.096 2.681 392 6,8393
13 8.192 5.385 714 7,5420
14 16.384 10.867 1.293 8,4045
15 32.768 21.853 2.372 9,2129
16 65.536 43.778 4.484 9,7632
17 131.072 87.667 8.450 10,3748
18 262.144 175.759 15.902 11,0526
19 524.288 352.171 29.956 11,7563
20 1.048.576 705.131 57.002 12,3703
21 2.097.152 1.412.740 108.191 13,0578
22 4.194.304 2.829.629 205.398 13,7763
23 8.388.608 5.665.805 392.498 14,4352
24 16.777.216 11.343.405 751.210 15,1002
25 33.554.432 22.710.289 1.439.421 15,7774
26 67.108.864 45.461.475 2.764.920 16,4422
27 134.217.728 90.999.304 5.316.867 17,1152
28 268.435.456 182.144.574 10.237.140 17,7925
29 536.870.912 364.548.705 19.746.417 18,4615
30 1.073.741.824 729.609.993 38.119.892 19,1399
31 2.147.483.648 1.460.168.932 73.682.997 19,8169
32 4.294.967.296 2.922.098.583 142.607.233 20,4905
33 8.589.934.592 5.847.524.050 276.272.479 21,1658
34 17.179.869.184 11.701.310.683 535.760.398 21,8406





 
35 34.359.738.368 23.414.410.130 1.039.909.544 22,5158
36 68.719.476.736 46.851.078.702 2.020.283.544 23,1903
37 137.438.953.472 93.744.352.325 3.928.018.222 23,8656
38 274.877.906.944 187.568.522.215 7.643.397.852 24,5399
39 549.755.813.888 375.288.626.881 14.883.784.616 25,2146
40 1.099.511.627.776 750.865.539.797 29.003.055.988 25,8892


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
121000100
242100200
383201200
4164301300
5328703500
664121105700
71282221091300
825637360162100
951270690313900
101.0241201190556500
112.048223222011011300
124.096392391019519700
138.192714713035635800
1416.3841.2931.292065963400
1532.7682.3722.37101.1901.18200
1665.5364.4844.48302.2422.24200
17131.0728.4508.44904.2344.21600
18262.14415.90215.90107.9557.94700
19524.28829.95629.955015.02514.93100
201.048.57657.00257.001028.57828.42400
212.097.152108.191108.190054.15054.04100
224.194.304205.398205.3970102.700102.69800
238.388.608392.498392.4970196.330196.16800
2416.777.216751.210751.2090375.676375.53400
2533.554.4321.439.4211.439.4200719.941719.48000
2667.108.8642.764.9202.764.91901.382.1231.382.79700
27134.217.7285.316.8675.316.86602.657.4022.659.46500
28268.435.45610.237.14010.237.13905.117.2985.119.84200
29536.870.91219.746.41719.746.41609.870.4969.875.92100
301.073.741.82438.119.89238.119.891019.054.82219.065.07000
312.147.483.64873.682.99773.682.996036.837.59736.845.40000
324.294.967.296142.607.232142.607.231071.296.02971.311.20300
338.589.934.592276.272.478276.272.4770138.126.078138.146.40000
3417.179.869.184535.760.396535.760.3950267.872.126267.888.27000
3534.359.738.3681.039.909.5401.039.909.5390519.954.072519.955.46800
3668.719.476.7362.020.283.5342.020.283.53301.010.145.4891.010.138.04500

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
241010100
383121200
4167253400
532166108800
664381523162200
7128773146344300
82561577186778000
951231815216615616200
101.02465631134532932700
112.0481.31764567265466300
124.0962.6811.2781.4031.3301.35100
138.1925.3852.5922.7932.6892.69600
1416.38410.8675.2425.6255.4535.41400
1532.76821.85310.54811.30510.91910.93400
1665.53643.77821.22522.55321.84221.93600
17131.07287.66742.64845.01943.88843.77900
18262.144175.75985.56990.19088.01587.74400
19524.288352.171171.705180.466176.145176.02600
201.048.576705.131344.399360.732352.910352.22100
212.097.1521.412.740692.049720.691706.459706.28100
224.194.3042.829.6291.387.2031.442.4261.415.1181.414.51100
238.388.6085.665.8052.779.7952.886.0102.832.4812.833.32400
2416.777.21611.343.4055.569.3505.774.0555.669.3015.674.10400
2533.554.43222.710.28911.160.78511.549.50411.351.85011.358.43900
2667.108.86445.461.47522.359.08523.102.39022.731.11622.730.35900
27134.217.72890.999.30444.787.72446.211.58045.501.81145.497.49300
28268.435.456182.144.57489.716.86292.427.71291.072.24391.072.33100
29536.870.912364.548.705179.667.932184.880.773182.269.851182.278.85400
301.073.741.824729.609.993359.793.771369.816.222364.797.540364.812.45300
312.147.483.6481.460.168.932720.413.324739.755.608730.080.596730.088.33600
324.294.967.2962.922.098.5831.442.349.8851.479.748.6981.461.023.1931.461.075.39000
338.589.934.5925.847.524.0502.887.639.7822.959.884.2682.923.714.6572.923.809.39300
3417.179.869.18411.701.310.6815.780.791.6235.920.519.0585.850.587.5815.850.723.10000
3534.359.738.36823.414.410.12211.571.855.02311.842.555.09911.707.141.80111.707.268.32100
3668.719.476.73646.851.078.66823.163.013.69423.688.064.97423.425.547.55923.425.531.10900

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. List of primes concerning f(n)=2n2+1 with 1 for n < 1000:


3, 1, 19, 11, 17, 73, 1, 43, 163, 67, 1, 1, 113, 131, 41, 1, 193, 59, 241, 89, 883, 1, 353, 1153, 139, 1, 1459, 523, 1, 1801, 641, 683, 2179, 257, 1, 2593, 83, 107, 179, 97, 1, 3529, 137, 1291, 4051, 1, 491, 419, 1601, 1667, 1, 601, 1873, 307, 2017, 1, 1, 2243, 211, 379, 827, 233, 467, 2731, 313, 8713, 1, 3083, 1, 1, 3361, 10369, 1, 1217, 11251, 3851, 1, 283, 1, 251, 1193, 4483, 1531, 1283, 4817, 4931, 15139, 1721, 5281, 953, 5521, 1, 17299, 1, 547, 18433, 1, 337, 19603, 1, 2267, 20809, 643, 7211, 22051, 227, 449, 569, 1, 2689, 1297, 8363, 8513, 1, 2939, 8971, 1, 9283, 1049, 347, 1, 9923, 30259, 1, 947, 281, 10753, 331, 401, 593, 673, 34849, 3931, 11971, 36451, 1, 1, 929, 1171, 1, 2339, 4481, 13633, 619, 1, 1579, 3929, 859, 1, 4091, 563, 1, 46819, 1, 1, 48673, 16433, 1, 857, 5689, 1571, 52489, 17713, 1, 3203, 18371, 18593, 2971, 577, 19267, 1, 1, 739, 3187, 1201, 1, 62659, 2347, 521, 1, 21841, 433, 6089, 22571, 22817, 69193, 409, 23563, 71443, 587, 1, 4337, 1307, 2281, 1289, 8537, 25873, 881, 1553, 2963, 80803, 2473, 1, 83233, 1, 1489, 1993, 28843, 571, 457, 443, 1, 1, 10177, 30817, 499, 31393, 1, 95923, 787, 32561, 1, 1, 3041, 1, 2003, 1, 103969, 34961, 35267, 1, 1, 2129, 1129, 3347, 12377, 112339, 3433, 1, 115201, 12907, 39043, 6947, 2089, 13339, 11003, 1, 1, 11273, 1, 1, 1187, 1, 1, 130051, 43691, 4003, 1987, 4969, 1, 3323, 45763, 809, 139393, 46817, 1097, 8387, 1451, 2539, 691, 4451, 1, 149059, 50051, 50417, 1163, 1, 769, 14153, 52267, 5849, 761, 1, 3163, 162451, 1, 617, 8731, 55681, 1699, 659, 56843, 1, 10169, 1, 58411, 176419, 811, 19867, 180001, 1, 1483, 1321, 1867, 62017, 187273, 3307, 7027, 4441, 64067, 3793, 1609, 1, 65731, 18041, 66571, 1, 11897, 1, 3593, 206083, 23041, 6323, 209953, 1051, 1, 213859, 4219, 72161, 1, 1, 73483, 977, 6761, 1, 1, 6883, 76163, 12097, 8563, 77521, 1, 1913, 26297, 1, 79811, 80273, 1, 27067, 81667, 246403, 1, 27691, 6113, 84017, 7681, 254899, 1499, 1, 259201, 1, 1, 1249, 4649, 88817, 267913, 907, 1, 1, 8297, 1, 4691, 92753, 93251, 281251, 1, 4987, 1, 1, 32089, 26393, 97283, 5147, 7193, 32939, 5843, 299539, 100363, 1019, 2843, 101921, 1, 308899, 3833, 1, 971, 1, 35201, 318403, 9697, 107201, 17011, 1, 1, 328051, 109891, 1, 1, 111521, 112067, 30713, 1, 6689, 2833, 6043, 4273, 347779, 116483, 117041, 20753, 1, 1, 357859, 119851, 1, 362953, 121553, 1259, 368083, 2417, 2099, 5113, 1033, 2203, 1123, 1, 7489, 8923, 1, 6793, 388963, 937, 14537, 1, 1361, 132611, 2137, 14867, 134401, 405001, 135601, 1, 21601, 1, 12547, 415873, 46411, 12713, 1, 141067, 1, 426889, 1, 8443, 1, 1, 1, 438049, 13331, 16363, 26099, 7817, 149153, 449353, 1, 151051, 1009, 8017, 1, 1, 1, 154883, 466579, 52057, 156817, 472393, 158113, 1, 478243, 2713, 1, 484129, 54011, 162691, 1, 164011, 1, 1, 15091, 166667, 2083, 1697, 168673, 508033, 1, 56897, 12539, 4001, 172721, 1, 58027, 174763, 1, 1979, 3467, 28027, 2441, 4363, 538723, 60089, 16451, 32057, 182353, 1, 5683, 2753, 185153, 2393, 1091, 1, 4057, 1, 63131, 1723, 1, 191531, 576739, 1, 11393, 1, 195121, 1, 53609, 2377, 198017, 1, 66491, 1, 1, 201667, 1, 5393, 203873, 1, 616051, 1, 18803, 622729, 5081, 1, 2011, 1, 211313, 636193, 6449, 1, 1, 19553, 71947, 649801, 217361, 3697, 1, 1, 1, 1, 221953, 1, 60953, 224267, 1619, 2699, 1481, 227371, 684451, 12049, 6961, 691489, 5641, 1, 5099, 4099, 3499, 16411, 236017, 1, 712819, 21673, 239201, 1, 7297, 241603, 8171, 2273, 1427, 734473, 14449, 4177, 67433, 1, 13099, 68099, 3739, 83777, 1747, 252971, 14929, 9203, 85147, 23297, 771283, 2659, 7841, 2411, 260417, 261251, 9473, 87641, 263761, 1, 1, 29587, 801379, 1433, 268817, 808993, 1, 271363, 8419, 273067, 1, 1, 1, 1, 75641, 92737, 279073, 839809, 14779, 93889, 1, 283403, 1, 1931, 95339, 2371, 863299, 16979, 10723, 13003, 1787, 15377, 12043, 2969, 2609, 887113, 1, 1, 6833, 2153, 7321, 1409, 1, 302851, 1, 304651, 1, 83579, 307361, 1, 48817, 2521, 1, 2161, 18401, 3169, 49681, 1, 28771, 16139, 1, 1, 960499, 321091, 107339, 22531, 29443, 1, 977203, 1, 3947, 57977, 329473, 1, 994051, 17489, 333233, 91139, 6571, 4049, 1, 8243, 37657, 1811, 1, 341771, 3659, 4243, 1, 7459, 346561, 10531, 1, 4787, 18443, 1, 1753, 2579, 3011, 32297, 118747, 12041, 32563, 359171, 1080451, 1, 1, 57331, 8467, 4507, 99833, 1523, 21649, 5297, 41113, 1, 16657, 373003, 2113, 1125001, 376001, 34273, 1627, 126337, 1, 1143073, 20107, 127681, 1152163, 22651, 1657, 1161289, 1, 9491, 1170451, 1, 43577, 1179649, 394241, 23251, 4201, 1, 398353, 108923, 400417, 7043, 1, 3571, 2953, 2131, 1, 1, 1226179, 4937, 1, 1235593, 1, 37633, 6451, 1, 1, 1254529, 5051, 1, 66529, 3491, 5801, 1273609, 1, 3257, 67537, 1889, 143291, 1, 1, 2657, 118409, 2459, 1, 119291, 25793, 146521, 1321939, 1, 442817, 13729, 148331, 1, 1341523, 23593, 1, 1, 451553, 2777, 31657, 50539, 455953, 80657, 41651, 153089, 1, 41953, 1, 1391113, 3779, 465931, 1401139, 27539, 8233, 128291, 471521, 472643, 129209, 2683, 28001, 34913, 478273, 53267, 1441603, 481667, 43891, 1777, 53897, 44201, 5059, 2729, 163211, 77491, 3539, 493067, 22129, 1, 1, 1492993, 1, 166657, 1, 11681, 503441, 1, 1, 29819, 138569, 1, 56713, 1, 26987, 513923, 5347, 19121, 7723, 21313, 519793, 15787, 1566451, 1, 1, 1907, 10331, 27793, 14051, 530443, 177211, 14939, 1, 1, 1609219, 1, 538801, 1620001, 541201, 20089, 1, 1, 546017, 8779, 60937, 549643, 7907, 6203, 4289, 2251, 1, 556931, 88129, 1, 1, 1685449, 563041, 17099, 4889, 566723, 33409, 6803, 1, 9689, 6073, 1, 63929, 1, 1, 579083, 3049, 1, 1, 1752193, 585313, 4547, 160313, 34651, 590321, 161339, 2707, 594091, 7411, 596611, 1, 1, 600401, 1, 1808803, 201401, 2897, 42331, 8329, 67699, 107747, 14923, 1, 1843201, 1, 10457, 1854739, 3313, 206939, 98227, 623393, 624683, 1, 209089, 628561, 9041, 631153, 12401, 1, 635051, 636353, 1912969, 212987, 640267, 2633, 3331, 1, 3299, 1, 58921, 11953, 72307, 652081, 1960201, 2027, 218681, 1972099, 1, 9851, 9403, 1, 1, 1, 666667,