19
\$\begingroup\$

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.

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

\$\endgroup\$
  • 1
    \$\begingroup\$ That q is a prime does not seem to matter. \$\endgroup\$ – Xi'an Sep 2 at 5:52
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Stef Sep 2 at 9:36
  • \$\begingroup\$ @Stef Can you link a proof of that? Can't seem to find the right google keywords \$\endgroup\$ – Redwolf Programs Sep 2 at 17:57
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – xnor Sep 2 at 22:45
  • \$\begingroup\$ @xnor Ah, thanks! A really simple answer to something I'd never really thought about before. \$\endgroup\$ – Redwolf Programs Sep 3 at 0:30

25 Answers 25

4
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
15
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

MATL, 8 5 bytes

-3 bytes thanks to @LuisMendo

&YFw^

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I think YfY'w^ should work for 6. \$\endgroup\$ – Giuseppe Sep 1 at 18:59
  • 2
    \$\begingroup\$ Or &YFw^ for 5 \$\endgroup\$ – Luis Mendo Sep 1 at 22:11
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

C (gcc) -lm, 47 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Dominic van Essen Sep 2 at 7:43
  • 1
    \$\begingroup\$ @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][1]) does not reach 36 bytes... \$\endgroup\$ – Xi'an Sep 2 at 8:30
  • 2
    \$\begingroup\$ 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). \$\endgroup\$ – Dominic van Essen Sep 3 at 8:19
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You can bind r on the outside in a guard as f x|r<-[2..x]=.... \$\endgroup\$ – xnor Sep 2 at 7:27
3
\$\begingroup\$

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)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I’m no expert in Ruby, so there might be a better way, but here is a working test setup: tio.run/… \$\endgroup\$ – ovs Sep 13 at 6:44
  • \$\begingroup\$ Perfect! Just what I needed. Thank you! \$\endgroup\$ – DrQuarius Sep 13 at 6:54
2
\$\begingroup\$

Wolfram Language (Mathematica), 24 bytes

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

Try it online!

Returns {q^p}, a singleton list.

        FactorInteger@# (* {{p,q}} *)
#2^#&@@@                (* { q^p } *)
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ I think using J wastes a byte here: ^lPQhP. \$\endgroup\$ – FryAmTheEggman Sep 1 at 20:13
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ (≢*⊃)⍭ In dyalog extended \$\endgroup\$ – rak1507 Sep 28 at 11:19
  • \$\begingroup\$ 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 (≢*↑)π \$\endgroup\$ – jimfan Sep 29 at 15:04
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Husk, 5 bytes

§^←Lp

Try it online!

| improve this answer | |
\$\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.