Inhaltsverzeichnis

Development of
Algorithmic Constructions

04:16:33
Deutsch
24.Nov 2020


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
c) Improved programming for speed with Hensel-lifting I
d) Improved programming for speed with Hensel-lifting II
e) Programming in the complex field
f) 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
e) Primes which could not be a factor of any Mersenne number
f) Graphic of the distribution of the sieved out primes

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 the form 2*n2 - 1
b) Numbers n such that 2*n2 - 1 is a prime
c) Primitive prime factors of the sequence 2k2 - 1 in the order that they are found
d) a(n)= Number of distinct prime divisors (taken together) of numbers of the form 2n2-1 for n<=10n
e) Mersenne numbers: 2p - 1, where p is prime
f) infinite sequence of primes concerning the polynom f(n)=2n2-1 with 1
g) infinite sequence of primes concerning the polynom f(n)=2n2-1 with the factorisation in the field with adjoined square root

7. Links
Mersenne - GIMPS Home
Mersenne prime numbers - Wikipedia
Mersenne prime numbers - Wolfram Mathworld
Mersenne Primes: History, Theorems and Lists - Chris K. Caldwell

0. Abstract:


Mersenne numbers and the polynomial f(n)=2n2-1


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

There is an interesting connection between this polynomial and the Mersenne numbers especially the Mersenne prime numbers,
as all Mersenne numbers 2p-1 are elements of f(n)=2n2-1. proof
Also that means that all factors of Mersenne numbers can be found on this polynomial.

Besides as all primes of f(n) = 2n2-1 are kind of p = 1 or 7 mod 8, proof
all possible factors of Mersenne numbers are kind of p = 1 or 7 mod 8.
That means that primes such as p = 3 or 5 mod 8 could not be a factor of Mersenne Numbers.

Therefore the sieving of the polynomial f(n)=2n2-1 explains the distribution of Mersenne numbers:
Mersenne prime numbers are "big" Primes, which are not sieved out by a prime, which appears in the polynomial before.

The question if there are infinite primes of the form p(n)=2n2-1 or infinite Mersenne prime is not answered,
but nevertheless by finding the 51th known Mersenne prime 282,589,933 -1 on 7th, december, 2018 the limit is increased.

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) All Mersenne Numbers 2p-1 with p element P are elements of f(n)=2n2-1.

   Proof: 2p-1 = 2*2(p-1) - 1 with n2=2^(p-1) respectively n = 2(p-1)/2 
<=> 2n2-1 = f(n)
b) 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) c) 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) d) Lemma: If p | f(-n) then also p | f(-n+p) This is a simple conclusion of b) and c) 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 e) 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=2 to n=list_max=100 with f(n)=2n2-1

f(2)= 7
f(3)= 17
f(4)= 31
f(5)= 49 = 72
f(6)= 71
f(7)= 97
f(8)= 127
f(9)= 161 = 7*23
f(10)= 199
f(11)= 241
f(12)= 287 = 7*41
f(13)= 337
f(14)= 391 = 17*23
f(15)= 449
f(16)= 511 = 7*73
f(17)= 577
f(18)= 647
f(19)= 721 = 7*103
f(20)= 799 = 17*47
f(21)= 881
f(22)= 967
f(23)= 1057 = 7*151
f(24)= 1151
f(25)= 1249
f(26)= 1351 = 7*193
f(27)= 1457 = 31*47
f(28)= 1567
f(29)= 1681 = 412
f(30)= 1799 = 7*257
f(31)= 1921 = 17*113
f(32)= 2047 = 23*89
f(33)= 2177 = 7*311
f(34)= 2311
f(35)= 2449 = 31*79
f(36)= 2591
f(37)= 2737 = 7*17*23
f(38)= 2887
f(39)= 3041
f(40)= 3199 = 7*457
f(41)= 3361
f(42)= 3527
f(43)= 3697
f(44)= 3871 = 72*79
f(45)= 4049
f(46)= 4231
f(47)= 4417 = 7*631
f(48)= 4607 = 17*271
f(49)= 4801
f(50)= 4999
f(51)= 5201 = 7*743
f(52)= 5407
f(53)= 5617 = 41*137
f(54)= 5831 = 73*17
f(55)= 6049 = 23*263
f(56)= 6271
f(57)= 6497 = 73*89
f(58)= 6727 = 7 312
f(59)= 6961
f(60)= 7199 = 23*313
f(61)= 7441 = 7*1063
f(62)= 7687
f(63)= 7937
f(64)= 8191
f(65)= 8449 = 7*17*71
f(66)= 8711 = 31*281
f(67)= 8977 = 47*191
f(68)= 9247 = 7*1321
f(69)= 9521
f(70)= 9799 = 41*239
f(71)= 10081 = 17*593
f(72)= 10367 = 7*1481
f(73)= 10657
f(74)= 10951 = 47*233
f(75)= 11249 = 7*1607
f(76)= 11551
f(77)= 11857 = 71*167
f(78)= 12167 = 233
f(79)= 12481 = 7*1783
f(80)= 12799
f(81)= 13121
f(82)= 13447 = 7*17*113
f(83)= 13777 = 23*599
f(84)= 14111 = 103*137
f(85)= 14449
f(86)= 14791 = 7*2113
f(87)= 15137
f(88)= 15487 = 17*911
f(89)= 15841 = 7*31*73
f(90)= 16199 = 97*167
f(91)= 16561
f(92)= 16927
f(93)= 17297 = 72*353
f(94)= 17671 = 41*431
f(95)= 18049
f(96)= 18431 = 7*2633
f(97)= 18817 = 31*607
f(98)= 19207
f(99)= 19601 = 17*1153
f(100)= 19999 = 7*2857

(1 added the factorization of the results, because it shows the periodical appearance of the primes.)

