Super-prime

Short description: Prime numbers that occupy prime-numbered positions

Super-prime numbers, also known as higher-order primes or prime-indexed primes (PIPs), are the subsequence of prime numbers that occupy prime-numbered positions within the sequence of all prime numbers.

The subsequence begins

3, 5, 11, 17, 31, 41, 59, 67, 83, 109, 127, 157, 179, 191, 211, 241, 277, 283, 331, 353, 367, 401, 431, 461, 509, 547, 563, 587, 599, 617, 709, 739, 773, 797, 859, 877, 919, 967, 991, ... (sequence A006450 in the OEIS).

That is, if p(n) denotes the nth prime number, the numbers in this sequence are those of the form p(p(n)).

(Dressler Parker) used a computer-aided proof (based on calculations involving the subset sum problem) to show that every integer greater than 96 may be represented as a sum of distinct super-prime numbers. Their proof relies on a result resembling Bertrand's postulate, stating that (after the larger gap between super-primes 5 and 11) each super-prime number is less than twice its predecessor in the sequence.

(Broughan Barnett) show that there are

[math]\displaystyle{ \frac{x}{(\log x)^2} + O\left(\frac{x\log\log x}{(\log x)^3}\right) }[/math]

super-primes up to x. This can be used to show that the set of all super-primes is small.

One can also define "higher-order" primeness much the same way and obtain analogous sequences of primes (Fernandez 1999).

A variation on this theme is the sequence of prime numbers with palindromic prime indices, beginning with

3, 5, 11, 17, 31, 547, 739, 877, 1087, 1153, 2081, 2381, ... (sequence A124173 in the OEIS).

References

• Bayless, Jonathan; Klyve, Dominic; Oliveira e Silva, Tomás (2013), "New bounds and computations on prime-indexed primes", Integers 13: A43:1–A43:21, http://digitalcommons.cwu.edu/cgi/viewcontent.cgi?article=1004&context=math 
• Broughan, Kevin A.; Barnett, A. Ross (2009), "On the subsequence of primes having prime subscripts", Journal of Integer Sequences 12: article 09.2.3, http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Broughan/broughan16.html .
• Dressler, Robert E.; Parker, S. Thomas (1975), "Primes with a prime subscript", Journal of the ACM 22 (3): 380–381, doi:10.1145/321892.321900 .
• Fernandez, Neil (1999), An order of primeness, F(p), http://borve.org/primeness/FOP.html .

External links

• A Russian programming contest problem related to the work of Dressler and Parker