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

34 Answers 34

21
\$\begingroup\$

Jelly, 5 bytes

ÆRÆNċ

Try it online!

How it works

ÆRÆNċ  Main link. Argument: n

ÆR     Prime range; yield the array of all primes up to n.
  ÆN   N-th prime; for each p in the result, yield the p-th prime.
    ċ  Count the occurrences of n.
\$\endgroup\$
3
  • 9
    \$\begingroup\$ Gosh darn it, you win again... \$\endgroup\$ Jul 7, 2017 at 21:50
  • 4
    \$\begingroup\$ He always does... \$\endgroup\$
    – Gryphon
    Jul 8, 2017 at 4:20
  • \$\begingroup\$ @ETHproductions Well, solution is pretty obvious...it's just the ninja here. \$\endgroup\$ Jul 8, 2017 at 13:52
15
\$\begingroup\$

Mathematica, 26 23 bytes

Thanks to user202729 for saving 3 bytes.

PrimeQ/@(#&&PrimePi@#)&

This makes use of the fact that Mathematica leaves most nonsensical expressions unevaluated (in this case, the logical And of two numbers) and Map can be applied to any expression, not just lists. So we compute the And of the input and its prime index, which just remains like that, and then we Map the primality test over this expression which turns the two operands of the And into booleans, such that the And can then be evaluated.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 23 bytes: PrimeQ/@(#&&PrimePi@#)&. \$\endgroup\$
    – DELETE_ME
    Jul 8, 2017 at 3:36
  • \$\begingroup\$ @user202729 Nice, thank you. :) \$\endgroup\$ Jul 8, 2017 at 6:37
10
\$\begingroup\$

Jelly, 6 bytes

ÆRi³ÆP

Try it online!

Uses the same technique as my Japt answer: Generate the primes up to n, get the index of n in that list, and check that for primality. If n itself is not prime, the index is 0, which is also not prime, so 0 is returned anyway.

\$\endgroup\$
10
\$\begingroup\$

Japt, 13 11 bytes

õ fj bU Ä j

Test it online!

Explanation

This is actually very straight-forward, unlike my original submission:

 õ fj bU Ä  j    
Uõ fj bU +1 j    Ungolfed
                 Implicit: U = input integer
Uõ               Generate the range [1..U].
   fj            Take only the items that are prime.
      bU         Take the (0-indexed) index of U in this list (-1 if it doesn't exist).
         +1 j    Add 1 and check for primality.
                 This is true iff U is at a prime index in the infinite list of primes.
                 Implicit: output result of last expression
\$\endgroup\$
5
\$\begingroup\$

Regex (Perl / PCRE), 55 54 53 bytes

^(?=((?=((\2x*?|^)((?!(xx+)\5+$)))xx)x)*(x*))\6(?4)xx

Try it online! - Perl
Try it online! - PCRE

Takes its input in unary, as a string of x characters whose length represents the number. Based on Prime counting function.

^       # tail = N = input value
(?=
    # Calculate π(N) = the number of primes <= N, by counting
    # from the largest to the smallest prime.
    (       # J = 0
        (?=
            # \2 starts at zero, and on each subsequent iteration, contains the
            # difference N-P-(J-1) where P is the previously found prime, and J
            # is the running total of our prime count.
            (
                (
                    \2           # Start from the previous value of \2. This
                                 # will make tail = P-1, where P is the
                                 # previously found prime.
                    x*?          # Advance as little as necessary to make the
                                 # following match, and add this to \2, while
                                 # subtracting it from tail.
                |        # or
                    ^            # Don't advance at all on the first iteration
                                 # (when \2 is is still unset), so as to assert
                                 # that N is not composite.
                )
                ((?!(xx+)\5+$))  # Define and use subroutine (?4): Assert tail
                                 # is prime. Note that this needs to be inside
                                 # group \2 for it to work in PCRE1 and older
                                 # versions of PCRE2, which atomicize groups
                                 # that have nested backreferences.
            )
            xx                   # Assert tail is prime by eliminating the
                                 # false positives 0, 1
        )
        x   # J += 1; tail -= 1
    )*      # Iterate zero or more times, until there are no smaller primes
            # remaining.
    # At this point, head = π(N), and tail = N - π(N)
    (x*)    # \6 = tail = N - head = tool to make tail = head
)
\6          # tail = π(N)
(?4)xx      # Assert tail is prime

Alternative 55 54 53 bytes:

^(?=((?=((\2x*?|^)((?!(xx+)\5+$|x?$))))x)*(x*))\6(?4)

Try it online! - Perl
Try it online! - PCRE

This eliminates the false negatives \$0\$ and \$1\$ in the definition of the primality subroutine instead of patching its second and third individual uses.

Regex (.NET), 70 60 58 bytes

^(?=(\3*?(?!(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. Since .NET regex has no subroutines, this has three two copies of the primality test.

^                      # 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
    (
        \3*?           # Advance as little as necessary to make the following
                       # match, but don't advance at all on the first iteration
                       # (when \3 is is still unset), so as to assert that N is
                       # not composite.
        (?!(xx+)\2+$)  # Assert tail is not composite
        (x)            # Eliminate the false primality positive of 0, and advance
                       # forward so that the next prime can be found (if we didn't
                       # do this, the regex engine would exit the loop due to a
                       # zero-width match); \3 = 1, to signal the first iteration
                       # has been done, and push a capture onto the Group 3 stack.
    )*                 # Loop as many times as can be done until its stops
                       # matching.
    x                  # Eliminate the false primality positive of 1
)
(?<-3>x){2,}           # Pop all Group 3 captures off the stack, asserting that
                       # the count is ≥ 2, 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|^\4+(x+x))      # Assert that the Group 3 capture stack is empty, and that
                       # head is not composite (and since it's already been
                       # forced to be ≥ 2, this asserts it to be prime).

Regex (Perl / Java / PCRE / .NET), 60 bytes

^(?=((?=((\2x*?|^)(?!(xx+)\4+$))xx)x)*(x*))\5(?!(xx+)\6+$)xx

Try it online! - Perl
Try it online! - Java
Try it online! - PCRE
Try it online! - .NET

This is a straight port of the Perl/PCRE version, to regex engines that lack subroutine calls but support nested backreferences. The subroutine call has been replaced with a copy of the routine.

Regex (Perl / PCRE / Pythonregex), 61 bytes

^(?=((?=((\6x*?|^)((?!(xx+)\5+$)))xx)(?=(\2))x)*(x*))\7(?4)xx

Try it online! - Perl
Try it online! - PCRE
Try it online! - Python import regex

This is a port of the Perl/PCRE version. \2 is copied into \6 using the lookahead (?=(\2)), since Python (even with import regex) lacks nested backreferences.

Regex (PCRE / Ruby), 62 bytes

^(?=((?=((\6x*?|^)((?!(xx+)\5+$)))xx)(?=(\2))x)*(x*))\7\g<4>xx

Try it online! - PCRE
Try it online! - Ruby

This is a straight port of the Pythonregex version, to Ruby's subroutine call syntax.

Regex (Perl / Java / PCRE / Pythonregex / Ruby / .NET), 68 bytes

^(?=((?=((\5x*?|^)(?!(xx+)\4+$))xx)(?=(\2))x)*(x*))\6(?!(xx+)\7+$)xx

Try it online! - Perl
Try it online! - Java
Try it online! - PCRE
Try it online! - Python import regex
Try it online! - Ruby
Try it online! - .NET

To be portable to all 6 regex engines, this uses neither nested backreferences nor subroutine calls.

\$\endgroup\$
4
\$\begingroup\$

Python 3, 104 97 93 bytes

p=lambda m:(m>1)*all(m%x for x in range(2,m))
f=lambda n:p(n)*p(len([*filter(p,range(n+1))]))

Returns 0/1, at most 4 bytes longer if it has to be True/False.

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 0/1 is fine. Nice answer! Since you don't ever use the value of f, you can reformat your code like this and exclude it from the byte count. \$\endgroup\$ Jul 7, 2017 at 21:57
  • \$\begingroup\$ @musicman523 Thanks for the tip! \$\endgroup\$
    – C McAvoy
    Jul 9, 2017 at 22:22
4
\$\begingroup\$

Python 2, 79 bytes

n=input()
s={2};p=i=1
while i<n:
 p*=i;i+=1
 if p*p%i:s|={i}
print{n,len(s)}<=s

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Jelly, 7 bytes

ÆCÆPaÆP

Try it online!

ÆC counts the number of primes less than or equal to the input (so, if the input is the nth prime, it returns n). Then ÆP tests this index for primality. Finally, a does a logical AND between this result and ÆP (primality test) of the original input.

\$\endgroup\$
3
\$\begingroup\$

Haskell, 62 bytes

p x=2==sum[1|0<-mod x<$>[1..x]]
f x=p$sum[1|y<-[1..x],p y,p x]

Try it online! Usage: f 991 yields True.

\$\endgroup\$
3
\$\begingroup\$

Husk, 2 bytes

ṗṗ

Try it online!

One of the cases when the behaviours of functions returning non booleans is really helpful.

user's solution.

Husk, 4 bytes

ṗ£İp

Try it online! or Verify all test cases

\$\endgroup\$
3
  • \$\begingroup\$ 2 or 3 bytes? \$\endgroup\$
    – user
    Oct 10, 2020 at 20:55
  • 1
    \$\begingroup\$ @user yep, 2 bytes. \$\endgroup\$
    – Razetime
    Oct 11, 2020 at 4:39
  • 1
    \$\begingroup\$ @user You don't need the trailing due to implicit input, plus, putting it on a seperate line just declares it as a new function, which doesn't affect the first line \$\endgroup\$
    – Jo King
    Oct 11, 2020 at 8:56
2
\$\begingroup\$

05AB1E, 6 bytes

ÝØ<Øså

Try it online!

Explanation

ÝØ<Øså
Ý      # Push range from 0 to input
 Ø     # Push nth prime number (vectorized over the array)
  <    # Decrement each element by one (vectorized)
   Ø   # Push nth prime number again
    s  # swap top items of stack (gets input)
     å # Is the input in the list?
\$\endgroup\$
1
  • \$\begingroup\$ Nice, almost the same as the answer I just came up with. Also, ÅP can be used instead of ÝØ (not that it saves any bytes, but hey, it's a built-in that does the trick). \$\endgroup\$
    – Makonede
    Mar 30, 2021 at 0:37
2
\$\begingroup\$

Pyth, 12 bytes

&P_QP_smP_dS

Try it online!

Explanation

&P_QP_smP_dS
                Implicit input
       mP_dS    Primality of all numbers from 1 to N
      s         Sum of terms (equal to number of primes ≤ N)
    P_          Are both that number
&P_Q            and N prime?
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 35 29 bytes

P=Prime;!P@P@Range@#~FreeQ~#&

-6 bytes from @MartinEnder

\$\endgroup\$
1
  • \$\begingroup\$ P@P@Range@# should save a bunch. \$\endgroup\$ Jul 7, 2017 at 21:55
2
\$\begingroup\$

Pyke, 8 bytes

sI~p>@hs

Try it here!

s        -  is_prime(input)
 I~p>@hs - if ^:
  ~p>    -    first_n_primes(input)
     @   -    ^.index(input)
      h  -   ^+1
       s -  is_prime(^)
\$\endgroup\$
2
\$\begingroup\$

Python 2, 89 bytes

def a(n):
 r=[2];x=2
 while x<n:x+=1;r+=[x]*all(x%i for i in r)
 return{n,len(r)}<=set(r)

Try it online!

Constructs r, the list of primes <= n; if n is prime, then n is the len(r)'th prime. So n is a super prime iff n in r and len(r) in r.

\$\endgroup\$
2
+350
\$\begingroup\$

Factor + math.primes, 51 49 36 32 bytes

Saved 13 bytes thanks to @Bubbler! Saved 4 bytes thanks to @chunes!

[ dup nprimes index ?1+ prime? ]

Try it online!

[ dup nprimes index ?1+ prime? ]
  dup nprimes                    ! First n primes (generates extra primes)
              index              ! Find the index of the input in that
                                 ! when the index is not found, an f is outputted
                                 ! If the index exists,
                    ?1+          ! If it's a number, increment
                                 ! If it's f, output 0 (which is not prime)
                        prime?   ! Is that prime?
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can simplify it to [ dup primes-upto index ?1+ prime? ]. ?1+ increments an integer or consumes an f and gives 0. \$\endgroup\$
    – Bubbler
    Mar 29, 2021 at 23:28
  • 1
    \$\begingroup\$ You can save 4 bytes by using nprimes instead of primes-upto. It's less efficient of course, but small price to pay. \$\endgroup\$
    – chunes
    Mar 30, 2021 at 0:46
2
\$\begingroup\$

Vyxal g, 4 bytes

¡†"æ

Try it Online! - test cases only

This is the same as the 5 byte answer below except the minimum is taken by the g flag rather than a g element.

Vyxal, 5 bytes

¡†"æg

Try it Online!
Try it Online! - test cases only

This makes use of Prime counting function, based on Dennis's 05AB1E solution to that challenge. This is actually much faster than the other two 5 byte solutions presented below it.

¡  # Factorial
†  # Number of distinct prime factors – when applied to the factorial, this
   # gives the index of the greatest prime ≤ the input number (1-indexed).
"  # Wrap the top two items (the input number, and the above result) in a list.
æ  # Is the number prime? (Vectorized)
g  # Minimum - effectively applies a boolean AND to the list

Alternative 5 bytes:

Þpḟ›æ

Try it Online!
Try it Online! - test cases only

Þp  # An infinite list of primes
ḟ   # Index of input number in that list (0-indexed; -1 if not found)
›   # Add 1
æ   # Is the number prime?

Another alternative 5 bytes:

Þp‹ǎc

Try it Online!
Try it Online! - test cases only

Port of Datboi's 05AB1E solution. This is much slower than the primary 5 byte solution above, but much faster than its 05AB1E counterpart.

Þp # An infinite list of primes
‹  # Subtract 1 from every item on the list
ǎ  # Nth prime - vectorized to the entire list
c  # Contains - Is the input number a member of that list?
\$\endgroup\$
2
\$\begingroup\$

Thunno D, \$ 8 \log_{256}(96) \approx \$ 6.58 bytes

FAFLZPNP

Attempt This Online!

Port of Deadcode's Vyxal answer.

It's all uppercase letters!

Explanation

FAFLZPNP  # Implicit input
F         # Factorial
 AF       # Unique prime factors
   L      # Length
    ZP    # Pair
      N   # Is prime
       P  # Product
          # Implicit output
\$\endgroup\$
2
\$\begingroup\$

Raku, 46 35 bytes

{$/=&is-prime;all($_∈*,$/)([grep $/,1..$_])}

grep {.is-prime&&is-prime ++$},^∞

Try it online!

Six years of golfing experience let me cut down on this solution considerably.

\$\endgroup\$
1
\$\begingroup\$

QBIC, 33 bytes

~µ:||\_x0]{p=p-µq|~q=a|_xµp]q=q+1

Explanation

~   |   IF   ....  THEN (do nothing)
  :         the number 'a' (read from cmd line) 
 µ |        is Prime
\_x0        ELSE (non-primes) quit, printing 0
]           END IF
{           DO
            In this next bit, q is raised by 1 every loop, and tested for primality. 
            p keeps track of how may primes we've seen (but does so negatively)
    µq|     test q for primality (-1 if so, 0 if not)
p=p-        and subtract that result from p (at the start of QBIC: q = 1, p = 0)
~q=a|       IF q == a
_xµp        QUIT, and print the prime-test over p (note that -3 is as prime as 3 is)
]           END IF
q=q+1       Reaise q and run again.
\$\endgroup\$
1
\$\begingroup\$

Haskell, 121 bytes

f=filter
p x=2==(length$f(\a->mod(x)a==0)[1..x])
s=map(\(_,x)->x)$f(\(x,_)->p x)$zip[1..]$f(p)[2..]
r x=x`elem`(take x s)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ (\(_,x)->x) is snd, (\(x,_)->p x) is (p.fst). Both fst and snd are in Prelude, so no need for imports. \$\endgroup\$
    – Laikoni
    Jul 7, 2017 at 23:52
  • \$\begingroup\$ Don't use backticks too often: r x=elem x$take x s. However, in this case you can go pointfree (introducing backticks again) and omit the function name: elem<*>(`take`s). \$\endgroup\$
    – nimi
    Jul 8, 2017 at 12:32
1
\$\begingroup\$

Positron, 148 bytes

x=#(input@@)a=function{p=1;k=$1==2;f=2;while(f<$1)do{p=p*$1%f;k=1;f=f+1};return p*k}r=1;i=2;while(i<x)do{if(a@i)then{r=r+1}i=i+1}print@((a@x*a@r)>0)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 31 bytes

n->(p=isprime)(n)*p(primepi(n))

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Matlab, 36 34 bytes

Saved 2 bytes thanks to Tom Carpenter.

A very naive implementation using built-in functions:

isprime(x)&isprime(nzz(primes(x)))
\$\endgroup\$
1
  • 1
    \$\begingroup\$ For Octave only you can also save a further byte with (p=@isprime)(x)&p(nnz(primes(x))) \$\endgroup\$ Jul 8, 2017 at 17:28
1
\$\begingroup\$

Julia 0.6, 61 bytes

return 1 if x is a super-prime, 0 otherwise.

without using an isprime-kind function.

x->a=[0,1];for i=3:x push!(a,0∉i%(2:i-1))end;a[sum(a)]&a[x]
\$\endgroup\$
1
\$\begingroup\$

Japt, 11 bytes

ÒÈj}jU bU)j

Try it

\$\endgroup\$
1
\$\begingroup\$

Pyth, 9 bytes

P_hx.fP_Z

Test suite

Uses a fairly different approach to the existing Pyth solution. Returns True for super-primes, False for non-super-primes, and [] (falsy) for composite numbers.

\$\endgroup\$
1
1
\$\begingroup\$

Ruby, 72 bytes

Tired of all the extremely obscure golfing languages in this thread? Here's the practical language solution you're looking for! Let me know if you see a way to shave off a few bytes.

require'prime';n=gets.to_i;p n.prime?&&(Prime.take(n).index(n)+1).prime?

Try it online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 6 bytes

.Ø>‚pß

Try it online! - 05AB1E
Try it online! - 05AB1E - test cases only
Try it online! - 05AB1E (legacy) - test cases only

Equal in length to Datboi's solution, but much faster on numbers that are not super-prime.

.Ø  # Get 0-indexed number of the greatest prime ≤ input number
>   # Add 1
‚   # Wrap the top two items (the input number, and the above result) in a list
p   # Is the number prime? (Vectorized)
ß   # Minimum - effectively applies a boolean AND to the list

Alternative 6 bytes:

!fg‚pß

Try it online!
Try it online! - test cases only

This makes use of Dennis's Prime counting function solution, which is equal in length to (but slower than) the ones using built-in prime-counting functions.

\$\endgroup\$
1
\$\begingroup\$

C89 (clang), 92 bytes

#define s for(i=e;--i&&e%i;)p+=i <3
p,r,i;m(e){s;for(p=r=i==e%2;--e;)s;e=p+1;s;return r<i<r;}

(added whitespace for readability)

Some alternatives:

  • i==e%2 \$\equiv\$ i==1&e
  • r<i<r \$\equiv\$ 1<i<r \$\equiv\$ i<2&r \$\equiv\$ i/2<r \$\equiv\$ i<r+r \$\equiv\$ i<2*r

Try it online!

\$\endgroup\$

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.