b) f(2)=7,
divide f(2+k*7) / 7 as often as there is no factor 7 in the result. k element N, 2+k*7<=Liste_max
You have to divide 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(-2+k*7) / 7 as often as there is no factor 7 in the result.k element N, k*7-2<=Liste_max
You have to divide f(5), f(12), f(19), f(26), f(33), f(40), f(47), f(54), f(61), f(68), f(75), f(82), f(89), f(96) on by 7.
(The factor 7 appears two times f(5)=7*7, you have to make two divisions.)

c) f(3)=17,
divide f(3+k*17) / 17 as often as there is no factor 17 in the result. k element N, 3+k*17<=Liste_max
You have to divide f(20), f(37), f(54), f(71), f(88) by 17.

divide f(-3+k*17) / 17 as often as there is no factor 17 in the result.k element N, k*17-3<=Liste_max
You have to divide f(14), f(31), f(48), f(65), f(82), f(99) by 17.

d) Go for n from 4 to liste_max
if f´(x) > 1
divide f(n+k*f´(n)) / f´(n) and
divide f(-n+k*f´(n)) / f´(n)
as often as there is no factor f´(n) in the result.
f´(n) is the prime which remains after dividing by f(1), f´(2) up to f´(n-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.

  • // numbers of the examined list
    liste_max:=1000;
    // number of primes which have to store
    anz_store:=0;
    // number of divisions which are made
    anz_div:=0;
    // number of primes which are found. 
    anz_prim:=0;

    siebung:=proc (s, p)
    begin
       if (s+p<liste_max) then
         anz_store:=anz_store+1;
       end_if;
       while (s<liste_max) do
           repeat
              liste [s]:=liste[s] /p;
              anz_div:=anz_div+1;
           until (liste[s] mod p > 0) end_repeat;
           s:=s+p;
       end_while;
    end_proc;

    for x from 1 to liste_max - 1 do
       liste [x]:=2*x2-1;
    end_for;

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

You get as result an unsorted list of primes.

Runtime

Runtime of the algorithm is O (n)

x Number of divisions Quotient
10 10
100 161 161 / 10 = 16.10
103 1.969 1.969 / 161 = 12.23
104 22.401 22.401 / 1.969 = 11.38
105 245.036 245.036 / 22.401 = 10.94
106 2.624.860 2.624.860 / 245.036 = 10.71
107 27.732.987 27.732.987 / 2.624.860= 10.57
108 290.244.956 290.244.956 / 27.732.987 = 10.47
109 3.016.887.643 3.016.887.643 / 290.244.956 = 10.39


Memory consumption

x stored Primes Quotient
10 1
100 14
103 114 114 / 14 = 8.14
104 882 882 / 114 = 7.74
105 6.845 6.845 / 882 = 7.76
106 55.870 55.870 / 6.845 = 8.16
107 471.493 471.493 / 55.870 = 8.44
108 4.075.075 4.075.075 / 471.493 = 8.64
109 35.883.124 35.883.124 / 4.075.075 = 8.81

3. b) Improved programming for speed


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

  • liste_max:=1000000;
    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 round (liste_max/2) 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/2)+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 I


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_prim:=0;
    anz_hensel:=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, p);
         inv:=fd(s)^(-1) mod p;
         repeat
            anz_hensel:=anz_hensel+1;
            a:=a*p;
            s:=s-f(s)*inv;
            s:=s mod a;
            siebung (s, p, a);
         until s>liste_max end_repeat;
    end_proc;

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

    for x from 1 to liste_max-1 do
       p:=liste[x];  
    //   print (x, p);
       if (p>1) then
          anz_prim:=anz_prim+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;

    print ("Anzahl Prime = ", anz_prim, " Anzahl Hensel = ", anz_hensel);

Results


x number of Hensel-lifting Factor
10 3
100 30
103 190 190 / 30 = 6.33
104 1.372 1.372 / 190 = 7.22
105 10.468 10.468 / 1.372 = 7.63
106 85.556 85.556 / 10.468 = 8.17
107 724.425 724.425 / 85.556 = 8.47
108 6.280.838 6.280.838 / 724.425 = 8.67
109 55.472.028 55.472.028 / 6.280.838 = 8.83

3. d) Improved programming with Hensel-lifting II


Only one calculation of the Hensel-lifting is made instead of two for one prime.

  • anz_hensel:=0;
    anz_prim:=0;
    liste_max:=1000;

    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 (x, p)
    begin
         siebung (x+p, p, p);
         siebung (p-x, p, p);

         s:=x;
         a:=p;
         inv:=fd(s)^(-1) mod p;
         repeat
            anz_hensel:=anz_hensel+1;
            a:=a*p;
            s:=s-f(s)*inv;
            s:=s mod a;
            siebung (s, p, a);
            siebung (a-s, p, a);
         until a-s>liste_max end_repeat;
    end_proc;

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

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

    print ("Anzahl = ", anz,"Anzahl Hensel = ", anz_hensel);

Results


x number of Hensel-lifting Factor
10 1
100 18
103 114 = 6.33
104 845 = 7.22
105 6.438 = 7.63
106 53.079 = 8.24
107 450.773 = 8.49
108 3.916.264 = 8.69
109 34.636.140 = 8.84

3. e) Programming in the field of adjoined square root


f(x)=2x2-1 = [ √2x + 1 ] * [ √2x - 1 ]
This algorithm is interesting from the mathematical point of view and the additional results.
The sieving is not made in N but in the field of adjoined square root.

  • liste_max:=1000;

    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
              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
       p:=r[x]^2-i[x]^2;
       if p>1 then 
          print (x, p, r[x], i[x]);
          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 field of adjoined square root.

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+1
Column E = reducible primes with p | x2+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)=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

7

1

0,800000

0,700000

0,100000

   

 

2

100

84

45

39

0,840000

0,450000

0,390000

10,500000

