Prime Powers of Primes

Question

For the purpose of this challenge, a Prime Power of a Prime (PPP) is defined as a number that can be defined as a prime number to the power of a prime number. For example, 9 is a PPP because it can be represented as 3^2. 81 on the other hand is not a PPP because it can only be represented as 3^4, and 4 is not prime. The first few PPPs are: 4, 8, 9, 25, 27, 32, 49, 121, 125, 128, 169, 243, 289, 343... This is OEIS sequence A053810

Your Task:

Write a program or function that for an input integer n returns/outputs the nth PPP, either 1-indexed or 0-indexed, whichever you prefer.

Input:

An integer between 0 and 1,000, received through any reasonable method.

Output:

The PPP at the index indicated by the input.

Test Cases:

These are 1-indexed, and so, if your program takes 0-indexed input, the same output should be arrived at for the stated input - 1.

3 -> 9
6 -> 32
9 -> 125

Scoring:

This code-golf,lowest score in bytes wins!

• Gryphon: This challenge was sandboxed

Answer 1

05AB1E (legacy), (削除) 9 (削除ここまで) 7 bytes

Saved 2 bytes thank to @KevinCruijssen

μNÓ0Kp»

Try it online!

μ # while counter_variable != input:
 N # push iteration counter e.g. 125
 Ó # get prime exponents -> [0, 0, 3]
 0K # filter out zeros -> [3]
 p # is prime? -> [1]
 » # join with newlines: we use » instead of J
 # so that [0,1] is not interpreted as truthy -> 1
 # implicit: if 1, increment counter_variable

• Kevin Cruijssen: Oh, I like the use of » instead of J so 0\n1 isn't interpret as truthy! But you can save a byte in the legacy version of 05AB1E (which you also used in your TIO), by omitting the ½, since this is done implicitly for µ (second bullet-point in this 05AB1E tip of mine). Also, ʒĀ} can be 0K. 7 bytes
• Arnauld: @KevinCruijssen Cool. Thanks!

Answer 2

Husk, 10 bytes

!fȯṗ§*ELpN

Try it online!

Explanation

!fȯṗ§*ELpN Implicit input.
 f N Filter the natural numbers by this function:
 ȯṗ§*ELp Argument is a number, say 27.
 p Prime factors: [3,3,3]
 L Length: 3
 E Are all elements equal: 1
 §* Multiply last two: 3
 ȯṗ Is it prime? Yes, so 27 is kept.
! Index into remaining numbers with input.

Answer 3

Haskell, (削除) 95 (削除ここまで) (削除) 85 (削除ここまで) 80 bytes

-10 bytes thanks to @Lynn
-5 bytes thanks to @WillNess

0-based

(!!)[x|x<-[2..],p<-[[i|i<-[2..x],all((>)2.gcd i)[2..i-1]]],or[y^e==x|e<-p,y<-p]]

Try it online!

Explanation

(!!) -- point-free expression, partially evaluate index-access operator
[x|x<-[2..] -- consider all integers x>=2
,p<- -- let p be the list of all primes <=x
[[ -- list of a list so p ends up as a list
i|i<-[2..x], -- consider all i<=x to be potentially prime
all((>)2.gcd i)[2..i-1] -- if the gcd of i with all smaller integers is
 -- smaller than 2 then this i is actually prime
 ]],or -- if any of the following list entries is true
[y^e==x| -- the condition y^e==x holds for x with ...
e<-p,y<-p] -- y and e being prime, i.e. x is a PPP,
] -- then add this x to the output sequence / list

• lynn: f=(!!)[x|x<-[2..],or[y^e==x|y<-p x,e<-p x]] saves 10 bytes.
• Will Ness: can get to 82 bytes by inlining : f=(!!)[x|x<-[2..],p<-[[i|i<-[2..x],all((>)2.gcd i)[2..i-1]]],or[y^e==x|e<-p,y<-p]]. maybe it's OK then to not count the f=? (never sure about the rules).
• Will Ness: I was once told that indeed f= shouldn't be counted. So it'll be 80 bytes, with (!!)[x|x<-[2..],p<-[[i|i<-[2..x],all((>)2.gcd i)[2..i-1]]],or[y^e==x|e<-p,y<-p]].

Answer 4

Actually, 14 bytes

Based on Mr. Xcoder's Pyth solution. Golfing suggestions welcome. Try it online!

;ur♂P;∙⌠in⌡MSE

