# Prime Power Switch

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

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

xpression:`?`

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!