A co-ordinated search for primes in the Payam number series


The lowest k values for which there are no low e prime factors in the series k*2^n +/- 1 are rather special, and that is what these pages are all about. Why are they special? Well, OK, they are not so special to be given a name, but I will call them Payam numbers, after Payam Samidoost, who sent me some correspondence on this. That makes them special now.

Actually we might expect the series k*2^n + or – 1 would produce more prime numbers when k is a Payam number because many of the common factors (our “low e” factors), which eliminate many values of n when factoring the numbers produced in the series, cannot be factors, by definition.

Look at the following for k = 75075, which is the smallest k for which there are no factors in the series k*2^n+1 with e less than 17 (if you want the whole list, the factors which do not exist in this series are 3,7,5,31,127,17,73,11, 23,89,13,8191,43,151, 257, and 131071, in order of their e values. If you want an even fuller list of low e numbers work them out from here. (actually you need all of the low numbers, including the evens.)

Factors of 75075*2^n+1
n
75075*2^n+1
Factors
1
150151
Prime!
2
300301
Prime!!
3
600601
Prime!!! Turkey!!!
4
1201201
Prime!!!! 4 in a row!!
5
2402401
Prime!!!!! 5 in a row!!
6
4804801
523*9187 Oh, the disappointment!
7
9609601
Prime! That's better!
8
19219201
41*468761 Mmmmmmm
9
38438401
43*87559 Heeeey!
10
76876801
Prime YESSSSSS!!!
11
153753601
7229*21269 Oh, well..

OK, so not every series is going to be so spectacular, but there is no doubt that these series are rich in primes, see to the results page! You might also know about Cunningham chains, and a 5 chain is always worthwhile.

So what are the Payam numbers? They are a bit difficult to calculate because they are the smallest k values with this series.

I approached the problem using good old bloody Bill's Excel. Whilst this is not the easiest programme to use with exact numbers, Torbjorn Alm pointed me in the direction of a deadly useful add in, zzmath, and this allowed me further exploration.

To do this, I noticed that primes seem to form into three groups depending on their modular behaviour when dividing the k*2^n+/-1 series:

1. Those which seem to divide almost all k*2^n+/-1 values, for any n up to their e value

2. Those which divide about 50% of k*2^n+/-1 in similar circumstances

3. Those which rarely divide k*2^n+/-1

Examples of this:

1. This series of primes, p, are quickly seen to have e=p-1 The first few examples of these are 3,5,11,13,19,29,37,53,83.....

2. This series of primes have e=(p-1)/2 The first few examples of these are 7,17,23,41,47,71,79…

3. These have e much smaller than p, and examples of this are 31,43,73,89,127,151…., mathematically those which have (p-1)/d when d>2 , d|(p-1). (thanks to Phil Carmody for this)

Payam's observation can be restated:

for any given value of e, the most efficient values of k , for which no primes with e smaller than the given value, are multiples of all of the p in the first group with e less than the given value (M), multiplied by the first odd number for which all primes with e smaller than the target (X) do not divide any number in the series (S) = k*2+/-1 up to k*2^e+/-1

M*X=S

To find these k is a matter of trial and error, looking at odd numbers starting at 1, up to X, and multiplying by M, and finding if any of the primes divide any of the series S.

A totally efficient programme will look at all possibilities, but it is possible to arrive at possible values for k just by looking at the second class of numbers, and if a k passes this test, then testing it on the whole set of primes. this is what I did to find the numbers.

I sweated blood and guts to calculate the first few Payam numbers for the k*2^n-1 series and I got some of them wrong. Payam produced a small program, in Maple, to calculate the values. Maybe someone can run it in PARI?

Here is what we have managed so far:

Payam numbers
e
k*2^n+1
k*2^n-1
2
3
3
3
9=3*3
3
4
15=3*5
45=3*3*5
5 to 9
105=3*5*7
45
10
165=3*5*11
2145=3*5*11*13
11
165
2805=3*5*11*17
12 to 17
75075
92235
18 and 19
855855
529815
20 to 22
5583435
529815
23 to 25
18625035
529815
26 and 27
1862035
1426425
28 to 34
27183585
247016055
35
1684200375
247016055
36
1684200375
74297465385
37 to 38
1684200375
77271113205
39 to 49
198840832905
191844014505
50
305892154425
191844014505
51 to 66
532326689895
246419198025
67
139592518105755
169680848811045

The results of the series, when run to quite high values of n, are producing some good prime counts. Right now they do not compare quite with the best results in the Primoproth search, or the most prime k but when we define higher Payam numbers I think we will be right up there.

Stop Press! A derivative of these numbers has just beaten the record for most prime series of the form k*2^n-1. I found it whilst searching for these numbers, and, whilst not the most efficient has already produced 102 primes for the first 25,000 n.

So, if you want to join in the hunt, or help to define the next Payam numbers, then sign up. Write to me at 100620.2351@compuserve.com and I will reserve you a range. For ranges reserved already see this.

There are ways to speed up your search. Firstly, there is a possibility to sieve the k's in k*2^n+/- 1. The latest beta version of Paul Jobling's NewPGen software, version 2.71 is available, in which Paul has kindly allowed sieving of Payam numbers to take place. Simply enter the Payam number in the form of its factors, for example enter 855855 as 3*5*5*7*11*13 in the k box, select the form k*2^n+ or – 1, with k constant, select 2 as the base, enter a file name to save, and bingo! Watch those n values melt away. At the right time, run pfgw on the numbers remaining, and see those primes roll through! It is so satisfying. Finally you should check that they are primes either in pfgw or proth and then send the results to me.

Continue

Back

Address questions about this web page to: Robert Smith

Last updated 9 November 2002