Proth numbers are numbers of the form
k*2^{n}+1
and for drag racing purposes you fix k, and vary only n, i.e.
f_{k}(n)=k*2^{n}+1
where n>0. Riesel numbers are similar, but instead have a '-1'
rather than a '+1'. In almost all regards that are important to
drag racing there's very little difference in behaviour between the
two, so I will analyse only Proth numbers as the results can be
generalised to Riesel numbers too. Likewise when I refer to just
"Proth racing" I mean drag racing both Proth form and Riesel
form sequences.

For some more information on early Proth Racing, see Ray Ballinger's suggestion for Prime Puzzle 6 on Carlos Rivera's Prime Puzzles and Problems Connection

One important property of Proth numbers (and, as I say, Riesel
numbers) is that they grow quite quickly due to the exponential
term 2^{n}. This means that prime density (or more strictly its
reciprocal) drops off linearly as you progress along the
sequence. It's a well known fact that the sum of 1/n diverges,
and therefore any sequence that is permitted to have any
non-trivial primes on it at all is expected to have an infinite
number of primes. However, the density of these primes will fall
off quite rapidly, such that you'd expect the same number of
primes between n=100 and n=200 as you would between
n=100000 and n=200000.

Finding primes in the n>100000 region is a slow process, and so
in order to do well at Proth racing, you typically need to get
lots of primes in as quickly as possible. That's why it's a bit
like real drag-racing, it's all about speed, and speed
**now**, not later.

If you choose an arbitrary k value, and look at the smallest factors of the first dozen or so terms, you'll notice some interesting patterns. Certain primes occur quite frequently, other primes don't turn up at all.

k | smallest factors of k*2^{n}+1 for n=1..12 |
---|---|

1 | 3, 5, 3, 17, 3, 5, 3, 257, 3, 5, 3, 17, |

3 | 7, 13, 5, 7, 97, 193, 5, 769, 29, 7, 5, 12289, |

5 | 11, 3, 41, 3, 7, 3, 641, 3, 13, 3, 7, 3, |

7 | 3, 29, 3, 113, 3, 449, 3, 11, 3, 67, 3, 53, |

9 | 19, 37, 73, 5, 17, 577, 1153, 5, 11, 13, 18433, 5, |

11 | 23, 3, 89, 3, 353, 3, 1409, 3, 43, 3, 13, 3, |

13 | 3, 53, 3, 11, 3, 7, 3, 3329, 3, 13313, 3, 7, |

15 | 31, 61, 11, 241, 13, 31, 17, 23, 7681, 15361, 31, 61441, |

Let us first look at occurences of the prime factor 3.
It never appears where k ≡ 0 (mod 3).
This is because 3*k*2^{n}+1 ≡ 1 (mod 3).
However, for all other k values, 3 will appear as a factor of k*2^{n}+1,
for exactly half of the terms. This is because 2^{n} follows the following
sequence modulo 3 : 2,1,2,1,2,1,2... , i.e. it has period 2, and the set
of residues it can reach is all of the non-zero ones. When multiplied by
a k that's not a multiple of 3 again the residues attainable are 1 and 2,
but not 0. And of course when the +1 is added on, the half of them will
become 0 (mod 3), and the other half will become 2 (mod 3). We
immediately see that for k !&equiv 0 (mod 3) the period of 2^{n} (mod 3)
is the same as the period of k*2^{n}+1 (mod 3). This is no coincidence.

Likewise for the prime factor 5, it will appear as a factor of exactly
1/4 of the terms of all sequences where k is not a multiple of 5, and
never in sequences where 5 divides k. Note however, that the 5s are all
hidden in the list of factors for the sequence generated by k=7. That's
because every term that's divisible by 5 is also divisible by 3. Again,
looking at the residues of 2^{n} (mod 5), the pattern 2,4,3,1,2,4,... is
repeated for ever, and so for k not a multiple of 5 all 4 non-zero
residues mod 5 will reached by the k*2^{n}+1, with a period of 4.

