Drag Racing Proth Primes!

What's So Special About Proth Numbers?

Proth numbers are numbers of the form k*2ⁿ+1 and for drag racing purposes you fix k, and vary only n, i.e. f_k(n)=k*2ⁿ+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

Average Density

One important property of Proth numbers (and, as I say, Riesel numbers) is that they grow quite quickly due to the exponential term 2ⁿ. 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.

Unusual Density

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.

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ⁿ+1 ≡ 1 (mod 3). However, for all other k values, 3 will appear as a factor of k*2ⁿ+1, for exactly half of the terms. This is because 2ⁿ 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ⁿ (mod 3) is the same as the period of k*2ⁿ+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ⁿ (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ⁿ+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ⁿ (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ⁿ+1 = 7*k'*2ⁿ+1 ≡ 1 (mod 7)
• Those with k ≡ {1,2,4} (mod 7) . For these k*2ⁿ+1 ≡ {2,3,5} (mod 7)
• Those with k ≡ {3,6,5} (mod 7) . For these k*2ⁿ+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ⁿ (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ⁿ (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ⁿ (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.

How Unusual?

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ⁿ+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!

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 Records

Proth-racing reached respectability when Jack Brennen discovered his first champion series 577294575*2ⁿ+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*2n+1	Proth	First to X primes, X=1..150...	Most primes by n=N, N=1..∞	Weighted rate X/ln(n)
k*2n-1	Riesel
2n+k	Proth Dual
2n-k	Riesel Dual
k*2n+/-1	Twins	First to X twins, X=1..15	Most twins by n=∞	Weighted rate X/ln(n)