Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
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.
Given a positive integer, determine whether it is a super-prime.
2: false 3: true 4: false 5: true 7: false 11: true 13: false 17: true 709: true 851: false 991: true
This is code-golf, so the shortest answer in each language wins.
ÆRÆNċ
Æ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.
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.
ÆRi³ÆP
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.
õ fj bU Ä j
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
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.
f, you can reformat your code like this and exclude it from the byte count.
\$\endgroup\$
– musicman523
Jul 7 '17 at 21:57
ÆCÆPaÆP
Æ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.
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.
ÝØ<Øså
ÝØ<Ø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?
&P_QP_smP_dS
&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?
sI~p>@hs
s - is_prime(input)
I~p>@hs - if ^:
~p> - first_n_primes(input)
@ - ^.index(input)
h - ^+1
s - is_prime(^)
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
~µ:||\_x0]{p=p-µq|~q=a|_xµp]q=q+1
~ | 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.
P=Prime;!P@P@Range@#~FreeQ~#&
-6 bytes from @MartinEnder
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)
(\(_,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 '17 at 23:52
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 '17 at 12:32
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)
Saved 2 bytes thanks to Tom Carpenter.
A very naive implementation using built-in functions:
isprime(x)&isprime(nzz(primes(x)))
(p=@isprime)(x)&p(nnz(primes(x)))
\$\endgroup\$
– Tom Carpenter
Jul 8 '17 at 17:28
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)
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.
ṗṗ
One of the cases when the behaviours of functions returning non booleans is really helpful.
user's solution.
ṗ£İp
⁰ 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 '20 at 8:56
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]