6,428571

39,000000

 

3

1.000

815

303

512

0,815000

0,303000

0,512000

9,702381

6,733333

13,128205

 

4

10.000

7.922

2.202

5.720

0,792200

0,220200

0,572000

9,720245

7,267327

11,171875

 

5

100.000

77.250

17.185

60.065

0,772500

0,171850

0,600650

9,751325

7,804269

10,500874

 

6

1.000.000

759.077

141.444

617.633

0,759077

0,141444

0,617633

9,826239

8,230666

10,282744

 

7

10.000.000

7.492.588

1.200.975

6.291.613

0,749259

0,120098

0,629161

9,870656

8,490816

10,186653

 

8

100.000.000

74.198.995

10.448.345

63.750.650

0,741990

0,104483

0,637507

9,902986

8,699886

10,132640

 

9

1.000.000.000

736.401.956

92.435.171

643.966.785

0,736402

0,092435

0,643967

9,924689

8,846872

10,101337

 

10

10.000.000.000

7.319.543.972

828.797.351

6.490.746.621

0,731954

0,082880

0,649075

9,939604

8,966255

10,079319

 

11

100.000.000.000

72.834.161.468

7.511.268.020

65.322.893.448

0,728342

0,075113

0,653229

9,950642

9,062852

10,064003

 

12

1.000.000.000.000

725.344.237.597

68.680.339.342

656.663.898.255

0,725344

0,068680

0,656664

9,958847

9,143641

10,052584

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

3

0

0,750000

0,750000

0,000000

3,000000

3,000000

 

 

3

8

6

6

0

0,750000

0,750000

0,000000

2,000000

2,000000

#DIV/0!

 

4

16

13

10

3

0,812500

0,625000

0,187500

2,166667

1,666667

#DIV/0!

 

5

32

27

17

10

0,843750

0,531250

0,312500

2,076923

1,700000

3,333333

 

6

64

54

34

20

0,843750

0,531250

0,312500

2,000000

2,000000

2,000000

 

7

128

106

55

51

0,828125

0,429688

0,398438

1,962963

1,617647

2,550000

 

8

256

212

99

113

0,828125

0,386719

0,441406

2,000000

1,800000

2,215686

 

9

512

420

178

242

0,820313

0,347656

0,472656

1,981132

1,797980

2,141593

 

10

1.024

835

309

526

0,815430

0,301758

0,513672

1,988095

1,735955

2,173554

 

11

2.048

1.656

545

1.111

0,808594

0,266113

0,542480

1,983234

1,763754

2,112167

 

12

4.096

3.295

1.002

2.293

0,804443

0,244629

0,559814

1,989734

1,838532

2,063906

 

13

8.192

6.512

1.838

4.674

0,794922

0,224365

0,570557

1,976328

1,834331

2,038378

 

14

16.384

12.889

3.376

9.513

0,786682

0,206055

0,580627

1,979269

1,836779

2,035302

 

15

32.768

25.587

6.294

19.293

0,780853

0,192078

0,588776

1,985181

1,864336

2,028067

 

16

65.536

50.829

11.743

39.086

0,775589

0,179184

0,596405

1,986517

1,865745

2,025916

 

17

131.072

101.018

21.965

79.053

0,770706

0,167580

0,603127

1,987409

1,870476

2,022540

 

18

262.144

200.903

41.386

159.517

0,766384

0,157875

0,608509

1,988784

1,884179

2,017849

 

19

524.288

399.532

78.131

321.401

0,762047

0,149023

0,613024

1,988681

1,887861

2,014839

 

20

1.048.576

795.725

147.640

648.085

0,758862

0,140800

0,618062

1,991643

1,889647

2,016437

 

21

2.097.152

1.584.289

280.678

1.303.611

0,755448

0,133838

0,621610

1,991001

1,901097

2,011482

 

22

4.194.304

3.156.024

534.268

2.621.756

0,752455

0,127379

0,625075

1,992076

1,903491

2,011149

 

23

8.388.608

6.290.171

1.019.557

5.270.614

0,749847

0,121541

0,628306

1,993068

1,908325

2,010337

 

24

16.777.216

12.540.349

1.948.488

10.591.861

0,747463

0,116139

0,631324

1,993642

1,911112

2,009607

 

25

33.554.432

25.004.583

3.737.250

21.267.333

0,745195

0,111379

0,633816

1,993930

1,918026

2,007894

 

26

67.108.864

49.869.735

7.174.585

42.695.150

0,743117

0,106910

0,636207

1,994424

1,919750

2,007546

 

27

134.217.728

99.481.971

13.795.167

85.686.804

0,741198

0,102782

0,638416

1,994837

1,922783

2,006945

 

28

268.435.456

198.492.861

26.560.180

171.932.681

0,739444

0,098944

0,640499

1,995265

1,925325

2,006525

 

29

536.870.912

396.098.536

51.221.836

344.876.700

0,737791

0,095408

0,642383

1,995530

1,928520

2,005882

 

30

1.073.741.824

790.540.524

98.900.070

691.640.454

0,736248

0,092108

0,644140

1,995818

1,930819

2,005472

 

31

2.147.483.648

1.578.008.402

191.194.071

1.386.814.331

0,734817

0,089032

0,645786

1,996113

1,933205

2,005109

 

32

4.294.967.296

3.150.256.547

370.016.238

2.780.240.309

0,733476

0,086151

0,647325

1,996350

1,935291

2,004768

 

33

8.589.934.592

6.289.736.836

716.818.946

5.572.917.890

0,732222

0,083449

0,648773

1,996579

1,937263

2,004473

 

34

17.179.869.184

12.559.184.251

1.390.087.477

11.169.096.774

0,731041

0,080914

0,650127

1,996774

1,939245

2,004174

 

35

34.359.738.368

25.080.235.460

2.698.149.317

