# Prime Power Switch

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 , so may the shortest code in bytes win! Input and output maybe in any reasonable format suitable to your language.

• That q is a prime does not seem to matter. Sep 2, 2020 at 5:52
• Fun fact: of course if p = q, then p^q = q^p. But if p != q, then the only pair of integers satisfying p^q = q^p is (2, 4), with 2^4 = 4^2 = 16.
– Stef
Sep 2, 2020 at 9:36
• @Stef Can you link a proof of that? Can't seem to find the right google keywords Sep 2, 2020 at 17:57
• @RedwolfPrograms From $p^q = q^p$, taking the natural log of both sides gives $q \ln p = p \ln q$, or $q / \ln q = p / \ln p$. So, we want two distinct positive integers that map to the same value under $f(x) = x / \ln x$. Looking at the graph of this function for $x>1$, we see it has a single minimum between 2 and 3 (actually $e$ as some calculus confirms). So, $p$ and $q$ must be on opposite sides of this minimum. Since they're integers and above 1, the lower one must be 2, and its matching value is 4.
– xnor
Sep 2, 2020 at 22:45
• @xnor Ah, thanks! A really simple answer to something I'd never really thought about before. Sep 3, 2020 at 0:30

# 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, 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. For this, $$\c=n\$$ more than suffices and is short for golfing, though it makes larger test cases time out.

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

# MATL, 8 5 bytes

-3 bytes thanks to @LuisMendo

&YFw^


Try it online!

• I think YfY'w^ should work for 6. Sep 1, 2020 at 18:59
• Or &YFw^ for 5 Sep 1, 2020 at 22:11

# 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      , 2
m   # power                     


# J, 9 8 bytes

2^~/@p:]


Try it online!

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

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

# C (gcc)-lm, 47 bytes

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


Try it online!

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

# 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


# R, 37 bytes

log(n<-scan(),p<-(b=2:n)[!n%%b])^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]), then the exponent (log(n,p)) and finally raising the exponent to the power of the factor (log(n,p)^p).

# 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
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


# R36281 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]


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]


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]) d


but this is not keeping with the code golf spirit!

• It's a beautiful approach, and better than my own best effort, but unfortunately I think you need to include the definition function(m) or the function(m,b=2,...) as part of the byte count. Sep 2, 2020 at 7:43
• @DominicvanEssen: this was rather a tongue-in-cheek remark. Using function is the code worsens things up: even pryr::f(sum(a<-!m%%(b<-2:m))^b[a]) does not reach 36 bytes... Sep 2, 2020 at 8:30
• by the way, R is the language of the month, so you might want to add this to the newly-created list of R answers/challenges/tips in September 2020 (see the link). Sep 3, 2020 at 8:19

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


Try it online!

• 3 bytes saved by @xnor
• You can bind r on the outside in a guard as f x|r<-[2..x]=....
– xnor
Sep 2, 2020 at 7:27

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

• I’m no expert in Ruby, so there might be a better way, but here is a working test setup: tio.run/…
– ovs
Sep 13, 2020 at 6:44
• Perfect! Just what I needed. Thank you! Sep 13, 2020 at 6:54

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


# Wolfram Language (Mathematica), 24 bytes

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


Try it online!

Returns {q^p}, a singleton list.

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


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

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

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

# 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
#        Copies of
#       Length (exponent)
{.##       Essentially swap the role of prime and exponent
&.    Undo q:; product of all "primes"


Try it online!

# 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


# 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 )
;

• <sup>woah..</sup> Nov 5, 2020 at 10:36

# Pyth, 7 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

• I think using J wastes a byte here: ^lPQhP. Sep 1, 2020 at 20:13

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

• Do you maybe have your i and p the wrong way around? Sep 5, 2020 at 16:14

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.

• (≢*⊃)⍭ In dyalog extended Sep 28, 2020 at 11:19
• I've learned from APL Orchard gurus that the outer ∘ can be saved, which reduces my answer to 8-char. Translating your (≢*⊃)⍭ into NARS2000 would be (≢*↑)π Sep 29, 2020 at 15:04

# Factor + math.primes.factors, 34 bytes

[ factors dup length swap last ^ ]


Try it online!

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

• Can be 37 bytes through various golfs. The most significant golf is replacing sign(l-ceil(l))+1 with 0^{mod(l,1)}, which also gives 1 when l is an integer, and 0 if not. May 22, 2022 at 22:03

# Husk, 5 bytes

§^←Lp


Try it online!