Prime Power Switch

Question

Input: A positive integer n=p^q where p and q are prime.

Output: Output the result of q^p

Test cases (in, out):

4, 4
8, 9
25, 32
27, 27
49, 128
121, 2048
125, 243
343, 2187
1331, 177147
3125, 3125, 
16807, 78125, 
823543, 823543
161051, 48828125
19487171, 1977326743

Scoring:
This is code-golf, so may the shortest code in bytes win! Input and output maybe in any reasonable format suitable to your language.

Related:
Recover the power from the prime power
Recover the prime from the prime power

Answer 1

Python 2, 56 bytes

n=input()
p=2
while n%p:p+=1
P=p**n-1
print(n**n/P%P)**p

Try it online!

We first find the prime \$p\$ for which \$n=p^q\$ by incrementing \$p\$ until we get a divisor on \$n\$. After that, we find the exponent \$q\$ with a mathematical trick first discovered by Sp3000 and used in Perfect power logarithms on Anarchy Golf.

We note that $$ \frac{n-1}{p-1} = \frac{p^q-1}{p-1} = 1 + p + p^2 \dots+p^{q-2}+p^{q-1}$$ Working modulo \$p-1\$, we have \$p \equiv 1\$, so each of \$q\$ the summands on the right hand side equals 1, and so: $$ \frac{n-1}{p-1} \equiv q \space \bmod (p-1)$$

We'd now like to extract \$q\$. We'd like to get there by applying the modulus operator %(p-1) to the left hand side. But this requires that \$q<p-1\$, which is not guaranteed, or we'll get a different value of q%(p-1).

Fortunately, we can get around this with one more trick. We can replace \$n\$ with \$n^c\$ and \$p\$ with \$p^c\$ for some positive number \$c\$, and still have \$n^c=(p^c)^q\$. Since the exponent \$q\$ relating them is unchanged, we can extract it as above, but make it so that \$q<p^c-1\$. For this, \$c=n\$ more than suffices and is short for golfing, though it makes larger test cases time out.

Answer 2

Bash + Linux utils, 17

factor|dc -e?zr^p

• factor takes a number as input and factorizes it. The output is the input number, followed by a colon, followed by a spaced-separated list of all the prime factors.
• This list is piped to dc which evaluates the following expression:
  • ? reads the whole line as input. dc cannot parse the input number followed by the colon, so it ignores it. Then it parses all the space-separated prime factors and pushes them to the stack.
  • z takes the number of items on the stack (number of prime factors) and pushes that to the stack
  • r reverses the top two items on the stack
  • ^ exponentiates, giving the required answer
  • p prints it.

Try it online!

Answer 3

MATL, ⁸ 5 bytes

-3 bytes thanks to @LuisMendo

&YFw^

Try it online!

Answer 4

05AB1E, 5 bytes

ÓOsfm

Try it online!

Commented:

        # implicit input            25
Ó       # prime factor exponents    [0, 0, 2]
 O      # sum                       2
  s     # swap (with input)         25, 2
   f    # unique prime factors      [5], 2
    m   # power                     [32]

Answer 5

J, ⁹ 8 bytes

2^~/@p:]

Try it online!

• 2 p: ] returns a list of primes and their exponents.
• ^~/@ then swap the arguments and exponentiate

Answer 6

Python 2, 62 bytes

n=input()
p=2
q=-1
while n%p:p+=1
while n:n/=p;q+=1
print q**p

Try it online!

Answer 7

C (gcc) -lm, 47 bytes

p;f(n){for(p=1;n%++p;);p=pow(log(n)/log(p),p);}

Try it online!

Answer 8

Brachylog, 6 bytes

ḋ⟨l^h⟩

Try it online! On the prime decomposition ḋ (like [5, 5]), length l ^ first element h.

A nicer and more Brachylog-y solution, that is one byte longer:

 ~^ṗᵐ↔≜^

Try it online! Reverse ~^ to get two Numbers [A,B] so that Input = A^B, while both are prime ṗᵐ. Flip ↔ the list to [B,A], actually find the numbers ≜ and output B^A.

Answer 9

Japt, 6 bytes

k
ÊpUg

Try it

k\nÊpUg     :Implicit input of integer U
k           :Prime factors
 \n         :Reassign to U
   Ê        :Length
    p       :Raised to the power of
     Ug     :First element of U

Answer 10

R, 37 bytes

log(n<-scan(),p<-(b=2:n)[!n%%b][1])^p

Try it online!

My best effort, sadly 1-byte longer than the Xi'an's much-cleverer R answer, but posting anyway in the competitive spirit.