22.382.086.143

0,729931

0,078526

0,651404

1,996964

1,940992

2,003930

 

36

68.719.476.736

50.088.477.866

5.241.732.604

44.846.745.262

0,728883

0,076277

0,652606

1,997129

1,942714

2,003689

 

37

137.438.953.472

100.041.078.738

10.191.540.564

89.849.538.174

0,727895

0,074153

0,653741

1,997287

1,944308

2,003480

 

38

274.877.906.944

199.824.969.996

19.831.109.798

179.993.860.198

0,726959

0,072145

0,654814

1,997429

1,945840

2,003281

 

39

549.755.813.888

399.162.730.752

38.616.670.706

360.546.060.046

0,726073

0,070243

0,655829

1,997562

1,947277

2,003102

 

40

1.099.511.627.776

797.400.601.203

75.249.390.723

722.151.210.480

0,725232

0,068439

0,656793

1,997683

1,948625

2,002937

 

           

 

           

 

            
            


4. b) Graphics of the distribution of the primes


Legend of the graphic:

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 2^40



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


A B C 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 0 3 0,0000
3 8 0 6 0,0000
4 16 3 10 0,3000
5 32 10 17 0,5882
6 64 20 34 0,5882
7 128 51 55 0,9273
8 256 113 99 1,1414
9 512 242 178 1,3596
10 1.024 526 309 1,7023
11 2.048 1.111 545 2,0385
12 4.096 2.293 1.002 2,2884
13 8.192 4.674 1.838 2,5430
14 16.384 9.513 3.376 2,8178
15 32.768 19.293 6.294 3,0653
16 65.536 39.086 11.743 3,3285
17 131.072 79.053 21.965 3,5990
18 262.144 159.517 41.386 3,8544
19 524.288 321.401 78.131 4,1136
20 1.048.576 648.085 147.640 4,3896
21 2.097.152 1.303.611 280.678 4,6445
22 4.194.304 2.621.756 534.268 4,9072
23 8.388.608 5.270.614 1.019.557 5,1695
24 16.777.216 10.591.861 1.948.488 5,4359
25 33.554.432 21.267.333 3.737.250 5,6906
26 67.108.864 42.695.150 7.174.585 5,9509
27 134.217.728 85.686.804 13.795.167 6,2114
28 268.435.456 171.932.681 26.560.180 6,4733
29 536.870.912 344.876.700 51.221.836 6,7330
30 1.073.741.824 691.640.454 98.900.070 6,9933
31 2.147.483.648 1.386.814.331 191.194.071 7,2534
32 4.294.967.296 2.780.240.309 370.016.238 7,5138
33 8.589.934.592 5.572.917.890 716.818.946 7,7745
34 17.179.869.184 11.169.096.774 1.390.087.477 8,0348
35 34.359.738.368 22.382.086.143 2.698.149.317 8,2953
36 68.719.476.736 44.846.745.262 5.241.732.604 8,5557
37 137.438.953.472 89.849.538.174 10.191.540.564 8,8161
38 274.877.906.944 179.993.860.198 19.831.109.798 9,0763
39 549.755.813.888 360.546.060.046 38.616.670.706 9,3365
40 1.099.511.627.776 722.151.210.480 75.249.390.723 9,5968

The following graphic shows the quotient of primes P(x) | 2x2-1 (E) and the primes P(x)=2x2-1. (D)


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
121100001
243211002
386422004
41610735005
532171168009
664342311150019
7128553817270028
8256996930470052
951217811959870091
101.02430920510415100158
112.04854536518026600279
124.0961.00267133149300509
138.1921.8381.23860090800930
1416.3843.3762.2761.1001.700001.676
1532.7686.2944.2002.0943.178003.116
1665.53611.7437.8153.9285.934005.809
17131.07221.96514.6077.35811.0340010.931
18262.14441.38627.54713.83920.7370020.649
19524.28878.13152.05026.08139.0840039.047
201.048.576147.64098.44449.19674.0100073.630
212.097.152280.678187.05093.628140.50800140.170
224.194.304534.268356.375177.893267.44200266.826
238.388.6081.019.557679.751339.806509.92300509.634
2416.777.2161.948.4881.298.941649.547974.27600974.212
2533.554.4323.737.2502.491.8731.245.3771.867.968001.869.282
2667.108.8647.174.5854.783.2302.391.3553.587.055003.587.530
27134.217.72813.795.1679.196.7224.598.4456.897.153006.898.014
28268.435.45626.560.18017.707.0738.853.10713.279.0140013.281.166
29536.870.91251.221.83634.147.77717.074.05925.610.6360025.611.200
301.073.741.82498.900.07065.935.45632.964.61449.450.2940049.449.776
312.147.483.648191.194.071127.467.80263.726.26995.604.0770095.589.994
324.294.967.296370.016.238246.687.629123.328.609185.013.89900185.002.339
338.589.934.592716.818.945477.883.711238.935.234358.408.10500358.410.840
3417.179.869.1841.390.087.474926.722.654463.364.820695.041.86200695.045.612
3534.359.738.3682.698.149.3091.798.752.890899.396.4191.349.055.174001.349.094.135
3668.719.476.7365.241.732.5883.494.472.9001.747.259.6882.620.827.449002.620.905.139

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
380000000
4163122001
53210466004
66420101090011
7128512229250026
82561135756510062
951224212611611400128
101.02452626326325400272
112.0481.11155455754200569
124.0962.2931.1541.1391.126001.167
138.1924.6742.3222.3522.322002.352
1416.3849.5134.7664.7474.731004.782
1532.76819.2939.6979.5969.625009.668
1665.53639.08619.74219.34419.5700019.516
17131.07279.05339.86739.18639.5520039.501
18262.144159.51780.25679.26179.8810079.636
19524.288321.401161.974159.427160.76200160.639
201.048.576648.085325.951322.134324.05200324.033
212.097.1521.303.611656.016647.595651.79500651.816
224.194.3042.621.7561.318.9571.302.7991.310.943001.310.813
238.388.6085.270.6142.649.2392.621.3752.634.688002.635.926
2416.777.21610.591.8615.324.0065.267.8555.294.606005.297.255
2533.554.43221.267.33310.688.72810.578.60510.631.1800010.636.153
2667.108.86442.695.15021.456.67921.238.47121.343.0580021.352.092
27134.217.72885.686.80443.051.83142.634.97342.835.5740042.851.230
28268.435.456171.932.68186.380.59885.552.08385.954.5300085.978.151
29536.870.912344.876.700173.231.122171.645.578172.426.84700172.449.853
301.073.741.824691.640.454347.362.799344.277.655345.816.07700345.824.377
312.147.483.6481.386.814.331696.393.313690.421.018693.400.82200693.413.509
324.294.967.2962.780.240.3091.395.928.7681.384.311.5411.390.103.047001.390.137.262
338.589.934.5925.572.917.8902.797.724.9312.775.192.9592.786.432.732002.786.485.158
3417.179.869.18411.169.096.7745.606.454.5415.562.642.2335.584.509.062005.584.587.712
3534.359.738.36822.382.086.13811.233.651.88311.148.434.25511.191.044.2540011.191.041.884
3668.719.476.73644.846.745.24122.506.291.10922.340.454.13222.423.359.8930022.423.385.348

