[HN Gopher] Only one pair of distinct positive integers satisfy ...
___________________________________________________________________
Only one pair of distinct positive integers satisfy the equation
m^n = n^m
Author : keithmcnulty
Score : 493 points
Date : 2023-04-20 01:59 UTC (21 hours ago)
(HTM) web link (keith-mcnulty.medium.com)
(TXT) w3m dump (keith-mcnulty.medium.com)
| casey2 wrote:
| since m,n must be even let m=2a, and n=2b, with a,b>=1
|
| 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
| munchler wrote:
| It's true that m and n have to have the same parity, but they
| could be both odd (in principle).
| [deleted]
| phoenixreader wrote:
| Why do m,n have to be even?
| gigatexal wrote:
| I could follow this proof! I could follow this proof! When I
| understand it, math is beautiful!
| nanidin wrote:
| 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.
| zsz wrote:
| Moreover, omitting said qualifiers from the title manifestly
| falsifies the claim it makes.
| nanidin wrote:
| Exactly, it felt like nerd sniping for clicks.
| rurban wrote:
| The answer is always 42.
|
| In this case it's even right
| rogerallen wrote:
| Egads, why hand-draw a graph like that when there is Desmos?
|
| https://www.desmos.com/calculator/f61mxuqurc [update]
|
| https://www.desmos.com/calculator/aqhcs63r2e [first version]
| sethaurus wrote:
| A hand-drawn graph can be a great tool for reasoning, because
| it only depicts the features we choose -- everything else is
| imprecise, and it _looks_ imprecise. For me, that 's actually a
| better way of building a visual intuition for how a function
| works.
| rogerallen wrote:
| What you say _can_ be true, but it sets a certain bar for
| clearly conveying the message artistically. I would say that
| bar was not met in this case. I found it so distracting I was
| compelled to go off to Desmos to draw it myself.
| keithmcnulty wrote:
| 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 24 = 16 = 42 , so the pair 2 and 4 are
| certainly one solution. Actually, it is the only solution.
| polishdude20 wrote:
| 1 and 1 are also a solution ?
| porphyra wrote:
| Yeah OP updated the title of the article to include
| "distinct".
| RheingoldRiver wrote:
| the original article says "distinct, positive." It was mis-
| transcribed to HN.
| andygeorge wrote:
| other way around - op updated title after submitting to hn
| cperciva wrote:
| The problem requires that n and m are _distinct_ integers.
| flippinburgers wrote:
| Is this why ... 42?
| brazzy wrote:
| 1 and 2 are positive integers, are they not?
| bsder wrote:
| 1^2 != 2^1
| [deleted]
| bobsomers wrote:
| 1^2 = 1 * 1 = 1
|
| 2^1 = 2
| brazzy wrote:
| I shouldn't comment when I'm half asleep...
| Computeiful wrote:
| 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.
| [deleted]
| OscarCunningham wrote:
| Only assuming y is also less than x.
| shusaku wrote:
| Thanks for sharing. Are there any other posts on your blog you
| highly recommend?
| the_black_hand wrote:
| TIL 1 is not an integer
| [deleted]
| bustermellotron wrote:
| Here is an elementary proof:
|
| 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.
| civilized wrote:
| This is almost word for word the proof that would appear in a
| solid number theory textbook. Very nice.
| giik wrote:
| 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.
| bustermellotron wrote:
| The "claim" more or less proves that k-1 th root of k is less
| than 2 if k is larger than 2. So I think your argument is
| equivalent.
| andygeorge wrote:
| this appears to be a(n incorrect!) gpt comment
| civilized wrote:
| No, it's a carefully constructed logical argument. Miles
| ahead of anything GPT is capable of producing, based on my
| experiments with it.
|
| There's a clear signal that it's constructed by a person with
| advanced mathematical training: the laconic, "high points
| only" style. It makes small, but nontrivial and correct,
| logical leaps, expecting that you will work through the
| details needed to justify the leap yourself.
|
| For example, the reasoning in this sibling comment is needed
| to justify the "n divides m" claim
| https://news.ycombinator.com/item?id=35638344
|
| In my experience, GPT writes much more verbose arguments and
| cannot reliably reason at this level.
| calf wrote:
| But if this were a college homework assignment you would be
| expected to explain briefly why n divides m, the comment
| did skip over it which can confuse people.
| dTal wrote:
| What drove you to this conclusion? We have an enlightening
| reply explaining how we know it isn't, but I would also like
| to know what heuristic you used (so that we know to be wary
| of it!)
| yonrg wrote:
| Thanks for this awareness exercise. Still, I forget to add
| gpt to my internal reading filter
| OscarCunningham wrote:
| 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.
| danbruc wrote:
| Say m contains the prime factor p^i and n contains the prime
| factor p^j, then m^n will contain p^in and n^m will contain
| p^jm. For them to be equal we need in = jm or i/j = m/n but
| for a given solution m/n is constant and the prime factor
| multiplicity ratio must be equal to that. And that applies to
| all prime factors, their multiplicities must all have the
| same constant ratio, therefore the smaller of the two numbers
| must have smaller multiplicity for all prime factors and
| therefore divide the larger number. There is probably a
| simpler way to say this, this feels too complicated.
| hgsgm wrote:
| Focusing on v_x(p), the multiplicity of some prime p in the
| prime factorization of x: m = j p^a -
| v_m(p) = a n = k p^b - v_n(p) = b
|
| p is not a factor of j or k m^n = j^n
| (p^a)^n = j^n p^(an) = k^m p^(bm)
| = ... = n^m v_{m^n}(p) = an = bm
|
| Note that a=0 iff b=0. This is the case where p is neither
| a factor of m nor n. b/a = m/n >=1
|
| This ratio is the same for all primes, so every prime has:
| v_m(p) >= v_n(p)
|
| so n | m
|
| (We didn't need the ratio to be the same, but we did need
| the ratios to be all greater >= 1)
| nmmnthrowaway wrote:
| n^n * n^(m - n) = n ^ m = m ^ n, so n^n divides m^n, so n
| divides m.
| waynecochran wrote:
| I was expecting he would mention that log(y)/y is the inverse of
| the prime counting function estimate, therefore relating to prime
| numbers.
| Sankozi wrote:
| I might be nitpicking but this seems false - there are 2 pairs.
|
| 1. pair: m = 2 n = 4
|
| 2. pair: m = 4 n = 2
|
| In this context (named values n,m) order does seem to matter.
| bigbacaloa wrote:
| This is a trivial claim of limited interest mathematically.
| curiousgal wrote:
| > _As x approaches zero, lnx approaches -[?] and so y approaches
| -[?] also._
|
| Oof. My highschool teacher would have had a field day with this
| one!
| captaintobs wrote:
| Although I have a degree in mathematics, I was never very good at
| deriving proofs.
| caporaltito wrote:
| No, the answer was 12.
| MrYellowP wrote:
| It's behind a paywall and I want to know the damn answer! -.-
| it_was_cool wrote:
| I was just thinking about this problem yesterday, in the context
| of polynomial vs exponential runtimes!
| bofaGuy wrote:
| Let m = n. For m^n = n^m. There are infinite solutions. Am I
| missing something?
|
| Edit: "Distinct"
| Dylan16807 wrote:
| Would you really call that a "pair of integers"? Especially
| when it makes the solution so trivial?
| tirpen wrote:
| Yes. (1,1) is a pair of integers, and so is (17,17). Why
| wouldn't they be?
| Dylan16807 wrote:
| But if you make it a sentence, "my pair of integers is 1
| and 1", it sounds a little bit off. Because "pair" for the
| same concept twice is often an error.
|
| Picking a mathematical formulation like you did can avoid
| that kind of implication, but there wasn't a template for
| which formulation to use and the way you wrote that makes
| it look like order matters which isn't right either.
| CyberDildonics wrote:
| In binary, you will probably get 1 next to another 1 all
| the time.
| Dylan16807 wrote:
| Those are digits, not integers?
|
| And that also sounds like two ordered numbers which is
| not what the question calls for.
| 1letterunixname wrote:
| m = n would be trivial and pointless. Also, I'm curious why he
| didn't specify precisely clarify "distinct" to mean "pairs of
| unequal values" (e.g., exclude {n,m} where n=m) and "pairs not
| equal to others" (e.g., {x,y} excludes {y,x}).
| ouid wrote:
| The condition is as precise as possible "pairs of distinct
| integers" is not equal to "distinct pairs of integers". Don't
| blame the writer when you fail to read what is written.
| ahmedalsudani wrote:
| It's common for the obvious cases and obvious constraints to
| be assumed.
|
| Adding "distinct" would have made it clearer, but it was
| obvious that the author meant distinct from reading the title
| alone.
| someweirdperson wrote:
| > Adding "distinct" would have made it clearer, but it was
| obvious that the author meant distinct from reading the
| title alone.
|
| It's math. No assumption is ever obvious. Only parts of
| some proofs are ever allowed to be called obvious.
| chx wrote:
| int
| 1letterunixname wrote:
| Obviously: .... where n, m [?] N, n != m
| tsu_tsu wrote:
| And then there's PHP => https://3v4l.org/QWjkB#v7.4.32
|
| (at least until v7)
| ouid wrote:
| >from our curve we can see...
|
| Just use Rolle's theorem. If you took calculus, you learned
| Rolle's theorem.
| gus_massa wrote:
| It means:
|
| fake quote> _Anyone that took a Calculus course knows how to
| analyze this function and get the minimum, maximum and
| increasing and decreasing intervals. The calculation is
| unsurprising and boring, so I will skip it and use a graph
| instead._
|
| fake quote> _Anyone that didn 't take a Calculus course will
| not understand the technical details. The calculation is long
| enough to be distracting and boring, so I will skip it and use
| a graph instead._
|
| Unless the main public of the blog are students from the first
| year of the university, I agree with the author that it's
| better to use a graph and left the calculations as an exercise.
|
| [Perhaps the analytical calculation could have been a note at
| the bottom, but it's long and unsurprising enough to be boring
| to write it clearly and carefully. Just left it as an exercise
| :) .]
| zwieback wrote:
| This was one of our bonus homework problems in Hohere Mathematik
| in engineering school in my misspent youth. I tried the
| factorization but got stuck. The offical solution was the log one
| shown in the article, somehow not as satisfying.
| Areibman wrote:
| 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 24 = 42, 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
| ptspts wrote:
| I think this part of the proof is precise. Which sentence is
| handwavy for you?
|
| "e is between 2 and 3" can be considered common knowledge, it
| easily follows from thd proof that its defining limit
| converges.
| archi42 wrote:
| They say just before that: "Then we can say that 1 < n < e."
|
| 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.
| pr337h4m wrote:
| To bypass the Medium loginwall: https://scribe.rip/only-one-pair-
| of-distinct-integers-satisf...
| moonchild wrote:
| see also a nice video by inigo quilez exploring the same problem
| - https://www.youtube.com/watch?v=p-R0druZiTs
| ahmedalsudani wrote:
| This is a neat problem! Thank you for sharing!
| anArbitraryOne wrote:
| Take the log base n of both sides, giving:
|
| m = n log_n(m)
|
| Because m and n are distinct (ie: m!=n), let's say that m>n.
|
| The log term will always be greater than one. Imagining the shape
| of the log function (with base>1), it isn't hard to see that
| there is one solution.
|
| Not a rigorous proof, but neither was the article.
| phoenixreader wrote:
| This doesn't prove anything, unfortunately. It doesn't even
| make use of the fact that m,n are integers. If m,n are not
| restricted to integers, there exists an infinite number of
| solutions (e.g. m=8.043, n=1.46).
|
| The mistake in your proof is that you considered the shape of
| the log function while implicitly holding m on the left-hand-
| side constant (i.e. you should have concluded "for a constant
| m", there is only 1 n satisfying this equality"). However,
| since m is variable, you have to consider an infinite number of
| log functions. If I missed something, let me know.
| anArbitraryOne wrote:
| You're right. Not sure what I was thinking.
|
| Would be interesting to use a recurrence relation by
| substituting m
| karthickgururaj wrote:
| Good article - but couple of points.
|
| 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 :)
| NotYourLawyer wrote:
| It's not totally rigorous, but it wouldn't be hard to fill in
| the details. This is a sketch of a proof, not the proof itself.
| karthickgururaj wrote:
| Yes, that's basically what I said and meant in the parent
| post. I was suggesting the article call it a "graphical"
| solution approach, not analytical.
|
| And if I wasn't clear - it wasn't my intent to treat this any
| less "useful". If anything, it is more interesting (for me)
| to read about solutions that give an intuitive feel, than dry
| analysis.
| n4r9 wrote:
| Proofs can be graphical or diagrammatic, though. Take for
| example this proof of the Pythagorean Theorem:
| https://cdn.britannica.com/43/70143-004-CCB17706/theorem-
| dem...
| hgsgm wrote:
| "analytical" means "calculus" here.
| chx wrote:
| No, the graph parts are explanation. The analysis of the
| derivative function maybe would be better if it were rewritten
| with the usual limes notations, nonetheless it's correct in the
| crucial conclusion of the ln x / x function is _monotonically
| increasing_ (0, e) and _monotonically decreasing_ (e, inf) and
| as such one of every pair of equal but distinct values must be
| from (0,e) the other from (e,inf). There are not many integers
| between 0 and e: 1 and 2. At 1, ln x / x is zero and in
| (e,inf) this function has a strict lower boundary of 0, it is
| never 0. Thus the only possible solution is 2 and it is.
| arketyp wrote:
| In general, couldn't a function be monotonically increasing
| in some interval and still have many points such that y = x?
| A curve that jiggles around the line y = x for instance.
| chx wrote:
| So while the original problem was x^y=y^x he have
| rearranged this into ln x / x = ln y / y and so now are
| investigating the ln x / x function. Yes, the lettering
| could be clearer because y at some points means one
| variable and later on it means the value of the function.
| deredede wrote:
| We are not looking for points such that y = x but for
| distinct points x, x' that have the same y (f(x) = f(x'))
| xiaodai wrote:
| m=n. I guess need to say m != n
| renewiltord wrote:
| 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.
| JoeAltmaier wrote:
| 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.
| kccqzy wrote:
| I would have approached this problem this way: set a lower bound
| say 3. Then we wish to prove there doesn't exist any n,m>=3 that
| satisfies n^m=m^n. This is much more easily proved using just
| double induction. Then you can just search for a case where n=2.
| NotYourLawyer wrote:
| I'm not seeing how induction helps here.
| gigel82 wrote:
| Title is extremely wrong: "Only One Pair of _Distinct_ Integers
| Satisfy The Equation n^m = m^n ".
| wrycoder wrote:
| Yes, that is the article's title. It should not have been
| changed. 1,1 is a solution.
| s1mon wrote:
| Yes. I had to search for that qualification in the text. As far
| as I can tell, any integer works if n=m.
| dqh wrote:
| As -2^-4 = -4^-2 I think the HN and blog title should also
| include the word 'positive'
| Rebelgecko wrote:
| Or n=1 and m=1
| defrost wrote:
| Or n=0 and m=0
| atahanacar wrote:
| Is 0^0 equal to 0^0?
| HWR_14 wrote:
| Yes.
| thayne wrote:
| The blog title says "distinct positive integer" which
| excludes that. The HN title is missing the word distinct
| for some reason.
| OscarCunningham wrote:
| 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.
| frodetb wrote:
| 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.
| eru wrote:
| Maybe. I do appreciate seeing both approaches, though.
| frodetb wrote:
| Agreed! I'm realizing that my comment came across as
| negative, but I did appreciate seeing a second path to the
| same place. I also agree that the expression x^(1/x) feels
| like a more natural place to start.
|
| You often see this I think, in "pretty" proofs compared
| with the more direct approach. A clever early step or some
| bit of startling insight.
| pdpi wrote:
| Seeing as we're in the integer world, I'm not sure logs need
| to show up ever, there's probably a proof path around unique
| prime factorisations. E.g. it's more or less immediately
| obvious that n and m would need to share the same prime
| factors in the same ratios.
| justinpombrio wrote:
| Here goes.
|
| n^m = m^n, so n^m and m^n share the same prime
| factorization. Call it p1^x1 * ... * pk^xk.
|
| n = n^m^(1/m) = p1^(x1/m) * ... * pk^(xk/m)
|
| m = m^n^(1/n) = p1^(x1/n) * ... * pk^(xk/n)
|
| Therefore each xi is divisible by both n and m, so it's
| divisible by lcm(n, m). Call lcm(n, m) = d. Now define:
|
| z = p1^(x1/d) * ... * pk^(xk/d)
|
| Both n and m are powers of z!
|
| n = z^(d/m)
|
| m = z^(d/n)
|
| Call a=d/m and b=d/n. Then:
|
| n^m = (z^a)^(z^b) = z^(az^b)
|
| m^n = (z^b)^(z^a) = z^(bz^a)
|
| n^m = m^n -> z^(az^b) = z^(bz^a) -> az^b = bz^a
|
| EDIT: continuing proof.
|
| That's as far as I've got. Can someone run with it?
| actuallyalys wrote:
| This back-and-forth makes me wonder, is it possible to
| write proofs about proofs? e.g., you cannot prove this
| result without logarithms or there must exist a proof that
| involves prime factors?
|
| I suppose at least some proofs vaguely like that are
| possible because Godel's incompleteness theorem is one,
| although I suspect that that same theorem puts some
| constraints on these "metaproofs."
| gjm11 wrote:
| The key thing you need is that for n >= 3 the sequence of
| (n^1/n) is decreasing. You can get that pretty easily
| without logs.
|
| Look at two consecutive terms: n^(1/n) and (n+1)^[1/(n+1)].
| The ratio of the first to the second -- we want to prove
| that this is >1 -- is n^(1/n) / (n+1)^[1/(n+1)]. This is
| bigger than 1 iff its n(n+1)th power is; that is, iff
| n^(n+1) / (n+1)^n > 1. We can write this as n (n/(n+1))^n;
| so what we need is that (n/(n+1))^n > 1/n.
|
| (Handwavily: we know that the LHS is about 1/e, so for n>=3
| this should be good. But we want a _proof_ and we 're
| trying to do it without nontrivial analytic machinery.)
|
| Actually, I prefer to write this as ((n+1)/n)^n < n, or
| (1+1/n)^n < n. Expand this with the binomial theorem: we
| get sum {0<=k<=n} of (n choose k) n^-k. And we have (n
| choose k) = n(n-1)...(n-k+1) / k! < n^k/k! so this is
| strictly less than sum {0<=k<=n} of 1/k!. And for k>0 we
| easily have k! >= 2^(k-1) so this sum is no bigger than 1 +
| 1 + 1/2 + 1/4 + 1/8 + etc. = 3.
|
| So, the function _on integers_ n - > n^1/n is decreasing
| for n >= 3. Now the proof goes through as before.
|
| (Maybe there's a more thoroughly number-theory-ish way to
| do it by looking at prime factorizations, but when I try it
| that way it always seems to end up rather a mess.)
|
| [EDITED to add:] But elsewhere in the discussion users
| bustermellotron and diffeomorphism give (very similar) neat
| number-theory-ish proofs, either of which is definitely a
| better proof than the one using the calculations above.
| bustermellotron wrote:
| On the other hand, your proof really only needs the
| binomial theorem and geometric series.
| freehorse wrote:
| 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.
| mst wrote:
| Plus this approach (IMO) visualised better than the proposed
| alternative.
|
| I think it's arguable that OP's approach is cleaner for some
| value of clean, but the article's approach gave me happy
| flashbacks to doing number theory in undergrad that OP's
| approach didn't.
|
| When communicating to the wider world, aesthetics do matter,
| and yeah, everything you said as well.
| onion2k wrote:
| That's a very clear explanation. Have an upvote.
| zapdrive wrote:
| [flagged]
| badrabbit wrote:
| Since when did medium require an account or an app??
| senden9 wrote:
| They try this from time to time. I normally open the page in a
| private window if that happens. https://12ft.io/ also helps.
| TobyTheDog123 wrote:
| 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.
| TheRealPomax wrote:
| 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 N, not R) 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. 2n=n2 gives n=4. We have found the only pair of
| integers that satisfies our constraint function.
| [deleted]
| hgsgm wrote:
| There is plenty of wel organized, high quality, free material
| like this on the web. There's no win in paywalling this, Keith
| McNulty
| quickthrower2 wrote:
| https://archive.is/9tILv
| diffeomorphism wrote:
| 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.
| kleiba wrote:
| _Clearly we have equality for k=1._
|
| 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.
| diffeomorphism wrote:
| Nah, k=1 is the trivial base case and is allowed. The
| "assumption" is no such thing, but just notational
| convenience. One can of course tidy that up (e.g. n\leq m and
| trivial case is obvious), but for a random HN post it seems
| not worth the effort.
| kleiba wrote:
| Well, I guess you're right. I mean, we're looking for two
| _disctinct_ numbers as the final solution, but that doesn
| 't mean we can't use k=1 in the proof.
| phoenixreader wrote:
| This is a very nice proof! Probably the best proof here, since
| it's easy to follow and does not require differentiation.
| bolanyo wrote:
| (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.
| diffeomorphism wrote:
| > surely has to be justified here.
|
| True, but considering that the linked post uses e, log,
| limits and derivatives without any further comment, I am
| going to err on the side of "nah, enough detail".
| psychphysic wrote:
| Easy once you realise squaring a squared number is the square
| root of the square to the power of 4.
|
| Which you hit very fast even if you take a simple approach to the
| search space.
| Jeff_Brown wrote:
| That gets you to existence but it doesn't show uniqueness,
| unless I'm missing something.
| psychphysic wrote:
| It's not unique solutions are 2,4 and 4,2 :p
| airbreather wrote:
| I am struggling to see the great revelation.
|
| 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?
| [deleted]
| chx wrote:
| 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.
| zmgsabst wrote:
| 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.
| Someone wrote:
| > but x^y will always be larger than y^x, for y>x and x^y > y^x
|
| That's trivially true, as that last condition equals the claim:
| but x^y > y^x, for y>x and x^y > y^x ^^^^^^^^^
| ^^^^^^^^^
|
| Also, if you leave out the _and x^y > y^x_ part, that isn't
| generally true because, for example _24 = 42_ and _12 < 21_.
|
| 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.
| colgate_total wrote:
| > 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.
|
| 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.
| bheadmaster wrote:
| > Basically a whole linear diagonal in the instersection of
| both 3d spaces is excluded (why though, to what useful end?)
|
| Because if m=n, then n^m=m^n is trivially true.
| Ensorceled wrote:
| This is when I stopped reading the original comment.
| Sniffnoy wrote:
| > 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...
| eru wrote:
| Apropos: difference calculus is a fascinating topic. It has
| lots of results that are analogous to differential calculus.
|
| Yes, p-adic numbers are also really interesting to look into.
|
| It's also interesting to re-derive much of analysis (like
| limits and derivatives etc) in the context of the dual
| numbers (https://en.wikipedia.org/wiki/Dual_number):
|
| > They are expressions of the form a + b * e, where a and b
| are real numbers, and e is a symbol taken to satisfy e^2 = 0
| with e [?] 0.
|
| You can sort-of pretend that e is an infinitesimal, but with
| a sound theoretical footing.
|
| See https://math.stackexchange.com/questions/341535/is-the-
| theor...
| thaumasiotes wrote:
| >> They are expressions of the form a + b * e, where a and
| b are real numbers, and e is a symbol taken to satisfy e^2
| = 0 with e [?] 0.
|
| > You can sort-of pretend that e is an infinitesimal, but
| with a sound theoretical footing.
|
| You can just work directly with infinitesimal values on a
| sound theoretical footing. This goes under the name
| "nonstandard analysis".
| https://en.wikipedia.org/wiki/Nonstandard_analysis
|
| If that's your only goal, the dual numbers aren't
| accomplishing anything.
| Sniffnoy wrote:
| > You can just work directly with infinitesimal values on
| a sound theoretical footing. This goes under the name
| "nonstandard analysis".
| https://en.wikipedia.org/wiki/Nonstandard_analysis
|
| This is an oversimplification. Nonstandard analysis, the
| hyperreals, are _one_ way of adding in infinitesimals to
| the reals, and definitely not the one I 'd recommend for
| all use cases (although going from context, they may be
| appropriate here).
|
| There are plenty of ways to make a number system that add
| in infinitesimals to the reals, such as yes the
| hyperreals, and also I'd count the dual numbers among
| them, but there's also e.g. the surreal numbers:
| https://en.wikipedia.org/wiki/Surreal_number
|
| So, why am I kind of down on the hyperreals? Well, thing
| is, as I understand it, nonstandard analysis isn't
| _really_ the study of the hyperreals; it 's the _use_ of
| the hyperreals to study the reals. I mentioned above that
| one big use of passing to a larger number system is that
| it reflects on the smaller number system; however, as
| best I can tell, the hyperreals are pretty much used
| _purely_ in this way. They 're used pretty much entirely
| as a tool for proving statements about the real numbers,
| rather than an object of study in their own right.
|
| And there's a reason for that; people often talk about
| "the" hyperreals, but actually, they're not uniquely
| defined. There's not really _the_ system of hyperreal
| numbers, so much as there are potentially different
| systems of hyperreal numbers, which is annoying, but not
| if you only want to use them as a tool to study the
| reals, because their (relevant) relation to the reals is
| all the same. It 's a bit icky.
|
| So yeah if you want to do analysis or calculus -- which
| might be the case, given that the earlier context was
| dual numbers, and that's what one would typically use
| dual numbers or -- then sure, use hyperreals. But if you
| just want to play around with a nifty number system that
| includes both reals and infinitesimals... eh, they're not
| great. You're likely to have more fun with the surreals.
|
| (More generally, of course, it's worth remembering that
| there's no need to stick to well-known systems of
| numbers... you can invent your own! Like, if for some
| reason you need infinitesimals, but you don't want them
| to square to zero like in the dual numbers, but you also
| don't want all the stuff that's in the hyperreals or
| surreals, there's nothing wrong with using R[e] (or R(e),
| or other variants depending on exactly what you're doing)
| to get a sort of minimal reals-with-infinitesimals...)
|
| [Edit: Is there no way to do bold anymore? Those R's in
| the above paragraph were supposed to be bold, to indicate
| the real numbers...]
| eru wrote:
| Yes. I was bringing up the dual numbers here as a gentle
| introduction to ramp up to nonstandard analysis.
| Sharlin wrote:
| > Apropos: difference calculus is a fascinating topic. It
| has lots of results that are analogous to differential
| calculus.
|
| Which is to be expected, right? Given that differential
| calculus is just difference calculus in the limit.
| armeehn wrote:
| 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!
| Ensorceled wrote:
| Your comment goes to the heart of the matter "claim by
| assumption".
|
| It's hilarious that the FIRST two integers greater than one
| form a counter example to their "proof".
| hgsgm wrote:
| > I am struggling to see the great revelation.
|
| No one said there was one.
|
| OP said "interesting problem".
| keithalewis wrote:
| First page of HN worthy? The intellectual level of posts here hit
| a new low.
| melvinmelih wrote:
| There's also only one distinct positive integer that satisfies
| this equation: x + 1 = 2
| SeanAnderson wrote:
| dang - the title should say "distinct integers"
| 2h wrote:
| [flagged]
| ComputerGuru wrote:
| I have my browser set up to automatically redirect. Here's what
| I saw instead:
|
| https://scribe.rip/@keith-mcnulty/only-one-pair-of-distinct-...
| omoikane wrote:
| https://archive.is/9tILv
___________________________________________________________________
(page generated 2023-04-20 23:03 UTC)