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.


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


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


This ,lowest score in bytes wins!

  • \$\begingroup\$ This challenge was sandboxed \$\endgroup\$
    – Gryphon
    Commented Oct 7, 2017 at 12:27

16 Answers 16


05AB1E (legacy),  9  7 bytes

Saved 2 bytes thank to @KevinCruijssen


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
  • \$\begingroup\$ 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 \$\endgroup\$ Commented Apr 12, 2019 at 13:34
  • \$\begingroup\$ @KevinCruijssen Cool. Thanks! \$\endgroup\$
    – Arnauld
    Commented Apr 12, 2019 at 13:40

Husk, 10 bytes


Try it online!


!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.

Haskell, 95 85 80 bytes

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


(!!)[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!


(!!)                    -- 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
  • \$\begingroup\$ f=(!!)[x|x<-[2..],or[y^e==x|y<-p x,e<-p x]] saves 10 bytes. \$\endgroup\$
    – lynn
    Commented Oct 7, 2017 at 14:12
  • \$\begingroup\$ 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). \$\endgroup\$
    – Will Ness
    Commented Oct 9, 2017 at 1:24
  • \$\begingroup\$ 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]]. \$\endgroup\$
    – Will Ness
    Commented Oct 9, 2017 at 9:01

Actually, 14 bytes

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



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

Mathematica, 48 bytes


Try it online!

but Martin Ender had a better idea and saved 6 bytes

Mathematica, 42 bytes


Try it online!

  • \$\begingroup\$ You can use Union instead of Join to avoid the Sort. \$\endgroup\$ Commented Oct 7, 2017 at 14:05
  • \$\begingroup\$ But I think Outer saves another byte over Array: (Union@@Outer[Power,p=Prime@Range@#,p])[[#]]& \$\endgroup\$ Commented Oct 7, 2017 at 14:05
  • \$\begingroup\$ And Tuples is even shorter: Sort[Power@@@Prime@Range@#~Tuples~2][[#]]& \$\endgroup\$ Commented Oct 7, 2017 at 14:09

Jelly, 12 11 10 bytes

1 byte thanks to Dennis.


Try it online!


R + numbers, 57 bytes


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.


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))
 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!

  • \$\begingroup\$ use lists instead to save a byte: i=[] and ....i+=[r]*.... \$\endgroup\$ Commented Oct 9, 2017 at 11:58
  • \$\begingroup\$ 153 bytes by removing the second for \$\endgroup\$ Commented Oct 9, 2017 at 12:04
  • \$\begingroup\$ @FelipeNardiBatista I did not use lists, as in its first iteration the program was defining a function. Thanks for spotting and the further golf. \$\endgroup\$ Commented Oct 9, 2017 at 15:10
  • \$\begingroup\$ Can't you return r instead of i[p] \$\endgroup\$
    – ASCII-only
    Commented Apr 12, 2019 at 12:30
  • \$\begingroup\$ 137? \$\endgroup\$
    – ASCII-only
    Commented Apr 12, 2019 at 12:32

APL (Dyalog Extended), 15 bytes


Try it online!



              ⍵   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.

Pyth, 15 bytes


Try it here! or Verify more test cases.


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.

Javascript 137 133 bytes

for(i of p)
for(j of p)
return Object.keys(x)[n]}


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

  for(i of p)
  for(j of p)
    l= i**j
    if(++T>n &&x.length<l )
    x[l] = 1
  return Object.keys(x)[n]
  • 6
    \$\begingroup\$ 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. \$\endgroup\$
    – Gryphon
    Commented Oct 7, 2017 at 15:31
  • \$\begingroup\$ 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? \$\endgroup\$ Commented Oct 7, 2017 at 15:43
  • 3
    \$\begingroup\$ The solution may take any finite amount of time to run. The only goal is to make the code shorter. \$\endgroup\$
    – Gryphon
    Commented Oct 7, 2017 at 16:28

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).


Pyth - 13 bytes


Test Suite.


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 22 through 999999 132132 and stores it in a List, then sorts that List, and then gets the n'th item from that List.

EDIT: Instead of using 999999 which results in a List of 28,225 items, I now use 132132 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.)


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

PARI/GP, 48 bytes


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:


J, 21 bytes


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'

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.