4. e) Primes (red marked) which could not be a factor of any Mersenne number



jac () means the jacobi function.

f(0) = 1 = 1
f(1) = 1 = 1
f(2) = 7 = 7 jac (2, 7)=1 jac (5, 7)=-1 6 = 2 3
f(3) = 17 = 17 jac (3, 17)=-1 jac (14, 17)=-1 16 = 2
f(4) = 31 = 31 jac (4, 31)=1 jac (27, 31)=-1 30 = 2 3 5
f(5) = 49 = 7*7 jac (5, 7)=-1 jac (2, 7)=1 6 = 2 3
f(6) = 71 = 71 jac (6, 71)=1 jac (65, 71)=-1 70 = 2 5 7
f(7) = 97 = 97 jac (7, 97)=-1 jac (90, 97)=-1 96 = 2 3
f(8) = 127 = 127 jac (8, 127)=1 jac (119, 127)=-1 126 = 2 3 7
f(9) = 161 = 7*23 jac (9, 23)=1 jac (14, 23)=-1 22 = 2 11
f(10) = 199 = 199 jac (10, 199)=1 jac (189, 199)=-1 198 = 2 3 11
f(11) = 241 = 241 jac (11, 241)=-1 jac (230, 241)=-1 240 = 2 3 5
f(12) = 287 = 7*41 jac (12, 41)=-1 jac (29, 41)=-1 40 = 2 5
f(13) = 337 = 337 jac (13, 337)=1 jac (324, 337)=1 336 = 2 3 7
f(14) = 391 = 17*23 jac (14, 23)=-1 jac (9, 23)=1 22 = 2 11
f(15) = 449 = 449 jac (15, 449)=-1 jac (434, 449)=-1 448 = 2 7
f(16) = 511 = 7*73 jac (16, 73)=1 jac (57, 73)=1 72 = 2 3
f(17) = 577 = 577 jac (17, 577)=1 jac (560, 577)=1 576 = 2 3
f(18) = 647 = 647 jac (18, 647)=1 jac (629, 647)=-1 646 = 2 17 19
f(19) = 721 = 7*103 jac (19, 103)=1 jac (84, 103)=-1 102 = 2 3 17
f(20) = 799 = 17*47 jac (20, 47)=-1 jac (27, 47)=1 46 = 2 23
f(21) = 881 = 881 jac (21, 881)=1 jac (860, 881)=1 880 = 2 5 11
f(22) = 967 = 967 jac (22, 967)=1 jac (945, 967)=-1 966 = 2 3 7 23
f(23) = 1057 = 7*151 jac (23, 151)=-1 jac (128, 151)=1 150 = 2 3 5
f(24) = 1151 = 1151 jac (24, 1151)=1 jac (1127, 1151)=-1 1150 = 2 5 23
f(25) = 1249 = 1249 jac (25, 1249)=1 jac (1224, 1249)=1 1248 = 2 3 13
f(26) = 1351 = 7*193 jac (26, 193)=-1 jac (167, 193)=-1 192 = 2 3
f(27) = 1457 = 31*47 jac (27, 47)=1 jac (20, 47)=-1 46 = 2 23
f(28) = 1567 = 1567 jac (28, 1567)=1 jac (1539, 1567)=-1 1566 = 2 3 29
f(29) = 1681 = 41*41 jac (29, 41)=-1 jac (12, 41)=-1 40 = 2 5
f(30) = 1799 = 7*257 jac (30, 257)=1 jac (227, 257)=1 256 = 2
f(31) = 1921 = 17*113 jac (31, 113)=1 jac (82, 113)=1 112 = 2 7
f(32) = 2047 = 23*89 jac (32, 89)=1 jac (57, 89)=1 88 = 2 11
f(33) = 2177 = 7*311 jac (33, 311)=-1 jac (278, 311)=1 310 = 2 5 31
f(34) = 2311 = 2311 jac (34, 2311)=1 jac (2277, 2311)=-1 2310 = 2 3 5 7 11
f(35) = 2449 = 31*79 jac (35, 79)=-1 jac (44, 79)=1 78 = 2 3 13
f(36) = 2591 = 2591 jac (36, 2591)=1 jac (2555, 2591)=-1 2590 = 2 5 7 37
f(37) = 2737 = 7*17*23 jac (37, 23)=-1 jac (-14, 23)=1 22 = 2 11
f(38) = 2887 = 2887 jac (38, 2887)=1 jac (2849, 2887)=-1 2886 = 2 3 13 37
f(39) = 3041 = 3041 jac (39, 3041)=-1 jac (3002, 3041)=-1 3040 = 2 5 19
f(40) = 3199 = 7*457 jac (40, 457)=-1 jac (417, 457)=-1 456 = 2 3 19
f(41) = 3361 = 3361 jac (41, 3361)=1 jac (3320, 3361)=1 3360 = 2 3 5 7
f(42) = 3527 = 3527 jac (42, 3527)=1 jac (3485, 3527)=-1 3526 = 2 41 43
f(43) = 3697 = 3697 jac (43, 3697)=-1 jac (3654, 3697)=-1 3696 = 2 3 7 11
f(44) = 3871 = 7*7*79 jac (44, 79)=1 jac (35, 79)=-1 78 = 2 3 13
f(45) = 4049 = 4049 jac (45, 4049)=1 jac (4004, 4049)=1 4048 = 2 11 23
f(46) = 4231 = 4231 jac (46, 4231)=1 jac (4185, 4231)=-1 4230 = 2 3 5 47
f(47) = 4417 = 7*631 jac (47, 631)=1 jac (584, 631)=-1 630 = 2 3 5 7
f(48) = 4607 = 17*271 jac (48, 271)=-1 jac (223, 271)=1 270 = 2 3 5
f(49) = 4801 = 4801 jac (49, 4801)=1 jac (4752, 4801)=1 4800 = 2 3 5
f(50) = 4999 = 4999 jac (50, 4999)=1 jac (4949, 4999)=-1 4998 = 2 3 7 17
f(51) = 5201 = 7*743 jac (51, 743)=-1 jac (692, 743)=1 742 = 2 7 53
f(52) = 5407 = 5407 jac (52, 5407)=1 jac (5355, 5407)=-1 5406 = 2 3 17 53
f(53) = 5617 = 41*137 jac (53, 137)=-1 jac (84, 137)=-1 136 = 2 17
f(54) = 5831 = 7*7*7*17 jac (54, 17)=-1 jac (-37, 17)=-1 16 = 2
f(55) = 6049 = 23*263 jac (55, 263)=-1 jac (208, 263)=1 262 = 2 131
f(56) = 6271 = 6271 jac (56, 6271)=1 jac (6215, 6271)=-1 6270 = 2 3 5 11 19
f(57) = 6497 = 73*89 jac (57, 89)=1 jac (32, 89)=1 88 = 2 11
f(58) = 6727 = 7*31*31 jac (58, 31)=-1 jac (-27, 31)=1 30 = 2 3 5
f(59) = 6961 = 6961 jac (59, 6961)=-1 jac (6902, 6961)=-1 6960 = 2 3 5 29
f(60) = 7199 = 23*313 jac (60, 313)=-1 jac (253, 313)=-1 312 = 2 3 13
f(61) = 7441 = 7*1063 jac (61, 1063)=-1 jac (1002, 1063)=1 1062 = 2 3 59
f(62) = 7687 = 7687 jac (62, 7687)=1 jac (7625, 7687)=-1 7686 = 2 3 7 61
f(63) = 7937 = 7937 jac (63, 7937)=-1 jac (7874, 7937)=-1 7936 = 2 31
f(64) = 8191 = 8191 jac (64, 8191)=1 jac (8127, 8191)=-1 8190 = 2 3 5 7 13
f(65) = 8449 = 7*17*71 jac (65, 71)=-1 jac (6, 71)=1 70 = 2 5 7
f(66) = 8711 = 31*281 jac (66, 281)=1 jac (215, 281)=1 280 = 2 5 7
f(67) = 8977 = 47*191 jac (67, 191)=1 jac (124, 191)=-1 190 = 2 5 19
f(68) = 9247 = 7*1321 jac (68, 1321)=-1 jac (1253, 1321)=-1 1320 = 2 3 5 11
f(69) = 9521 = 9521 jac (69, 9521)=1 jac (9452, 9521)=1 9520 = 2 5 7 17
f(70) = 9799 = 41*239 jac (70, 239)=-1 jac (169, 239)=1 238 = 2 7 17
f(71) = 10081 = 17*593 jac (71, 593)=1 jac (522, 593)=1 592 = 2 37
f(72) = 10367 = 7*1481 jac (72, 1481)=1 jac (1409, 1481)=1 1480 = 2 5 37
f(73) = 10657 = 10657 jac (73, 10657)=1 jac (10584, 10657)=1 10656 = 2 3 37
f(74) = 10951 = 47*233 jac (74, 233)=1 jac (159, 233)=1 232 = 2 29
f(75) = 11249 = 7*1607 jac (75, 1607)=1 jac (1532, 1607)=-1 1606 = 2 11 73
f(76) = 11551 = 11551 jac (76, 11551)=1 jac (11475, 11551)=-1 11550 = 2 3 5 7 11
f(77) = 11857 = 71*167 jac (77, 167)=1 jac (90, 167)=-1 166 = 2 83
f(78) = 12167 = 23*23*23 jac (78, 23)=1 jac (-55, 23)=-1 22 = 2 11
f(79) = 12481 = 7*1783 jac (79, 1783)=-1 jac (1704, 1783)=1 1782 = 2 3 11
f(80) = 12799 = 12799 jac (80, 12799)=1 jac (12719, 12799)=-1 12798 = 2 3 79
f(81) = 13121 = 13121 jac (81, 13121)=1 jac (13040, 13121)=1 13120 = 2 5 41
f(82) = 13447 = 7*17*113 jac (82, 113)=1 jac (31, 113)=1 112 = 2 7
f(83) = 13777 = 23*599 jac (83, 599)=1 jac (516, 599)=-1 598 = 2 13 23
f(84) = 14111 = 103*137 jac (84, 137)=-1 jac (53, 137)=-1 136 = 2 17
f(85) = 14449 = 14449 jac (85, 14449)=1 jac (14364, 14449)=1 14448 = 2 3 7 43
f(86) = 14791 = 7*2113 jac (86, 2113)=1 jac (2027, 2113)=1 2112 = 2 3 11
f(87) = 15137 = 15137 jac (87, 15137)=-1 jac (15050, 15137)=-1 15136 = 2 11 43
f(88) = 15487 = 17*911 jac (88, 911)=-1 jac (823, 911)=1 910 = 2 5 7 13
f(89) = 15841 = 7*31*73 jac (89, 73)=1 jac (-16, 73)=1 72 = 2 3
f(90) = 16199 = 97*167 jac (90, 167)=-1 jac (77, 167)=1 166 = 2 83
f(91) = 16561 = 16561 jac (91, 16561)=-1 jac (16470, 16561)=-1 16560 = 2 3 5 23
f(92) = 16927 = 16927 jac (92, 16927)=1 jac (16835, 16927)=-1 16926 = 2 3 7 13 31
f(93) = 17297 = 7*7*353 jac (93, 353)=1 jac (260, 353)=1 352 = 2 11
f(94) = 17671 = 41*431 jac (94, 431)=-1 jac (337, 431)=1 430 = 2 5 43
f(95) = 18049 = 18049 jac (95, 18049)=-1 jac (17954, 18049)=-1 18048 = 2 3 47
f(96) = 18431 = 7*2633 jac (96, 2633)=-1 jac (2537, 2633)=-1 2632 = 2 7 47
f(97) = 18817 = 31*607 jac (97, 607)=1 jac (510, 607)=-1 606 = 2 3 101
f(98) = 19207 = 19207 jac (98, 19207)=1 jac (19109, 19207)=-1 19206 = 2 3 11 97
f(99) = 19601 = 17*1153 jac (99, 1153)=1 jac (1054, 1153)=1 1152 = 2 3
f(100) = 19999 = 7*2857 jac (100, 2857)=1 jac (2757, 2857)=1 2856 = 2 3 7 17