Ungolfing

 Implicit input n
;ur Duplicate and push [0..n]
 ♂P Push the 0th to nth primes
 ;∙ Push Cartesian square of the primes
 ⌠in⌡M Reduce each list in the Cartesian square by exponentiation
 SE Sort the list and get the nth index (0-indexed)

Answer 5

Mathematica, 48 bytes

Sort[Join@@Array[(p=Prime)@#^p@#2&,{#,#}]][[#]]& 

Try it online!

but Martin Ender had a better idea and saved 6 bytes

Mathematica, 42 bytes

Sort[Power@@@Prime@Range@#~Tuples~2][[#]]& 

Try it online!

• Martin Ender: You can use Union instead of Join to avoid the Sort.
• Martin Ender: But I think Outer saves another byte over Array: (Union@@Outer[Power,p=Prime@Range@#,p])[[#]]&
• Martin Ender: And Tuples is even shorter: Sort[Power@@@Prime@Range@#~Tuples~2][[#]]&

Answer 6

Jelly, (削除) 12 (削除ここまで) (削除) 11 (削除ここまで) 10 bytes

1 byte thanks to Dennis.

ÆN€*þ`FṢị@

Try it online!

Answer 7

R + numbers, 57 bytes

function(n,x=numbers::Primes(2*n))sort(outer(x,x,"^"))[n]

Try it online!

outer is such a handy function.

Fairly certain this will always work. Will make a formal argument when I have the time.

Answer 8

Python 2, (削除) 163 (削除ここまで) (削除) 157 (削除ここまで) (削除) 137 (削除ここまで) 136 bytes

• Saved six bytes by using input() rather than defining a function.
• Saved four bytes thanks to Felipe Nardi Batista; merging two loops.
• Saved sixteen bytes thanks to ASCII-only.
• Saved a byte thanks to ArBo.

p=input();r=i=0;e=lambda p:all(p%d for d in range(2,p))
while~-i<p:
 r+=1
 for x in range(r*r):y=x%r;x/=r;i+=x**y==r>e(x)>0<e(y)
print r

Try it online!

• Felipe Nardi Batista: use lists instead to save a byte: i=[] and ....i+=[r]*....
• Felipe Nardi Batista: 153 bytes by removing the second for
• Jonathan Frech: @FelipeNardiBatista I did not use lists, as in its first iteration the program was defining a function. Thanks for spotting and the further golf.
• ASCII-only: Can't you return r instead of i[p]
• ASCII-only: 137?

Answer 9

APL (Dyalog Extended), 15 bytes

{⍵⌷∧∊∘.*⍨ ̄2⍭⍳⍵}

Try it online!

Explanation

{⍵⌷∧∊∘.*⍨ ̄2⍭⍳⍵}
 ⍵ Right argument. Our input.
{ } Wraps the function in dfn syntax which allows us to use ⍵.
 ⍳ Range [1..⍵].
 ̄2⍭ Get the n-th prime for each n in the range.
 ∘.*⍨ Get the prime powers of each prime.
 ∊ Flatten the list.
 ∧ In Extended, this is monadic sort ascending.
 ⍵⌷ Get the input-th index of the list of prime powers of primes.

Answer 10

Pyth, 15 bytes

e.f/^FR^fP_TSZ2

Try it here! or Verify more test cases.

Explanation

e.f/^FR^fP_TSZ2 - Full program. Q means input.
 .f - First Q inputs with truthy results. Uses the variable Z.
 fP_TSZ - Filter the range [1, Z] for primes.
 ^ 2 - Cartesian square. Basically the Cartesian product with itself.
 ^FR - Reduce each list by exponentiation.
 / - Count the occurrences of Z in ^.
e - Last element.

Answer 11

Javascript (削除) 137 (削除ここまで) 133 bytes

P=n=>{for(p=[i=2];j=++i<n*9;j^i&&p.push(i))
for(;j*j<=i;)j=i%++j?j:i
x=[]
for(i of p)
for(j of p)
x[i**j]=1
return Object.keys(x)[n]}
console.log(P(1000))
console.log(P(800))
console.log(P(9))
console.log(P(5))

**normal algorithem(100ms result) P =n => {

 for(p=[i=2];f=++i<=n*10;!f||p.push(i))
 for(j=0;f&&(x=p[j++])*x<=i;)
 f=i%x
 x=[]
 T=0
 for(i of p)
 for(j of p)
 {
 l= i**j
 if(++T>n &&x.length<l )
 break
 x[l] = 1
 }
 return Object.keys(x)[n]
}

• Gryphon: Umm, this is code-golf, not fastest-code. Therefore, the speed of your submission compared to others is not important, as this is scored by byte count. Please include the byte count and language of your submission in your answer.
• DanielIndie: but it should have at least a time limit , i can golf it to , but than a 100ms solution will become a 5 seconds solution, is it ok?
• Gryphon: The solution may take any finite amount of time to run. The only goal is to make the code shorter.

Answer 12

Perl 6, 50 bytes

{(sort [X**] (^7028,^24)>>.grep(&is-prime))[$_-1]}

Try it online!

 (^7028,^24) # create 2 ranges from 0
 >>.grep(&is-prime) # grep for primes in both
 [X**] ... # calc each exponential pair (2^2, 2^3, 2^5...)
(sort ... )[$_-1] # sort and get value at index n-1

The reasons for the 24 and 7028 are that the largest value (n=1000) is 49378729, which is 7027^2, and the largest prime power of 2 which fits under that is 23. So covering 2..7027 ^ 2..23 includes all the items in the first 1000 (and a lot of spares).

Answer 13

Pyth - 13 bytes

e.f&P_lPZ!t{P

Test Suite.

Answer 14

Java 8, 211 bytes

import java.util.*;n->{List l=new Stack();for(int a=2,b;a<132;a++)for(b=2;b<132;b++)if(p(a)*p(b)>0)l.add(Math.pow(a,b));Collections.sort(l);return l.get(n);}int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}

Very inefficient method.. It basically calculates all PPP's from 2² through (削除) 999⁹⁹⁹ (削除ここまで) 132¹³² and stores it in a List, then sorts that List, and then gets the n'th item from that List.

EDIT: Instead of using 999⁹⁹⁹ which results in a List of 28,225 items, I now use 132¹³² which results in a List of just 1,024 items. This improves the performance quite a bit, and is perfectly acceptable since the challenge states we should support an input from index 0 through 1,000. (Changing 1e3 to 132 doesn't affect the byte-count, though.)

Explanation:

Try it here.

import java.util.*; // Required import for List, Stack and Collections
n->{ // Method with integer as parameter and Object as return-type
 List l=new Stack(); // List to store the PPPs in
 for(int a=2,b;a<132;a++) // Loop (1) from 2 to 1,000 (exclusive)
 for(b=2;b<132;b++) // Inner loop (2) from 2 to 1,000 (exclusive)
 if(p(a)*p(b)>0) // If both `a` and `b` are primes:
 l.add(Math.pow(a,b)); // Add the power of those two to the List
 // End of loop (2) (implicit / single-line body)
 // End of loop (1) (implicit / single-line body)
 Collections.sort(l); // Sort the filled List
 return l.get(n); // Return the `n`'th item of the sorted List of PPPs
} // End of method
int p(int n){ // Separated method with integer as parameter and return-type
 for(int i=2; // Index integer (starting at 2)
 i<n; // Loop from 2 to `n` (exclusive)
 n=n%i++<1? // If `n` is divisible by `i`:
 0 // Change `n` to 0
 : // Else:
 n // Leave `n` the same
 ); // End of loop
 return n; // Return `n` (which is now 0 if it wasn't a prime)
} // End of separated method

Answer 15

PARI/GP, 48 bytes

f(n)=[x|x<-[1..4^n],isprime(isprimepower(x))][n]

If you do not count the f(n)= part, that is 43 bytes.

---

Another approach without the set notation which does not check so many unnecessary cases:

f(n)=c=0;i=1;while(c<n,i++;isprime(isprimepower(i))&&c++);i

Answer 16

J, 21 bytes

{[:/:~@,[:^/~p:@i.@>:

Zero-indexed anonymous function.

Try it online!

Trying to get back into the swing of things but I seem to have forgotten all tricks to make good monadic chains.

Short explanation

Constructs a table of prime powers from the 0th prime to the prime at the index of the input plus 1 (to account for 0). Flattens this list and sorts it and then indexes into it. I realize now that this might give incorrect results for some values since the table might not be large enough -- in that case I'd edit in a hardcoded value like 1e4 which should suffice. I can't prove it one way or the other (it passes for the test cases given), so do let me know if this is an issue.

Also 21 bytes

3 :'y{/:~,^/~p:i.>:y'