I think taking logs is an unnecessary indirection in the given proof. If n^m = m^n then raising both sides to the power of 1/(nm) gives us n^(1/n) = m^(1/m). So we are looking for two distinct positive integers at which the function x ↦ x^(1/x) takes the same value. The rest of the proof then goes as before.
Differentiating the above function yields (1/x^2)(1-log(x))x^(1/x), which is positive when log(x) < 1 and negative when log(x) > 1. So the function has a maximum at e and decreases on either side of it. Therefore one of our integers must be less than e, and the other greater than it. For the smaller integer there are only two possibilities, 1 and 2. Using 1 doesn't give a solution since the equation x^(1/x) = 1 only has the solution 1. So the only remaining possibility for the smaller number is 2, which does yield the solution 2^4 = 4^2. Since x^(1/x) is strictly decreasing when x > e, there can't be any other solutions with the same value.
Logs will appear no matter what, at some point in the line of reasoning. They are only held back until differentiating in this approach. I think the expression for the derivative of logn/n was much nicer to grapple with.
It is a sort of automatic reflex when encountering stuff like $x^x$ in such contexts like here in mathematics to take logarithms. Working with logarithms is usually much simpler and easier to understand when having variables in both the exponent and the base, both for technical reasons (the logarithms will not be avoided anyway, as the other commenter said) and for intuition-gaining reasons. Multiplication of two functions is more intuitively understood (as one can work stuff such as signs, monotonicity etc easily) than exponentiation involving one function in the base and one in the exponent.
Since m and n are distinct, we may assume that m > n >= 2. From the equation and unique factorization, we know that n divides m, so write m = nd.
Then (nd)^n = n^(nd).
Hence d^n = n^{n(d-1)}, which yields d = n^{d-1} >= 2^{d-1}.
Claim: if k is an integer greater than or equal to 3, then k < 2^{k - 1}.
Proof: the base case is clear: 3 < 4. Suppose k > 3 and k - 1 < 2^{k - 2}.
Then k < 2^{k-2} + 1 <= 2^{k-1}, where the last inequality holds because 2^{k-1} - 2^{k-2} = 2^{k-2} >= 1. QED
So, d must be less than 3. Since m = nd and m and n are distinct, d is not 1, so d = 2.
Since d = n^{d-1} and d - 1 = 1, we have n = d, so m = 4.
How exactly do we know that n divides m? I think it's clear that they have the same prime factors, but it's not clear why they couldn't be like n = 12 and m = 18.
I think it's even simpler after you figured out that m = kn = n^k => n is an integer > 1 and equal to the (k-1)-th root of k where k is an integer > 1.
The only integer (k-1)-th root of k is 2 for k = 2. Thus, n = 2, k = 2, m = 4.
I am not a mathematician, but in the discrete domain of integers:
1) you have two functions, essentially we look for where the two 3d space surfaces intersect, if z is taken as the result for each equation.
2) the integers "are disctinct", so (0,0) and (1,1) are out, plus (2,2) (3,3) etc. Basically a whole linear diagonal in the instersection of both 3d spaces is excluded (why though, to what useful end?)
3) Starting points for the ranges is therefore (0,1) and (1,0)
4) 1^y is always 1, and x^0 is always 1 so there is a constant starting value of 1 both on both axis
5) but x^y will always be larger than y^x, for y>x and x^y > y^x
(prove this by taking the first derivative to get rate of change. Do you use Laplace z domain for discrete, instead of s for continuous?)
6) and the converse to 5.
So once you have found one solution, you know to stop looking, the two surfaces keep diverging from each other.
Why resort to the continuous domain to solve a problem n the discrete, is this even a valid approach?
eg Is there a formal proof that says integers strictly follow that same rules as the continuous domain, just as a subset? I'm interested.
Does this come under group theory, a set with an applied operation?
As I said I am not a mathematician, I am an electrical engineer so probably one of the worst abusers of pure math in a formal sense, but the more I think about this the more questions this raises in my thinking.
> 5) but x^y will always be larger than y^x, for y>x and x^y > y^x (prove this by taking the first derivative to get rate of change. Do you use Laplace z domain for discrete, instead of s for continuous?)
This is false, though! Or, it's almost always true, but there are some exceptions. We of course have an exception at (2,4) and (4,2), where they're equal, and of course at (n,n), where they're obviously equal. And of course 0's and 1's will cause problems for you.
But also, most interestingly, there's an exception at (2,3) and (3,2)! 2<3, and yet, 3^2 > 2^3. Any proof has to account for this!
(There's a fair bit I could say about this exception, but perhaps I should just let you think about it instead. :) )
> Why resort to the continuous domain to solve a problem n the discrete
Because oftentimes this is easier. (In a number of cases it's much easier.) Also... you did this? Like to the extent that your step (5) is valid, you seem to have "proven" it by using the first derivative. That's a continuous tool! I'm not sure what you're talking about with the "Laplace z domain". Or are you using "first derivative" to mean "first difference", or something?
> is this even a valid approach?
Yes, why wouldn't it be? In fact this is actually one of the big reasons for introducing larger number systems, that they let you prove things about the original smaller number system. The rational numbers let you prove things about the integers; the complex numbers let you prove things about the reals; the real numbers and p-padic numbers let you prove things about the rationals; etc. (The integers let you prove things about the whole numbers!)
Proving statements about integers by means of complex numbers is a whole field in itself, i.e., analytic number theory. And in the case of Goodstein's theorem, one famously proves a statement about the whole numbers by passing to the ordinals...
A subset won’t have more solutions than its containing set; but it may have fewer.
Many problems are easier to solve in the reals (due to being complete), and you can then restrict that solution to your (sub)set of interest — in this case, the integers.
You see the same thing with Pythagorean triples being simpler to solve by doing the math over the complex numbers and then restricting your answers.
I'm trying to understand 5). If you're claiming that both (A) y > x, and (B) x^y > y^x hold, then x^y > y^x ("will always be larger") holds. You're satisfying your claim by assumption. Nothing new is deduced.
However, if only A) needs to be satisfied: y = 3, x = 2 is a counterexample, as x^y = 2^3 = 8 < 9 = 3^2 = y^x.
edit: looks like someone had the same thought as me as I was typing my reply!
I am not a mathematician either, I always maintained the university made a mistake granting make a math teacher degree :) It was also long ago enough a lot of you weren't even alive and I haven't done any such work in a quarter century. Nonetheless...
> but x^y will always be larger than y^x, for y>x and x^y > y^x (prove this by taking the first derivative to get rate of change. Do you use Laplace z domain for discrete, instead of s for continuous?)
I am struggling to follow what are you saying here
>
Why resort to the continuous domain to solve a problem n the discrete, is this even a valid approach?
I can't make heads or tails of this question. The proof says, correctly, for all (real) x != y, x < y solutions it is true that 0<x<e and e<y. He found this by investigating the derivative and establishing the monotonically increasing / decreasing nature of the function. Only after finding this out using does he go back to the original question: what integer x could be? Since he restricted x to be 0 < x < e , we only need to investigate the case of 1 and 2.
For today’s interesting problem, we are looking to find all positive integer pairs n and m which satisfy the equation above, when n and m are distinct. If we play around with small n and m we can quickly see that 2⁴ = 16 = 4² , so the pair 2 and 4 are certainly one solution. Actually, it is the only solution.
I noticed this interesting fact during my secondary school education. Additionally you can use this to prove that e is the point where a change in the exponent causes a larger result than a change in the base. E.g. (x+d)^y > x^(y+d) when y >= e for any real value d.
Alternative proof without any real numbers, logs or the like:
After relabeling we may assume n<m.
Step 1: We claim that there exists a natural number k such that m=kn.
Write the equation as
n^n n^(m-n) = m^n
n^(m-n) = (m/n)^n
The left-hand-side is always an integer. The right-hand-side is an integer if and only if such a factor k exists.
Step 2: Inserting this ansatz, we may take n-th roots and reduce the problem to n^k =k n.
Step 3: Monotonicity. Clearly we have equality for k=1.
We claim that the difference n^k-kn strictly increases with k for fixed n unless n=2, k=1. That claim in particular gives the result.
We prove this by induction in k. That is, suppose that n^k\geq kn holds for all k\leq K, then
n^(K+1) = n n^K \geq n K n \geq Kn +Kn \geq Kn +n = (K+1)n.
The second inequality is strict unless n=2 and the last one is strict unless K=1.
(m/n)^n is only an integer if m/n is an integer: true but this is quite a big piece of mathematics on its own.
The proof that no rational number squares to 2 is a famous result of number theory. That no rational non-integer, raised to any power, is any integer, surely has to be justified here.
Showing the graph of the functions without showing that there are only two possible integers to work with (since we're looking for solutions in ℕ, not ℝ) on the left side of the maximum feels like missing the most important part of the drawing things out. You can even leave the y axis unlabeled, but label the x-axis (especially since we've already determined f(1)=0) and draw some dots on the curve to show that those are the only values that can be in our solution space.
"There's a maximum at e, so the only two possible values on the left of e that can be used in these pairs are 1, and 2. But really there's only one, because 1 is the power identity, so we can't use that. If there is a solution, it has to use 2."
Which means we're solving one function for one unknown, in the natural numbers. 2ⁿ=n² gives n=4. We have found the only pair of integers that satisfies our constraint function.
Why was "Distinct Positive" left out of the submission title? The submission smells like clickbait without it, yet it is part of the actual article title and the article appears to be submitted by the author.
I like problems like these. I was posed one at the end of a 'Constructive Mathematics' course I took at Stanford. Eight and nine are right next to each other (+-1). One is a cube, and the other is a square.
Do a cube and a square land next to each other ever again?
Note it's not asking if they land on each other, that is trivial - 1000000 is 100^3 and 1000^2.
My solution was to form an equation, divide by x and solve the resulting quadratic equation. It produce new solutions: 0 and 1, 0 and -1! As well as 2 and 3. So I was encouraged to say no, those were the only solutions.
I was following until the very end. This felt very handwavy:
>Now, since e is somewhere between 2 and 3, we have to conclude that n must be 2. Further, from our curve, we can see that there can only be one other value of x for which (lnx)/x = (ln2)/2, and since we know that 2⁴ = 4², we know that the other integer must be 4.
Is this sort of thinking something that could be justifiably written in a real proof? Sure, conveniently fishing out 2 as n seems to narrow down the search space for m, but I'd imagine this wouldn't work for harder problems
Really fun article to read, and I'm not even that interested in math.
Somewhat unrelated, but I cant help but ask why authors are still using Medium as opposed to Substack or some other alternative. The hook of the post happened to interest me to the extent where I went looking for an un-auth-walled version, but I'm sure there have been countless cases where I have simply abandoned it because I wasn't invested enough to seek out the mirrors -- and I'm sure no author wants that.
Similar pathway for classic high school problem I really enjoyed about finding which one is bigger e^pi or pi^e. I was unreasonably pleased with that problem. Won't spoil.
I'm not formally trained Mathematician, but I think this is not an analytic proof - it lacks rigour. It is more a graphical approach that appeals to the reader's intuition. I could be wrong here though.
Second, I really really thought the last graph will include y = x line and was very surprised to not see it :)
[+] [-] OscarCunningham|2 years ago|reply
Differentiating the above function yields (1/x^2)(1-log(x))x^(1/x), which is positive when log(x) < 1 and negative when log(x) > 1. So the function has a maximum at e and decreases on either side of it. Therefore one of our integers must be less than e, and the other greater than it. For the smaller integer there are only two possibilities, 1 and 2. Using 1 doesn't give a solution since the equation x^(1/x) = 1 only has the solution 1. So the only remaining possibility for the smaller number is 2, which does yield the solution 2^4 = 4^2. Since x^(1/x) is strictly decreasing when x > e, there can't be any other solutions with the same value.
[+] [-] frodetb|2 years ago|reply
[+] [-] freehorse|2 years ago|reply
[+] [-] onion2k|2 years ago|reply
[+] [-] bustermellotron|2 years ago|reply
Since m and n are distinct, we may assume that m > n >= 2. From the equation and unique factorization, we know that n divides m, so write m = nd.
Then (nd)^n = n^(nd). Hence d^n = n^{n(d-1)}, which yields d = n^{d-1} >= 2^{d-1}.
Claim: if k is an integer greater than or equal to 3, then k < 2^{k - 1}.
Proof: the base case is clear: 3 < 4. Suppose k > 3 and k - 1 < 2^{k - 2}. Then k < 2^{k-2} + 1 <= 2^{k-1}, where the last inequality holds because 2^{k-1} - 2^{k-2} = 2^{k-2} >= 1. QED
So, d must be less than 3. Since m = nd and m and n are distinct, d is not 1, so d = 2. Since d = n^{d-1} and d - 1 = 1, we have n = d, so m = 4.
[+] [-] OscarCunningham|2 years ago|reply
[+] [-] civilized|2 years ago|reply
[+] [-] giik|2 years ago|reply
The only integer (k-1)-th root of k is 2 for k = 2. Thus, n = 2, k = 2, m = 4.
[+] [-] andygeorge|2 years ago|reply
[+] [-] airbreather|2 years ago|reply
I am not a mathematician, but in the discrete domain of integers:
1) you have two functions, essentially we look for where the two 3d space surfaces intersect, if z is taken as the result for each equation.
2) the integers "are disctinct", so (0,0) and (1,1) are out, plus (2,2) (3,3) etc. Basically a whole linear diagonal in the instersection of both 3d spaces is excluded (why though, to what useful end?)
3) Starting points for the ranges is therefore (0,1) and (1,0)
4) 1^y is always 1, and x^0 is always 1 so there is a constant starting value of 1 both on both axis
5) but x^y will always be larger than y^x, for y>x and x^y > y^x (prove this by taking the first derivative to get rate of change. Do you use Laplace z domain for discrete, instead of s for continuous?)
6) and the converse to 5.
So once you have found one solution, you know to stop looking, the two surfaces keep diverging from each other.
Why resort to the continuous domain to solve a problem n the discrete, is this even a valid approach?
eg Is there a formal proof that says integers strictly follow that same rules as the continuous domain, just as a subset? I'm interested.
Does this come under group theory, a set with an applied operation?
As I said I am not a mathematician, I am an electrical engineer so probably one of the worst abusers of pure math in a formal sense, but the more I think about this the more questions this raises in my thinking.
Can someone point out errors in thinking?
[+] [-] Sniffnoy|2 years ago|reply
This is false, though! Or, it's almost always true, but there are some exceptions. We of course have an exception at (2,4) and (4,2), where they're equal, and of course at (n,n), where they're obviously equal. And of course 0's and 1's will cause problems for you.
But also, most interestingly, there's an exception at (2,3) and (3,2)! 2<3, and yet, 3^2 > 2^3. Any proof has to account for this!
(There's a fair bit I could say about this exception, but perhaps I should just let you think about it instead. :) )
> Why resort to the continuous domain to solve a problem n the discrete
Because oftentimes this is easier. (In a number of cases it's much easier.) Also... you did this? Like to the extent that your step (5) is valid, you seem to have "proven" it by using the first derivative. That's a continuous tool! I'm not sure what you're talking about with the "Laplace z domain". Or are you using "first derivative" to mean "first difference", or something?
> is this even a valid approach?
Yes, why wouldn't it be? In fact this is actually one of the big reasons for introducing larger number systems, that they let you prove things about the original smaller number system. The rational numbers let you prove things about the integers; the complex numbers let you prove things about the reals; the real numbers and p-padic numbers let you prove things about the rationals; etc. (The integers let you prove things about the whole numbers!)
Proving statements about integers by means of complex numbers is a whole field in itself, i.e., analytic number theory. And in the case of Goodstein's theorem, one famously proves a statement about the whole numbers by passing to the ordinals...
[+] [-] zmgsabst|2 years ago|reply
Many problems are easier to solve in the reals (due to being complete), and you can then restrict that solution to your (sub)set of interest — in this case, the integers.
You see the same thing with Pythagorean triples being simpler to solve by doing the math over the complex numbers and then restricting your answers.
[+] [-] armeehn|2 years ago|reply
However, if only A) needs to be satisfied: y = 3, x = 2 is a counterexample, as x^y = 2^3 = 8 < 9 = 3^2 = y^x.
edit: looks like someone had the same thought as me as I was typing my reply!
[+] [-] chx|2 years ago|reply
> but x^y will always be larger than y^x, for y>x and x^y > y^x (prove this by taking the first derivative to get rate of change. Do you use Laplace z domain for discrete, instead of s for continuous?)
I am struggling to follow what are you saying here
> Why resort to the continuous domain to solve a problem n the discrete, is this even a valid approach?
I can't make heads or tails of this question. The proof says, correctly, for all (real) x != y, x < y solutions it is true that 0<x<e and e<y. He found this by investigating the derivative and establishing the monotonically increasing / decreasing nature of the function. Only after finding this out using does he go back to the original question: what integer x could be? Since he restricted x to be 0 < x < e , we only need to investigate the case of 1 and 2.
[+] [-] Someone|2 years ago|reply
That’s trivially true, as that last condition equals the claim:
Also, if you leave out the and x^y > y^x part, that isn’t generally true because, for example 2⁴ = 4² and 1² < 2¹.Another, minor, point: you write
> Why resort to the continuous domain to solve a problem n the discrete
and
> essentially we look for where the two 3d space surfaces intersect
Those two are in conflict with each other.
[+] [-] bheadmaster|2 years ago|reply
Because if m=n, then n^m=m^n is trivially true.
[+] [-] colgate_total|2 years ago|reply
It may have come as a surprise to a programmer, but in the domain of math, the integers are indeed a subset of a real numbers.
[+] [-] unknown|2 years ago|reply
[deleted]
[+] [-] hgsgm|2 years ago|reply
No one said there was one.
OP said "interesting problem".
[+] [-] keithmcnulty|2 years ago|reply
[+] [-] Computeiful|2 years ago|reply
[+] [-] shusaku|2 years ago|reply
[+] [-] polishdude20|2 years ago|reply
[+] [-] flippinburgers|2 years ago|reply
[+] [-] brazzy|2 years ago|reply
[+] [-] diffeomorphism|2 years ago|reply
After relabeling we may assume n<m.
Step 1: We claim that there exists a natural number k such that m=kn.
Write the equation as
n^n n^(m-n) = m^n
n^(m-n) = (m/n)^n
The left-hand-side is always an integer. The right-hand-side is an integer if and only if such a factor k exists.
Step 2: Inserting this ansatz, we may take n-th roots and reduce the problem to n^k =k n.
Step 3: Monotonicity. Clearly we have equality for k=1. We claim that the difference n^k-kn strictly increases with k for fixed n unless n=2, k=1. That claim in particular gives the result.
We prove this by induction in k. That is, suppose that n^k\geq kn holds for all k\leq K, then
n^(K+1) = n n^K \geq n K n \geq Kn +Kn \geq Kn +n = (K+1)n.
The second inequality is strict unless n=2 and the last one is strict unless K=1.
[+] [-] bolanyo|2 years ago|reply
The proof that no rational number squares to 2 is a famous result of number theory. That no rational non-integer, raised to any power, is any integer, surely has to be justified here.
[+] [-] kleiba|2 years ago|reply
But k cannot be equal to 1 as per your assumption that n<m. So you need to still prove a base case for the induction step.
[+] [-] phoenixreader|2 years ago|reply
[+] [-] pr337h4m|2 years ago|reply
[+] [-] TheRealPomax|2 years ago|reply
"There's a maximum at e, so the only two possible values on the left of e that can be used in these pairs are 1, and 2. But really there's only one, because 1 is the power identity, so we can't use that. If there is a solution, it has to use 2."
Which means we're solving one function for one unknown, in the natural numbers. 2ⁿ=n² gives n=4. We have found the only pair of integers that satisfies our constraint function.
[+] [-] gigel82|2 years ago|reply
[+] [-] dqh|2 years ago|reply
[+] [-] s1mon|2 years ago|reply
[+] [-] wrycoder|2 years ago|reply
[+] [-] nanidin|2 years ago|reply
[+] [-] zsz|2 years ago|reply
[+] [-] bofaGuy|2 years ago|reply
Edit: “Distinct”
[+] [-] unknown|2 years ago|reply
[deleted]
[+] [-] JoeAltmaier|2 years ago|reply
Do a cube and a square land next to each other ever again?
Note it's not asking if they land on each other, that is trivial - 1000000 is 100^3 and 1000^2.
My solution was to form an equation, divide by x and solve the resulting quadratic equation. It produce new solutions: 0 and 1, 0 and -1! As well as 2 and 3. So I was encouraged to say no, those were the only solutions.
[+] [-] casey2|2 years ago|reply
if m^n = n^m is true then
(2a)^(2b) = (2b)^(2a)
2^2b * a^2b = 2^2a * b^2a
since m,n are distinct and a,b are distinct let n>m, b>a
2^(2(b-a)) * a^2b = b^2a
so since b>a, b must also be even
let b=2c
2^(2(2c-a)) * a^4c = (2c)^2a
2^(2(2c-a)) * a^4c = 2^2a * c^2a
2^(2(2c-a)) = 2^(4c-2a) plug in and divide 2^2a
2^(4c-4a) * a^4c = c^2a (1)
Here either c<a, c>a or c=a
if it's the first two then let c+k=a
2^(4k) * a^(4a+4k) = (a-k)^2a (2)
if k is positive
2^(4k) * a^(4a+4k) > a^2a > (a-k)^2a
breaking equality (2) so c<a is false
if k is negative, remember 2c = b > a with that 2c+2k=2a -> 2k>a, but a is positive, so k is positive.
Thus, c=a (giving only 1 possible solution), plugging into (1) and solving gives
2^(4a-4a) * a^4a = a^2a
a^4a = a^2a
a^2a = 1
a = 1.
so m=2, c = 1, b=2, n=4
2^4 = 4^2
There are probably some mistakes though :P
[+] [-] SeanAnderson|2 years ago|reply
[+] [-] captaintobs|2 years ago|reply
[+] [-] Areibman|2 years ago|reply
>Now, since e is somewhere between 2 and 3, we have to conclude that n must be 2. Further, from our curve, we can see that there can only be one other value of x for which (lnx)/x = (ln2)/2, and since we know that 2⁴ = 4², we know that the other integer must be 4.
Is this sort of thinking something that could be justifiably written in a real proof? Sure, conveniently fishing out 2 as n seems to narrow down the search space for m, but I'd imagine this wouldn't work for harder problems
[+] [-] archi42|2 years ago|reply
Since e = 2.71..., there are not too many options for n. The sentence is a bit overconvoluted, but it's correct.
Of course if the search space is bigger, you need to either do some more thinking to narrow it down - or spend a lot of time probing candidates.
[+] [-] ptspts|2 years ago|reply
“e is between 2 and 3” can be considered common knowledge, it easily follows from thd proof that its defining limit converges.
[+] [-] moonchild|2 years ago|reply
[+] [-] TobyTheDog123|2 years ago|reply
Somewhat unrelated, but I cant help but ask why authors are still using Medium as opposed to Substack or some other alternative. The hook of the post happened to interest me to the extent where I went looking for an un-auth-walled version, but I'm sure there have been countless cases where I have simply abandoned it because I wasn't invested enough to seek out the mirrors -- and I'm sure no author wants that.
[+] [-] renewiltord|2 years ago|reply
[+] [-] karthickgururaj|2 years ago|reply
I'm not formally trained Mathematician, but I think this is not an analytic proof - it lacks rigour. It is more a graphical approach that appeals to the reader's intuition. I could be wrong here though.
Second, I really really thought the last graph will include y = x line and was very surprised to not see it :)