4. f) Graphic of the distribution of the sieved out primes


The x-axis shows the potence of 2, the y axis shows the amount of sieved out primes.
Sieving was done up to 238, the sieved out primes go to 277.



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. f) unsorted list of primes with 1 for n<100:


1,7,17,31,1,71,97,127,23,199,241,41,337,1,449,73,577,647,103,47,881,967,151,1151,1249,
193,1,1567,1,257,113,89,311,2311,79,2591,1,2887,3041,457,3361,3527,3697,1,4049,4231,631,
271,4801,4999,743,5407,137,1,263,6271,1,1,6961,313,1063,7687,7937,8191,1,281,191,1321,9521,
239,593,1481,10657,233,1607,11551,167,1,1783,12799,13121,1,599,1,14449,2113,15137,911,1,1,16561,
16927,353,431,18049,2633,607,19207,1153

6. g) unsorted list of primes with adjoined square root for n<100


x = 2 prim = 7 = (2 √2+ 1) * (2 √2- 1) =  8 - 1

x = 3 prim = 17 = (3 √2+ 1) * (3 √2- 1) =  18 - 1

x = 4 prim = 31 = (4 √2+ 1) * (4 √2- 1) =  32 - 1

x = 6 prim = 71 = (6 √2+ 1) * (6 √2- 1) =  72 - 1