Things get more intersting when looking at occurances of the prime
factor 7 in the above terms. As 2^{n} (mod 7) follows the pattern 2,4,1,2,4...
with period three, there are three classes of sequence:

- Those with k ≡ 0 (mod 7) .
For these k*2
^{n}+1 = 7*k'*2^{n}+1 ≡ 1 (mod 7) - Those with k ≡ {1,2,4} (mod 7) .
For these k*2
^{n}+1 ≡ {2,3,5} (mod 7) - Those with k ≡ {3,6,5} (mod 7) .
For these k*2
^{n}+1 ≡ {4,0,6} (mod 7)

The patterns shown above can be found for all potential factors,
not just 3, 5, and 7. You can examine the values attainable by 2^{n}
(mod p), and then apply the general rule:

- If k ≡ 0 (mod p), then no term in k's sequence will be divisible by p.
- Otherwise, if k !≡ 0 (mod p) and C={2
^{n}(mod p)} has (p-1) elements, then each such k's sequence will have 1 in every (p-1) terms divisible by p. - However, if k !≡ 0 (mod p) but C={2
^{n}(mod p)} has <(p-1) elements, then |C| out of (p-1) such k will have 1 out of |C| terms divisible by p, and the other (p-1-|C|) out of (p-1) such k will never have p as a factor.

*Phew!*

What all this means is that some k values generate sequences with lots of small prime factors which will therefore rarely be prime. The flipside is that some sequences will never have small prime factors, and therefore have a much higher probability of containing primes. (Ah, I need to write my page on sieving theory sometime soon... .)

I also have a worked example of what happens when you exclude all primes with periods less than or equal to 12, if the above didn't have enough examples in it.

The extrema of the "lots of small prime factors" case are the Sierpinski
numbers. These have *zero* prime density, as all the small prime
factors contrive to line up next to each other and cover every possible
term in the sequence. Right beside those, but mathematically quite
distinct, are those for which there's no such "covering set" of small
prime factors as a tiny fraction of the possible candidates will not be
hit by the small primes. It's possible to generate sets of small primes
which will miss out arbitrarily small proportions of terms, and therefore
there's no such thing as the smallest non-zero density. However, if you
restrict your region of interest to just those k less than the first known
Sierpinski number, then you've landed squarely in the middle of the
Sierpinksi problem, which I mentioned on the introductory page. As I say,
this is like a holding your breath competition. The longer a k's sequence
can go without generating a prime the more impressive it is. However,
there's no prize for staying under-water for ever, people might think
you're dead!

In the other direction, where we're considering boosting density by
avoiding small prime factors, it can be hard to boost the density by
much without resorting to massive k values. The problem with massive k
values is that it seriously compromises your chances of finding primes
in the smallest terms - basically because the smallest terms aren't
small! There's also a law of diminishing returns - Merten's Law says
that even if we exclude all small primes up to p, then the density boost
would be only ~ln(p) (with some small constant scaling factor). The
form k*2^{n}+1 by construction excludes 2 as a prime factor of any term,
so all such numbers (even the near-zero-density ones) have a factor
of 2 density boost over sequences which don't have 2 excluded as a
factor. It's therefore conventional to only measure boosts relative
to odd numbers rather than arbitrary numbers which could include evens.

For example, exclusion of 3 as a factor is a 1.5x boost over arbitrary odd numbers (from 2/3-rds not multiples of 3 to 3/3-rds). Flipside - inclusion of 3 as a factor is a 0.75x boost (from 2/3-rds to 1/2).

Similarly, exclusion of 5 as a factor is a 1.25x boost (4/5 to 5/5), but inclusion of 5 brings a 0.9375x boost (4/5 to 3/4). 7 gets more interesting, as we saw above. Exclusion of 7 is a 1.1667x boost (6/7 to 7/7), but inclusion of 7 is a 0.7778x boost (6/7 to 2/3), which you'll want to avoid if you're seriously into drag racing!

