Double-Safe and Triple-Safe Primes

A safe prime \(p\) is one such that \( \dfrac{p-1}{2} \) is also prime.

The first example of such a prime is 5 because \( \dfrac{5-1}{2} =2\) which is prime.

However, we can generalise this notion and speak of a \(k\)-safe prime \(p\) where $$ \frac{p-(2^i-1)}{2^i} \text{ is prime for } i=0,1, 2, \dots  k$$Let's look at the various values of \(k\) as applied to a prime \(p\) :

• \(i=0\) just gives the originating prime \(p\)

• \(i=1\) means the prime is safe and  \( \dfrac{p-1}{2} \) is prime

• \(i=2\) means the prime is 2-safe or double-safe and  \( \dfrac{p-3}{4} \) is prime

• \(i=3\) means the prime is 3-safe or triple-safe and  \( \dfrac{p-7}{8} \) is prime

Let's look at a specific prime, 28319, that is known be a triple safe prime:

\(28319\) is prime

\(28319 \rightarrow \dfrac{28319-1}{2}  =14159\) which is thus a safe prime

\(28319 \rightarrow \dfrac{28319-3}{4} =7079\) which is thus a double-safe prime

\(28319 \rightarrow \dfrac{28319-7}{8}  =3539\) which is thus a triple-safe prime

\(28319 \rightarrow  \dfrac{28319-15}{16} =1769= 29 \times 61 \) which is not prime

These triple-safe primes form OEIS A157358 and the initial members are: 

23, 47, 719, 1439, 2879, 4079, 9839, 11279, 21599, 28319, 51599, 84719, 92399, 95279, 96959, 137279, 157679, 159119, 178799, 209519, 219839, 243119, 349199, 429119, 430799, 441839, 462719, 481199, 491279, 507359, 533999, 571199, 597599

As can be seen, 28319 is the last triple-safe prime that I'll see in my lifetime. The double-safe primes form OEIS A066179 and these are more frequent in the range up to 40000:

11, 23, 47, 167, 359, 719, 1439, 2039, 2879, 4079, 4127, 4919, 5639, 5807, 5927, 6047, 7247, 7559, 7607, 7727, 9839, 10799, 11279, 13799, 13967, 14159, 15287, 15647, 20327, 21599, 21767, 23399, 24407, 24527, 25799, 28319, 28607, 29399, 31607, 35879, 36887

What about quadruple, quintuple-safe primes and beyond. Up to 40000, there are only three quadruple-safe primes and these are 47, 1439 and 2879. Of these, only 2879 is a quintuple-safe prime (permalink). There is no sextuple-safe prime until we reach 71850239! Up to a billion, there are no septuple-safe primes.