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.)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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.
Address questions about this web page to: Robert
Smith
Last updated 9 November 2002