Uses the straightforward approach of finding the prime factor (p<-(b=2:n)[!n%%b][1]), then the exponent (log(n,p)) and finally raising the exponent to the power of the factor (log(n,p)^p).

Answer 11

JavaScript (ES7),  47 46  44 bytes

Uses a recursive function that first looks for the smallest divisor \$k\ge2\$ of \$n\$ and then counts how many times \$n\$ can be divided by \$k\$. The result is raised to the power of \$k\$.

n=>(k=2,g=_=>n%k?n>1&&g(k++):1+g(n/=k))()**k

Try it online!

Commented

n => (          // main function taking n
  k = 2,        // start with k = 2
  g = _ =>      // g is a recursive function ignoring its input
    n % k ?     //   if k is not a divisor of n:
                //     this point of the code is reached during the first step
                //     of the algorithm; but it's also reached on the last
                //     iteration when n = 1, which is why ...
      n > 1 &&  //     ... we test whether n is greater than 1 ...
        g(k++)  //       ... in which case we do a recursive call with k + 1
    :           // else (k has been found):
      1 +       //   add 1 to the final result
      g(n /= k) //   and do a recursive call with n / k
)()             // initial call to g
** k            // raise the result to the power of k

Answer 12

R 36 28 1 36 bytes

Using the fact that exactly p powers of n are factors of n^p:

sum(a<-!max(b<-2:scan())%%b)^b[a][1]

Try it online!

but using a function definition does better (by moving function(m) to the header part!)

f=function(m)
sum(a<-!m%%(b<-2:m))^b[a][1]

Try it online!

with the ultimate improvement in length (1 byte!) produced by defining everything as the function argument (in the header of Try It Online).

f=function(m,b=2:m,a=!m%%b,d=sum(a)^b[a][1]) d

but this is not keeping with the code golf spirit!

Answer 13

Haskell, 42, 39 bytes

f x|r<-[2..x]=[z^w|z<-r,w<-r,w^z==x]!!0

Try it online!

• 3 bytes saved by @xnor

Answer 14

Ruby, 56 bytes

n=gets.to_i
p=2
p+=1while n%p>0
w=p**n-1
p (n**n/w%w)**p

Port of xnor's Python 3 answer.

Try it online! (headers and footers courtesy of ovs. :D)

Answer 15

Vyxal, 5 bytes

ǐ₌Lhe

Try it Online!

How?

ǐ₌Lhe
ǐ     # Prime factors with duplicates
 ₌    # Apply both of next two elements and push both results to the stack:
  L   #  Length
   h  #  First item
    e # Exponentiate these two (length ^ first item)

Answer 16

Wolfram Language (Mathematica), 24 bytes

#2^#&@@@FactorInteger@#&

Try it online!

Returns {q^p}, a singleton list.

        FactorInteger@# (* {{p,q}} *)
#2^#&@@@                (* { q^p } *)

Answer 17

Retina, 59 bytes

.+
*
~`(?=(__+?)\1*$)((?=(_+)(\3+)$)\4)+
_+¶$$.($.1*$($#2$*

Try it online! Link includes faster test cases. Explanation:

.+
*

Convert the input to unary.

(?=(__+?)\1*$)((?=(_+)(\3+)$)\4)+

First, find the smallest nontrivial factor, which will necessarily be p. Secondly, count the number of times q that n can be replaced with its largest proper factor. (The proper factor will be n/p on the first pass and eventually decrease to 1 which is left unmatched but this doesn't affect the result.)

_+¶$$.($.1*$($#2$*

Generate a Retina stage which takes n as input and calculates (in decimal) the result of multiplying 1 by q p times, thus calculating q^p.

~`

Evaluate the resulting code, thus calculating the desired result.

Answer 18

Scala, 63 bytes

n=>2 to n find(n%_<1)map{p=>import math._;pow(log(n)/log(p),p)}

Try it online!

Finds the first factor of n, which must be p because n is a prime power, then finds \$\log_p(n)^p\$. Returns an Option[Double] that's a Some[Double] if the input is valid.

Answer 19

Jelly, 6 bytes

ÆFẎṪ*$

Try it online!

Jelly, 6 bytes

ÆFẎ*@Ɲ

Try it online!

Jelly, 6 bytes

ÆfL*ḢƊ

Try it online!

A 5-byter feels possible...

Answer 20

J, 8 bytes

2^~/@p:]

Try it online!

J has a built-in that gives the prime factorization of a given integer in prime-exponent form. Then it's just a matter of applying exponentiation in reverse (^~) between the two numbers.

