# Background

A super-prime is a prime number whose index in the list of all primes is also prime. The sequence looks like this:

3, 5, 11, 17, 31, 41, 59, 67, 83, 109, 127, 157, 179, 191, ...

This is sequence A006450 in the OEIS.

# Challenge

Given a positive integer, determine whether it is a super-prime.

# Test Cases

2: false
3: true
4: false
5: true
7: false
11: true
13: false
17: true
709: true
851: false
991: true


# Scoring

This is , so the shortest answer in each language wins.

• What is the index of 2? Is it 1 or 0? Commented Jul 7, 2017 at 21:44
• @Dennis the sequence is 1-indexed; the index of 2 is 1. Commented Jul 7, 2017 at 22:03
• First thought after reading what a super-prime is: What would you call super-super-primes? Or super^3-primes? What is bigger, the number of atoms in the universe or the 11th super^11-prime? You, dear internet person, are stealing another few hours of my hours of my prime time!
– JFBM
Commented Jul 8, 2017 at 19:28
• @J_F_B_M 11 is a super-prime who's index in the super-prime list is also a super-prime (3), so the 11'th super-prime is a super-super-super-prime Commented Jul 10, 2017 at 8:33
• 435748987787 happens to be the 11th super^11-prime, for anyone interested.
– JFBM
Commented Jul 10, 2017 at 13:19

# J, 13 bytes

e.p:@<:@p:@i.


Same idea as 05AB1E, Vyxal, and kind of Factor. Reminder (f g) y → y f g y.

Attempt This Online!

e.p:@<:@p:@i.
i.  NB. range 0..y
p:@    NB. then get nth prime, vectorized
<:@       NB. then decrement each
p:@          NB. then get primes again
e.             NB. is y a member of


# Pyt, 5 bytes

Đřᵽᵽ∈


Try it online!

Đ            implicit input; Đuplicate
ř           řangify [1,2,...,n]
ᵽ          get ᵽrimes with given indices
ᵽ         get ᵽrimes with given indices
∈        is input in the resulting array?; implicit print


# Regex (.NET), 57 bytes

^(?=((?!(xx+)\2+$)(x+?))+x$)(?<-3>x){2,}(?<!\3|^\4+(x+x))


Try it online!

This uses the .NET feature of balanced groups to do the prime counting, saving 3 bytes relative to the shortest version that doesn't use this feature and is still .NET-compatible. Since .NET regex has no subroutines, this has two copies of the primality test.

It is based on my 58 byte .NET regex answer. Shown side-by-side with it:

^(?=(\3*?(?!(xx+)\2+$)(x))*x)(?<-3>x){2,}(?<!\3|^\4+(x+x)) ^(?=((?!(xx+)\2+$)(x+?))+x$)(?<-3>x){2,}(?<!\3|^\4+(x+x))  This -1 byte golf relies on a mathematical conjecture, which is extremely likely to be true, but as far I can tell has not been proven: that $$\g(n)≤n\$$ always, where $$\g(n)\$$ is the $$\1\$$-indexed $$\n\$$th prime gap, i.e. OEIS A001223. For this reason I'm posting it as a separate answer, as the existing answer is already quite long and diluted with answers for other regex engines. For this regex to fail, there would need to be a counterexample $$\g(p)>p\$$ where $$\p\$$ is prime. This would give the regex false positives for the $$\\{p+1\}\$$th prime and every subsequent prime. It is known to hold true at least up to $$\n=423,731,791,997,205,041\$$, with $$\g(n)=1,550\$$ of course being far less than $$\n\$$. The prime is $$\p_n=18,361,375,334,787,046,697\$$, which is of course far too large for any conventional regex engine to match in unary, but theoretical accuracy up to infinity is the goal here. ^ # tail = N = input value # Calculate π(N) = the number of primes <= N, by counting # from the largest to the smallest prime. (?= # Atomic lookahead - lock in this match once it completes ( (?!(xx+)\2+$)  # Assert tail is not composite; since this is done at the
# beginning of the loop, it also asserts N is not composite
# on the first iteration.
(x+?)          # Eliminate the false primality positive of 0, and advance
# forward as little as necessary to make the next iteration
# match the next prime; push a capture onto the Group 3
# stack (containing the Kth prime gap, counting down from
# K=π(N) to K=1, such that by the time this loop finishes,
# on the top of the stack will be the value 1, and below
# that, the first prime gap, which is also 1).
)+                 # Loop at least once, and as many times as can be done
# until it stops matching.
x                  # Assert that tail == 1, to force the above loop to keep
# finding subsequent smaller primes (instead of exiting
# after finding only one prime) until the smallest prime,
# 2, is reached.
)
(?<-3>x){2,}   # Pop all Group 3 captures off the stack, asserting that the count
# is ≥ 2 (to eliminate the non-composite numbers 0 and 1 from being
# falsely identified as prime), and doing head += 1 for each one.
# Since this isn't done atomically, we need to subsequently verify
# that all captures were popped, due to backtracking if the
# following assertion fails.
(?<!
\3         # Assert that the Group 3 capture stack is empty. Note that this
# will only work up to infinity if the Kth prime gap is always less
# than or equal to K, i.e. that in OEIS A001223, a(K) ≤ K up to
# infinity. This is because if the below alternative matches, due
# to N being prime but not super-prime, it will cause the negative
# lookbehind to fail to match, causing the regex engine to
# backtrack into the "(?<-3>x){2,}" loop above, which at each step
# will subtract 1 from head, and restore a prime gap onto the top
# of the stack, starting with the last one. This will never reach
# the point of restoring either of the bottom two stack values
# (which are 1, 1) due to the "{2,}" constraint, which is good
# because the bottom-most one would compare 1 against 0, which is
# not less than or equal and would prevent this golf from working.
#
# Thus if there is any counterexample where a(P) > P, such that P
# is prime, this would cause \3 to fail to match with a non-empty
# capture stack (whereas it's intended only to fail to match due to
# the stack being empty and \3 being unset), and then the below
# alternative would be tried, also failing to match due to P being
# prime, resulting in the negative lookbehind matching, resulting
# in a false positive for the {P+1}th prime and every subsequent
# prime.
|
^\4+(x+x)  # Assert that head is not composite (and since it's already
# been forced to be ≥ 2, this asserts it to be prime).
)


# Nekomata + -e, 3 bytes

QƥQ


Attempt This Online!

QƥQ
Q       Check if the input is a prime
ƥ      Count number of primes <= input
Q     Check if the result is a prime