Minimising $x+y$ in $x^y=a$

Question

Regarding this recent question, the question asks for minimizing $x+y$, given $x^y=a$, (for a constant real positive $a$) for real and positive values of $x$ and $y$. Now $(x,y)=\left(\exp\left({2W\left(\frac{\sqrt{\ln a}}{2}\right)}\right),\frac{\ln(a)}{2W\left(\frac{\sqrt{\ln a}}{2}\right)}\right)$ was the solution in that case. But I am curious to know what would happen if we restrict $x$ and $y$ to being positive integers (with $a$ being an integer greater than $1$) and then try to minimise $x+y$ under the given constraint.

I think that using the prime factorization of $a$, something like $\alpha^A\beta^B\gamma^C...$ (where $\alpha$, $\beta$ and $\gamma$ are primes), we might be able to come to a solution, but so far, I haven't been able to proceed. Perhaps something with the common divisors of the exponents in the prime factorization? (That might denote possible values of $y$)

I will link this question to the previous one too.

All help and clarification requests are welcome.

Edit: algorithmic answers like the one by @stef are perfectly acceptable, but I am looking for a more mathematical form.

Answer 1

Let $a>1$ be an integer, and let $x$ and $y$ be positive integers such that $x^y=a$. If $a$ is not a perfect power then it follows that $x=a$ and $y=1$, and so the minimum value of $x+y$ is $a+1$.

If $a$ is a perfect power then we can$^{1}$ write $a=b^c$ for integers $b$ and $c$ such that $b$ is not a perfect power. Then $$x=b^d\qquad\text{ and }\qquad y=\frac cd,$$ for some divisor $d$ of $c$, and so we want to minimize $b^d+\tfrac cd$. Of course $b>1$ because $a>1$, and for $$f(t):=b^t+\frac ct\qquad\text{ we have }\qquad f'(t)=b^t\ln b -\frac{c}{t^2},$$ and so $f'(t)=0$ if $f$ is minimal at $t$, because $f$ is continuous on the positive reals. Then $t^2b^t\ln b=c$, so $$t^2e^{t\ln b}=\frac{\ln c}{\ln b}\qquad\text{ and so }\qquad we^w=\frac12\sqrt{(\ln b)(\ln c)},$$ where $w=\tfrac12t\ln b$. This shows that the minimum of $f$ over the positive reals is at $$t_0=\frac{2}{\ln b}W\left(\frac12\sqrt{(\ln b)(\ln c)}\right).$$ Next note that $f$ is a convex function on the positive reals because $$f''(t)=b^t(\ln t)^2+\frac{2c}{t^3},$$ which is strictly positive on the positive reals. It follows that the minimum of $f$ over the positive divisors of $c$ one of the two divisors nearest to the real minimum $t_0$. One can now simply check and compare these two divisors.

---

1: https://stackoverflow.com/questions/39190815/how-to-make-perfect-power-algorithm-more-efficient

Answer 2

A programmatic solution in python, iterating on the possible values of y between 1 and $\log_2(n)$:

from sympy.core.power import integer_nthroot

def clog2(n):
    """Ceiling of log2, https://stackoverflow.com/a/71122440/3080723 """
    if n <= 0:
        raise ValueError("domain error")
    return (n-1).bit_length()

def all_solutions(n):
    """All solutions (x, y) of x**y == n"""
    for y in range(1, clog2(n) + 1):
        x, is_exact = integer_nthroot(n, y)
        if is_exact:
            yield (x, y)

def smallest_sum_solution(n):
    """(x,y) that minimises x+y under constraint x**y == n"""
    return min(all_solutions(n), key=sum)

Testing:

for n in [2**6, 2**10, 6**40, 3**700]:
    x,y = smallest_sum_solution(n)
    print(f'{x}**{y} == {n}')

# 4**3 == 64
# 4**5 == 1024
# 6**40 == 13367494538843734067838845976576
# 81**175 == 9657802140591758043812442031522928437371194636776843099838260055342219733688083412928987321682880332396927287242805644548901834234972280564072880735127568242460394336247761481999342991210220561304479523441956128812808859393388776484808811910915541232693035534590226711458043242074211993816993921587180335757972232760635320184916654001
```