x = 7 prim = 97 = (7 √2+ 1) * (7 √2- 1) =  98 - 1

x = 8 prim = 127 = (8 √2+ 1) * (8 √2- 1) =  128 - 1

x = 9 prim = 23 = (5 + √2) * (5 - √2) =  25 - 2

x = 10 prim = 199 = (10 √2+ 1) * (10 √2- 1) =  200 - 1

x = 11 prim = 241 = (11 √2+ 1) * (11 √2- 1) =  242 - 1

x = 12 prim = 41 = (7 + 2 √2) * (7 - 2 √2) =  49 - 8

x = 13 prim = 337 = (13 √2+ 1) * (13 √2- 1) =  338 - 1

x = 15 prim = 449 = (15 √2+ 1) * (15 √2- 1) =  450 - 1

x = 16 prim = 73 = (9 + 2 √2) * (9 - 2 √2) =  81 - 8

x = 17 prim = 577 = (17 √2+ 1) * (17 √2- 1) =  578 - 1

x = 18 prim = 647 = (18 √2+ 1) * (18 √2- 1) =  648 - 1

x = 19 prim = 103 = (11 + 3 √2) * (11 - 3 √2) =  121 - 18

x = 20 prim = 47 = (7 + √2) * (7 - √2) =  49 - 2

x = 21 prim = 881 = (21 √2+ 1) * (21 √2- 1) =  882 - 1

x = 22 prim = 967 = (22 √2+ 1) * (22 √2- 1) =  968 - 1

x = 23 prim = 151 = (13 + 3 √2) * (13 - 3 √2) =  169 - 18

x = 24 prim = 1151 = (24 √2+ 1) * (24 √2- 1) =  1152 - 1

x = 25 prim = 1249 = (25 √2+ 1) * (25 √2- 1) =  1250 - 1

x = 26 prim = 193 = (15 + 4 √2) * (15 - 4 √2) =  225 - 32

x = 28 prim = 1567 = (28 √2+ 1) * (28 √2- 1) =  1568 - 1

x = 30 prim = 257 = (17 + 4 √2) * (17 - 4 √2) =  289 - 32

x = 31 prim = 113 = (11 + 2 √2) * (11 - 2 √2) =  121 - 8

x = 32 prim = 89 = (7 √2+ 3 1) * (7 √2- 3 1) =  98 - 9