(Happens to be the same as Jonah's answer; somehow didn't notice before I submitted the answer...)

---

Because it is also solvable using f&.g ("Under"; do action g, do action f, then undo action g), here are some interesting ones:

10 bytes

|.&.(2&p:)
     2&p:  Prime factorization into prime-exponent form
|.         Swap the prime and exponent
  &.       Undo `2&p:`; evaluate the "prime" raised to "exponent"

Try it online!

10 bytes

({.##)&.q:
        q:  Prime factorization into plain list of primes
 {.         Head (prime)
   #        Copies of
    #       Length (exponent)
 {.##       Essentially swap the role of prime and exponent
      &.    Undo `q:`; product of all "primes"

Try it online!

Answer 21

Alice, 13 bytes

/ \f~#oE/
 i@

Try it online!

Explanation:

/           Switch to Ordinal mode
 i          Push the input as a string
  \         Switch to Cardinal mode
   f        Pop n, implicitly convert n to an integer, 
            and push the prime factors of n as pairs of prime and exponent
    ~       Swap the top two elements of the stack
     #      Skip the next command
       E    Pop y, pop x. If y is non-negative, push x ^ y
        /   Switch to Ordinal mode
      o     Pop s, then output s as a string.
    ~       Swap the top two elements of the stack.
  \         Switch to Cardinal mode
  @         Terminate the program

Answer 22

Forth (gforth), 85 bytes

: f dup 2 do dup i mod 0= if i leave then loop tuck swap s>f fln s>f fln f/ s>f f** ;

Try it online!

Works like Noodle9's C answer. Takes an integer and returns a floating-point number on the FP stack.

How it works

: f ( n -- float )
  dup 2 do           \ loop from i = 2..n-1
    dup i mod 0= if  \ if n % i == 0
      i leave        \ ( n p ) we found p; leave the loop
    then             \ end if
  loop               \ end loop
  tuck swap          \ ( p p n )
  s>f fln s>f fln    \ ( p F:ln(n) F:ln(p) )
  f/                 \ ( p F:q ) q = ln(n)/ln(p)
  s>f f**            \ ( F:q**p )
;

Answer 23

Pyth, ⁷ 6 bytes

-1 byte thanks to @FryAmTheEggman

^lPQhP

Try it online!

Explanation

^lPQhP
 l      # length of
  PQ    # prime factors of input
^       # raised to power of
    hP  # first element in prime factors of input

Answer 24

Io, 57 55 bytes

^{Fixed a bug kindly pointed out by @DominicvanEssen}

method(i,p :=2;while(i%p>0,p=p+1);i log(p)floor pow(p))

Try it online!

Answer 25

APL (NARS2000 0.5.14), 9 characters 8 characters (thanks to gurus in APL Orchard):

(⍴*1∘↑)π

How it works:

Take input 8 as example. π breaks down 8 into vector of prime factors 2 2 2. The fork ⍴*1∘↑ takes one element from 2 2 2 as exponent, applies this to length of vector 2 2 2 which is 3, giving 3^2 = 9.

Answer 26

Factor + math.primes.factors, 34 bytes

[ factors dup length swap last ^ ]

Try it online!

Answer 27

Desmos, 61 10+38=48 bytes

l=log_m(n)
\sum_{m=2}^{n-1}(sign(l-ceil(l))+1)l^m

View it online (note that large values may fail because Desmos doesn't handle large numbers well)

I decided to revisit this because I felt like outgolfing myself, and I remember this having potential inefficiencies. I could only find one improvement, but it seemed substantial enough for the edit.

Input is via the variable n, output via the second calculation. If taking input via a variable feels wrong, feel free to add two bytes for a n=.

Not horribly efficiently golfed. About 70% of the code is just dedicated to finding one factor, and there's surely a more efficient way to factor numbers in Desmos, but I haven't found one yet, and Desmos is lacking in built-ins relating to factorization or prime numbers.

Instead, we simply observe that since \$p\$ and \$q\$ are prime, then \$p*p...*p\$ must be the only factorization of \$n\$ which can be represented with integer values, because the list of \$p\$s cannot be split into any other even groups. Therefore, we can just interate through all integers \$m \in 2,3,...,n-1\$ and find the value satisfying \$log_mn \in \mathbb{Z}\$ (the set of integers). We do this in the code using sign(log_m(n)-ceil(log_m(n)))+1, which gives us a nice 1 when integeral and 0 when not. We multiply by log_m(n)^m to give us our new value, and add up the results for all values 2 through n-1 to single out the answer.

Answer 28

Husk, 5 bytes

§^←Lp

Try it online!