Wikipedia:Reference desk/Archives/Mathematics/2024 September 30

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 30

How to find max(x^y) for each r where x + y = r and x, y are positive integers

Drawing fractal canopy diagrams had me wondering for a given SVG file size, I could add more branches or more depth. Below are two examples:

2 branches, depth 12

4 branches, depth 8

To make the tree as dense as possible, I wish to maximise the number of leaf nodes. In other words, how can I find max(x^y) for each r where x + y = r and x, y are positive integers?

I realise I can use calculus but I'm unsure what equation I should differentiate.

Thanks, cmɢʟee⎆τaʟκ 00:50, 30 September 2024 (UTC)

Unfortunately, this is actually quite complicated. We can rewrite the problem as $\max(x^{r-x})$, and consider all real $x$ instead of just integers. Notice that $\ln(x^{r-x})=(r-x)\ln(x)$. Because $\ln$ is monotonic over $x$, $x^{r-x}$ is maximized when $(r-x)\ln(x)$ is. Its derivative is $-\ln(x)+(r-x)/x$, which is $0$ when $r=x+x\ln(x)$. This is a nice closed-form expression, but it's for $r$ in terms of $x$. Inverting it is complicated, but Wolfram Alpha gives us $x=r/W(er)$ where $W$ is the Lambert W function. While this is sort of a closed-form expression, it's still unfortunately annoying to work with since $W$ is implicitly defined as $W(z)=w\Leftrightarrow z=we^{w}$. In any case, $x=r/W(er)$ is irrational for all positive rational $r\neq 1$. The proof of this is annoying so I've put it below, but ultimately what it implies is that when $r>1$, as far as I can tell, the best you can do is either round $x$ for convenience, or take floor/ceiling of $x$ and compare values to get the max over integers.

Proof that $r/W(er)$ is irrational for positive rational $r\neq 1$

Suppose $r\in \mathbb {Q} ^{+}\backslash \{1\}$, and let $w:=W(er)$. $W(er)=0\Rightarrow r=0$ and $W(er)=1\Rightarrow r=1$, so $w\neq 0,1$ as well. By definition, $er=we^{w}$. Since $w\neq 0$, we can rearrange to get $r/w=e^{w-1}$. Lindemann's 1882 theorem implies that if $k$ is nonzero rational, then $e^{k}$ is not only irrational, but transcendental as well. If $w$ is rational, then since $w\neq 1$, $e^{w-1}$ is transcendental, while $r/w$ is rational, which is contradictory. $w$ must be irrational and is nonzero, so $r/w$ is irrational. We conclude that $r\in \mathbb {Q} ^{+}\backslash \{1\}$ implies $r/W(er)$ is irrational.

GalacticShoe (talk) 02:41, 30 September 2024 (UTC)

Here is a numerical recipe (Newton's method) for solving $r=x+x\ln x$ for real-valued $x$:

1. Set $x=9$
2. Iterate the replacement $x=x^{*}$ until convergence, where

   $x^{*}={\frac {x+r}{2+\ln x}}.$

In practice ($r<90$), two iterations will bring you close enough; then test $\lfloor x\rfloor$ and $\lceil x\rceil$ to get the optimal integer value.  --Lambiam 10:17, 30 September 2024 (UTC)

Thanks so much, @GalacticShoe and @Lambiam. I thought analytically I was heading into a dead end. Guess solving it iteratively is still the best for small values. cmɢʟee⎆τaʟκ 11:45, 30 September 2024 (UTC)

P.S. It seems there's an interesting trend:

x=1 for r=2	(1 term):	1¹.
x=2 for r=3 to 4	(2 terms):	2¹ and 2².
x=3 for r=5 to 7	(3 terms):	3², 3³ and 3⁴.
x=4 for r=8 to 11	(4 terms):	4⁴, 4⁵, 4⁶ and 4⁷.

x changes when r is the x–1th triangular number + 2. Serendipity? cmɢʟee⎆τaʟκ 17:06, 30 September 2024 (UTC)

Unfortunately, serendipity. The number of $r$ for each $x$ is the sequence OEIS:A108414. Although it starts with $1,2,3,4$, it quickly levels out. The inverse triangular number function you're looking for is $\lceil ({\sqrt {8r-7}}-1)/2\rceil \approx {\sqrt {2r}}$, while $x=r/W(er)$ grows faster than $r/\ln(r)$, which in turn grows faster than ${\sqrt {2r}}$, hence the number of terms slowing down in growth. GalacticShoe (talk) 03:46, 1 October 2024 (UTC)

Note that, unlike for T_n, these first differences in the r-values for which x changes do not only always increase but may even decrease.  --Lambiam 03:58, 1 October 2024 (UTC)

After some testing, it seems that rounding suffices at least for r < 100, possibly more. To simplify it, applying Newton's method twice, we can get this approximation which maximizes $x^{y}$ for these values of $x+y=r$:

$x=round\left({\frac {9+5.197225r}{2.373852+4.197225\ln(9+r)}}\right)$

GalacticShoe (talk) 04:14, 1 October 2024 (UTC)

Thanks so much, @Lambiam and @GalacticShoe. I much appreciate the time and effort you've put into it. Cheers, cmɢʟee⎆τaʟκ 20:17, 2 October 2024 (UTC)