x = 33 prim = 311 = (19 + 5 √2) * (19 - 5 √2) =  361 - 50

x = 34 prim = 2311 = (34 √2+ 1) * (34 √2- 1) =  2312 - 1

x = 35 prim = 79 = (9 + √2) * (9 - √2) =  81 - 2

x = 36 prim = 2591 = (36 √2+ 1) * (36 √2- 1) =  2592 - 1

x = 38 prim = 2887 = (38 √2+ 1) * (38 √2- 1) =  2888 - 1

x = 39 prim = 3041 = (39 √2+ 1) * (39 √2- 1) =  3042 - 1

x = 40 prim = 457 = (23 + 6 √2) * (23 - 6 √2) =  529 - 72

x = 41 prim = 3361 = (41 √2+ 1) * (41 √2- 1) =  3362 - 1

x = 42 prim = 3527 = (42 √2+ 1) * (42 √2- 1) =  3528 - 1

x = 43 prim = 3697 = (43 √2+ 1) * (43 √2- 1) =  3698 - 1

x = 45 prim = 4049 = (45 √2+ 1) * (45 √2- 1) =  4050 - 1

x = 46 prim = 4231 = (46 √2+ 1) * (46 √2- 1) =  4232 - 1

x = 47 prim = 631 = (27 + 7 √2) * (27 - 7 √2) =  729 - 98

x = 48 prim = 271 = (17 + 3 √2) * (17 - 3 √2) =  289 - 18

x = 49 prim = 4801 = (49 √2+ 1) * (49 √2- 1) =  4802 - 1

x = 50 prim = 4999 = (50 √2+ 1) * (50 √2- 1) =  5000 - 1

x = 51 prim = 743 = (29 + 7√2) * (29 - 7√2) =  841 - 98

x = 52 prim = 5407 = (52 √2+ 1) * (52 √2- 1) =  5408 - 1

x = 53 prim = 137 = (9 √2+ 5) * (9 √2- 5) =  162 - 25

x = 55 prim = 263 = (12 √2+ 5) * (12 √2- 5) =  288 - 25

x = 56 prim = 6271 = (56 √2+ 1) * (56 √2- 1) =  6272 - 1

x = 59 prim = 6961 = (59 √2+ 1) * (59 √2- 1) =  6962 - 1

x = 60 prim = 313 = (13 √2+ 5) * (13 √2- 5) =  338 - 25

x = 61 prim = 1063 = (35 + 9 √2) * (35 - 9 √2) =  1225 - 162

x = 62 prim = 7687 = (62 √2+ 1) * (62 √2- 1) =  7688 - 1

x = 63 prim = 7937 = (63 √2+ 1) * (63 √2- 1) =  7938 - 1

x = 64 prim = 8191 = (64 √2+ 1) * (64 √2- 1) =  8192 - 1

x = 66 prim = 281 = (17 + 2 √2) * (17 - 2 √2) =  289 - 8

x = 67 prim = 191 = (10 √2+ 3 1) * (10 √2- 3 1) =  200 - 9

x = 68 prim = 1321 = (39 + 10 √2) * (39 - 10 √2) =  1521 - 200

x = 69 prim = 9521 = (69 √2+ 1) * (69 √2- 1) =  9522 - 1

x = 70 prim = 239 = (12 √2+ 7) * (12 √2- 7) =  288 - 49

x = 71 prim = 593 = (25 + 4 √2) * (25 - 4 √2) =  625 - 32

x = 72 prim = 1481 = (41 + 10 √2) * (41 - 10 √2) =  1681 - 200

x = 73 prim = 10657 = (73 √2 + 1) * (73 √2 - 1) =  10658 - 1

x = 74 prim = 233 = (11 √2+ 3) * (11 √2-  3) =  242 - 9

x = 75 prim = 1607 = (43 + 11 √2) * (43 - 11 √2) =  1849 - 242

x = 76 prim = 11551 = (76 √2+ 1) * (76 √2 - 1) =  11552 - 1

x = 77 prim = 167 = (13 + √2) * (13 - √2) =  169 - 2

x = 79 prim = 1783 = (45 + 11 √2) * (45 - 11 √2) =  2025 - 242

x = 80 prim = 12799 = (80 √2 + 1) * (80 √2 - 1) =  12800 - 1

x = 81 prim = 13121 = (81 √2 + 1) * (81 √2 - 1) =  13122 - 1

x = 83 prim = 599 = (18 √2+ 7) * (18 √2- 7) =  648 - 49

x = 85 prim = 14449 = (85 √2+ 1) * (85 √2 - 1) =  14450 - 1

x = 86 prim = 2113 = (49 + 12 √2) * (49 - 12 √2) =  2401 - 288

x = 87 prim = 15137 = (87 √2 + 1) * (87 √2 - 1) =  15138 - 1

x = 88 prim = 911 = (31 + 5 √2) * (31 - 5 √2) =  961 - 50

x = 91 prim = 16561 = (91 √2 + 1) * (91 √2 - 1) =  16562 - 1

x = 92 prim = 16927 = (92 √2 + 1) * (92 √2 - 1) =  16928 - 1

x = 93 prim = 353 = (17 √2 + 15) * (17 √2 -15) =  578 - 225

x = 94 prim = 431 = (16 √2 + 9) * (16 √2 - 9) =  512 - 81

x = 95 prim = 18049 = (95 √2 + 1) * (95 √2 - 1) =  18050 - 1

x = 96 prim = 2633 = (55 + 14 √2) * (55 - 14 √2) =  3025 - 392

x = 97 prim = 607 = (25 + 3 √2) * (25 - 3 √2) =  625 - 18

x = 98 prim = 19207 = (98 √2 + 1) * (98 √2 - 1) =  19208 - 1

x = 99 prim = 1153 = (35 + 6 √2) * (35 - 6 √2) =  1225 - 72