- Hi

Paul Leyland askedme the other day about 4^n-3. As far as I know the

biggest "ordinary prime" (whatever that is) is 4^7057-3 proven by

Preda Milhailescu.

I am intersted in these because I have never found a composite of

the form F:2^N-2^k-1 for which F|2^F-2. In the above case k=1 and

n=2N.

Modular reducton of a 2N bit number is particularly easy since

2^N=2+1 and hence requires just two shifts and additions. Moreover to

test F we could check 2^(2^N)=8 modulo F i.e take N (FFT) squarings

of 2, use the simple modular reduction, and finally check to see if

this equals 8.

I checked an old email file to the old utm list server for back on

the 3rd May 1999.I wrote:

>4^n-3 is proven prime. n:

2

3

5

7

10

11

12

47

58

61

75

87

133

168

226

347

425

868

1977

2815

3378

4385

5286

7057

4^n-3 not proven prime. n:

720

8230

8340

13175

17226

I also tested 4^n+3:

1

2

3

6

8

9

14

15

42

114

195

392

555

852

1004

1185

2001

2030

2031

2276

8610

8967

10362

11366

15927

16514

In both case I tested to n=17400. You might want to check these are

PRP. Do I qualify for Henri's PRP list with any of these?

Tony Forbes concurred with me that these were the only such numbers

upto some maximum I forget.

Chris Nash attemted factorisation of some of these numbers for BHS

test. I guese he got lucky with 7057 and Preda was able to finish the

job with his "cycloprove" program.

I hope this helps. Don't forget to check the PRPs.

Paul - --- In primenumbers@y..., paulunderwood@m... wrote:
> Hi

Especially the 4^720-3 number ;) Might you mean 4^7200-3 instead?

>

>Paul Leyland askedme the other day about 4^n-3. As far as I know the

> ...

>4^n-3 not proven prime. n:

>720

> ...

>In both case I tested to n=17400. You might want to check these are

>PRP.

Jim. > Paul Leyland askedme the other day about 4^n-3. As far as I know the

Indeed, as I am toying with the idea of searching for further examples

> biggest "ordinary prime" (whatever that is) is 4^7057-3 proven by

> Preda Milhailescu.

and putting up a web page to coordinate the search, should anyone else

be interested in joining in. However, pressure of other work means that

it won't happen in the immediate future 8-(

> I am intersted in these because I have never found a composite of

[Lists deleted.]

> the form F:2^N-2^k-1 for which F|2^F-2. In the above case k=1 and

> n=2N.

>

> Modular reducton of a 2N bit number is particularly easy since

> 2^N=2+1 and hence requires just two shifts and additions. Moreover to

> test F we could check 2^(2^N)=8 modulo F i.e take N (FFT) squarings

> of 2, use the simple modular reduction, and finally check to see if

> this equals 8.

>

> I checked an old email file to the old utm list server for back on

> the 3rd May 1999.I wrote:

>

> >4^n-3 is proven prime. n:

Thanks Paul! This will help populate the web page, and also gives a few

nice test cases to pick up really stupid bugs.

Paul