16
\$\begingroup\$

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 ,lowest score in bytes wins!

\$\endgroup\$

16 Answers 16

8
\$\begingroup\$

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

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

Actually, 14 bytes

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

;ur♂P;∙⌠iⁿ⌡MSE

Ungolfing

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

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!

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

Jelly, 12 11 10 bytes

1 byte thanks to Dennis.

ÆN€*þ`FṢị@

Try it online!

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

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ f=(!!)[x|x<-[2..],or[y^e==x|y<-p x,e<-p x]] saves 10 bytes. \$\endgroup\$ – Lynn Oct 7 '17 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 Oct 9 '17 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 Oct 9 '17 at 9:01
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ use lists instead to save a byte: i=[] and ....i+=[r]*.... \$\endgroup\$ – Felipe Nardi Batista Oct 9 '17 at 11:58
  • \$\begingroup\$ 153 bytes by removing the second for \$\endgroup\$ – Felipe Nardi Batista Oct 9 '17 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\$ – Jonathan Frech Oct 9 '17 at 15:10
  • \$\begingroup\$ Can't you return r instead of i[p] \$\endgroup\$ – ASCII-only Apr 12 at 12:30
  • \$\begingroup\$ 137? \$\endgroup\$ – ASCII-only Apr 12 at 12:32
2
\$\begingroup\$

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

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]
}
\$\endgroup\$
  • 5
    \$\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 - Reinstate Monica Oct 7 '17 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\$ – DanielIndie Oct 7 '17 at 15:43
  • 2
    \$\begingroup\$ The solution may take any finite amount of time to run. The only goal is to make the code shorter. \$\endgroup\$ – Gryphon - Reinstate Monica Oct 7 '17 at 16:28
2
+100
\$\begingroup\$

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

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

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

Pyth - 13 bytes

e.f&P_lPZ!t{P

Test Suite.

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

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

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

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

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'
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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