p | Ord2 | Powers of 2 in order | Excl# | Excl* | Incl# | Incl* | Worth |
---|---|---|---|---|---|---|---|

3 | 2 | all apart from 0 | 1 | 3/2=1.5000 | 2 | 3/4=0.75000 | 2=2.0000 |

5 | 4 | all apart from 0 | 1 | 5/4=1.2500 | 4 | 15/16=0.93750 | 4/3=1.3333 |

7 | 3 | 2, 4, 1, | 4 | 7/6=1.1667 | 3 | 7/9=0.77778 | 3/2=1.5000 |

11 | 10 | all apart from 0 | 1 | 11/10=1.1000 | 10 | 99/100=0.99000 | 10/9=1.1111 |

13 | 12 | all apart from 0 | 1 | 13/12=1.0833 | 12 | 143/144=0.99306 | 12/11=1.0909 |

17 | 8 | 2, 4, 8, 16, 15, 13, 9, 1, | 9 | 17/16=1.0625 | 8 | 119/128=0.92969 | 8/7=1.1429 |

19 | 18 | all apart from 0 | 1 | 19/18=1.0556 | 18 | 323/324=0.99691 | 18/17=1.0588 |

23 | 11 | 2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1, | 12 | 23/22=1.0455 | 11 | 115/121=0.95041 | 11/10=1.1000 |

29 | 28 | all apart from 0 | 1 | 29/28=1.0357 | 28 | 783/784=0.99872 | 28/27=1.0370 |

31 | 5 | 2, 4, 8, 16, 1, | 26 | 31/30=1.0333 | 5 | 62/75=0.82667 | 5/4=1.2500 |

37 | 36 | all apart from 0 | 1 | 37/36=1.0278 | 36 | 1295/1296=0.99923 | 36/35=1.0286 |

- Excl#
- # of k values that can avoid this prime as a factor (out of p)
- Excl*
- Ratio boost of prime density over arbitrary numbers achieved by excluding this prime
- Incl#
- # of k values that cannot avoid this prime as a factor (out of p)
- Incl*
- Ratio boost, <1 so actaully a drop, of prime density over arbitrary numbers suffered by not excluding this prime.
- Worth
- Relative boost of prime density between those that exclude this prime, and those that don't include this prime.

We can see from the above that the (ratio) difference between excluding a prime and not excluding it is Ord2/(Ord2-1). And therefore it's most useful to exclude primes with the smallest Ord2s. Now we know what the ratio boost is for excluding or failing to exclude a single prime (the Excl* or Incl* values, whichever one applies), we can multiply all the ratios for a large number of primes together to get a nett ratio indicating what the approximate density boost of the sequence is relative to arbitrary odd numbers. This ratio is called the "Proth Weight", or the "Nash Weight", and famous Proth-racer Jack Brennen has written a Proth Weight Calculation Applet in Java so that you can approximately measure these weights for arbitrary k values.

You want real numbers? I can get a density boost of >5.0 from some of my numbers. That's 10 times as dense as arbitrary numbers, and 5 times as dense as arbitrary odd numbers.

Proth-racing reached respectability when
Jack Brennen discovered his first
champion series 577294575*2^{n}+1, which set some
very high
records indeed.

Since then, however, there's a veritable olympics of events, both in terms of exactly what forms are raced, and over what distance.

Forms being raced: (note, some of these are dead links currently)

Form | Name | Races | ||
---|---|---|---|---|

k*2^{n}+1 | Proth | First to X primes, X=1..150... |
Most primes by n=N, N=1..∞ |
Weighted rate X/ln(n) |

k*2^{n}-1 | Riesel | |||

2^{n}+k | Proth Dual | |||

2^{n}-k | Riesel Dual | |||

k*2^{n}+/-1 | Twins | First to X twins, X=1..15 |
Most twins by n=∞ | Weighted rate X/ln(n) |

Another hastily constructed page by Phil Carmody

Home /
Maths /
Drag Racing Primes /
proth.html