30
\$\begingroup\$

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.

\$\endgroup\$
7
  • 9
    \$\begingroup\$ What is the index of 2? Is it 1 or 0? \$\endgroup\$
    – Dennis
    Commented Jul 7, 2017 at 21:44
  • 5
    \$\begingroup\$ @Dennis the sequence is 1-indexed; the index of 2 is 1. \$\endgroup\$ Commented Jul 7, 2017 at 22:03
  • 5
    \$\begingroup\$ 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! \$\endgroup\$
    – JFBM
    Commented Jul 8, 2017 at 19:28
  • 1
    \$\begingroup\$ @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 \$\endgroup\$
    – Mayube
    Commented Jul 10, 2017 at 8:33
  • 1
    \$\begingroup\$ 435748987787 happens to be the 11th super^11-prime, for anyone interested. \$\endgroup\$
    – JFBM
    Commented Jul 10, 2017 at 13:19

34 Answers 34

1
2
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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).
)
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.