Super-prime

Super-prime numbers,also known ashigher-order primesorprime-indexed primes(PIPs), are thesubsequenceofprime numbersthat occupy prime-numbered positions within the sequence of all prime numbers. In other words, if prime numbers are matched with ordinal numbers, starting with prime number 2 matched with ordinal number 1, the primes matched with prime ordinal numbers are the super primes.

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,... (sequenceA006450in theOEIS).

That is, ifp(n) denotes thenth prime number, the numbers in this sequence are those of the formp(p(n)).

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
p(n)	2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71
p(p(n))	3	5	11	17	31	41	59	67	83	109	127	157	179	191	211	241	277	283	331	353

Dressler & Parker (1975)used a computer-aided proof (based on calculations involving thesubset 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 resemblingBertrand'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 (2009)show that there are

{\frac {x}{(\log x)^{2}}}+O\left({\frac {x\log \log x}{(\log x)^{3}}}\right)

super-primes up tox. This can be used to show that the set of all super-primes issmall.

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 withpalindromic primeindices, beginning with

3, 5, 11, 17, 31, 547, 739, 877, 1087, 1153, 2081, 2381,... (sequenceA124173in theOEIS).

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,MR 3097157
Broughan, Kevin A.; Barnett, A. Ross (2009),"On the subsequence of primes having prime subscripts",Journal of Integer Sequences,12,article 09.2.3.
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,MR 0376599.
Fernandez, Neil (1999),An order of primeness, F(p).

External links

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

Thisnumber theory-related article is astub.You can help Wikipedia byexpanding it.

v t e Prime numberclasses
By formula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Double Mersenne ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Factorial ( $n!\pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin
By property	Wieferich(pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient Unique
Base-dependent	Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Minimal Delicate Primeval Full reptend Unique Happy Self Smarandache–Wellin Strobogrammatic Dihedral Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n \pm 1, 2 n \pm 1, 4 n \pm 1,\dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k-tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain/Safe ( $p,2 p + 1$ ) Cunningham ( $p,2 p \pm 1, 4 p \pm 3, 8 p \pm 7,...$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3,...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Mega (1,000,000+ digits) Largest known list
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Perrin Somer–Lucas Strong Carmichael number Almost prime Semiprime Sphenic number Interprime Pernicious
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 60 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
List of prime numbers