8 ms·
Inventing an Operation to Solve x^x = y (2000)
- yiyus 7y agoThe J language makes trivial to solve this problem without a tetration operator: (^~^:_1)5 2.12937
- H8crilA 7y agoHow's that implemented? Newton's method like in the OP? I.e. if there's at least one solution there's an okay chance to find at most one solution?
- xelxebar 7y agoEssentially, yes. > (^~^:_1) 5 First, let me break this down, in the interest of sharing the joys of J. The thing in parenthesis is our inverse operation of x^x; we then evaluate that at 5. The first ^ is exponentiation and the following ~ makes binary operators into unary ones by evaluating on the diagonal. In other words it turns f(x,y) into f(x) = f(x,x), which for x^y corresponds to x^x. Next we have the ^: modifier. This is function iteration, i.e. exponentiation over function composition. The function is on the left (here ^~) and the count on the right (here _1). So f ^: 2 means f(f(x)). In fact, this function exponentiation is extended to negative integers as well! In J, negative numbers are prefixed with _ (underscore), and f^:_1 actually gives us the inverse of f (if it exists)! Anyway, we can see inspect the definition for an operation's inverse using the b. verb. From the jconsole: ^~ b. _1 3 : '(- -&b@(*^.) % >:@^.)^:_ ]1>.b=.^.y'"0 :.(^~) The part we are interested in is in single quotes. Pulling this one apart would involve introducing the various operator combinators in J, so suffice it to say that the ^:_ part numerically approximates a fixed point of the part in parenthesis, which essentially is a straightforward transcription of the recursive relation in Newton's method.
- youareawesome 7y agoThis is easily solved using the Lambert W function: Observe: W(x * e ^ x) = x x ^ x = y ln(x ^ x) = ln(y) ln(x) * x = ln(y) ln(x) * e ^ ln(x) = ln(y) W(ln(x) * e ^ ln(x)) = W(ln(y)) ln(x) = W(ln(y)) x = e^W(ln(y)) https://en.wikipedia.org/wiki/Lambert_W_function https://en.wikipedia.org/wiki/Lambert_W_function
- throwlaplace 7y agoThat's pretty asinine since the W function is that inverse (basically). You're just saying "this is easily solved by easily solving". Before anyone jumps on me: I'm perfectly familiar and comfortable with functions that aren't defined in closed form.
- paulddraper 7y agoTo be fair, this is much of math. The ratio of right triangle legs is "easily solved" by tan(x). But that's magical/cheating to someone who hasn't studied trigonometry. Lambert-W is a well known function with known approximation methods; once you reduce your problem to it (in this case, trivially), you can lean on that knowledge from others.
- knzhou 7y agoThat's true for almost any nontrivial transcendental algebraic or differential equation. Special functions to solve special cases are the norm. We could repeat the same discussion at a lower level. Suppose you tell a bright middle schooler about the basics of integration, and the power rule. Then they ask, "So what's the integral of 1/x? It can't be x^0/0..." "That's a special case. It's a function called "natural logarithm", ln(x)." "But what's the definition of that weird function?" "It's defined to be the integral of 1/x." [0] "That's pretty asinine..." [0] https://en.wikipedia.org/wiki/Natural_logarithm#Definitions https://en.wikipedia.org/wiki/Natural_logarithm#Definitions
- throwaway71828 7y agoHere is another fun problem for you folks: x^x^x^... (infinite power tower) = 2. If you solved it, try the general case of x^x^x^... = y, for some arbitrary constant y.
- H8crilA 7y agoHow do you define infinite power? A limit of such series, if exists? {x, x^x, x^x^x, ...}
- lokedhs 7y agoThat would be equal to x^y, which means that the solution is the y'th root of y? However, don't you have to prove that the series converges? Is the approach even valid if it doesn't?
- deleted 7y ago[deleted]
- jwilk 7y agoNote that according to your solution, x=√2 for both y=2 and y=4. But of course the sequence cannot converge to both 2 and 4 at the same time!
- a1369209993 7y agoFixed point of x^(...), I guess; you don't actually need to define it properly: x^x^x^... = y x^(x^x^x^...) = x^(y) x = y^(1/y) # there you go
- np_tedious 7y agoSeems to this series converges to 1 for the interval between 0 and 1, and nothing else converges. Is that correct? EDIT: actually I guess it's more complicated than that. If I'm understanding the order of operations correctly, there's an alternating parity (where n is the number of exponentiations) thing going on with the values between 0 and 1
- 7y ago
- zabzonk 7y agoMight be useful if it was stated at the start of the post exactly what the ^ operator is supposed to do - it does different things in different programming languages.
- saagarjha 7y agoIn context, I think it’s pretty clear that it’s exponentiation. Mostly because the context is math where the meaning is a lot more unambiguous.
- namirez 7y agoI always felt the Fortran exponentiation operator (* *), which is inherited by javascript and php, was more intuitive notation.
- samatman 7y agoInteresting, the caret looks better to my eyes, since the real notation is x², thus x^2 is pointing at where the 2 should be. But I get the reading of double-asterisk as 'multiplication of multiplication' as well, either is fairly transparent really.
- kaoD 7y agoIndeed. To me C's ^ as xor has always been the weird one since it actually looks like a logical and: https://en.m.wikipedia.org/wiki/List_of_logic_symbols https://en.m.wikipedia.org/wiki/List_of_logic_symbols
- hprotagonist 7y agoIt’s always nice when people independently reinvent good ideas! This poster’s more or less come up with up-arrow notation and a shot at its inverse. edit: actually meant https://en.wikipedia.org/wiki/Tetration https://en.wikipedia.org/wiki/Tetration https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation
- ColinWright 7y agoAs is pointed out further down, it does effectively invent tetration, which is cool, but that's not Knuth's arrow notation. Edited: I've removed the original and replaced it with the above because clearly my original comment wasn't being understood the way it was intended. Possibly this is no better, but it's worth a try. To provide context, the comment by elil17 is in response to my original, in which I asked what this had to do with Knuth's arrow notation.
- acollins1331 7y agoI wouldn't worry much when your e-rep takes a few hits from people with nothing better to do.
- perl4ever 7y agoYou're not supposed to discuss voting...but I've noticed a couple times that sometimes when I make two related comments on the same thread expressing basically the same opinion, one gets upvoted a lot and one gets downvoted a lot, and that's just weird. Maybe the exact timing determines if the upvoters see it.
- acollins1331 7y agoYeah, this is just one reason why I wouldn't be super concerned with your hacker news points.
- elil17 7y agoa@2 = a↑↑2
- Straw 7y agoWe can express the solution in terms of the Lambert-W function, the inverse of f(x) = x*exp(x). We still need a new function, but at least Lambert-W comes up in other places as well- not much worse than introducing log.
- ludamad 7y agoOne thing that has got me thinking in the past was another kind of formula,`f(f(x)) = g(x)`, where `g` is given. It bothered me that far from a general algorithm being known, individual cases were stumping (e.g., `f(f(x)) = e^x`). Any insights/references from HN folks about this?
- dan-robertson 7y agoProblems like these (typically restricted to integers/natural numbers) come up in competitions from time to time. Sometimes there are some tricks required that are very hard to find on the spot. Here is a related problem you may enjoy: Find all increasing functions f : N -> N such that f(f(x)) = 3x
- fyp 7y agoIs this problem correctly stated? Substituting in x=f(y) you get f(f(f(y))) = 3f(y) so f(3y) = 3f(y) This suggests a linear solution but then you get f(x)=sqrt(3)x which doesn't work since it's N -> N.
- Chinjut 7y agoSuggests is not demands. If we discard the requirement to be an increasing function, one recursively defined solution takes f(3x + 1) = 3x + 2, f(3x + 2) = 3 * (3x + 1), and f(3x) = 3f(x), with f(0) = 0. Or analogously for any way of splitting the positive integers not divisible by 3 into ordered pairs (a, b). Then define f(3^n a) = 3^n b and f(3^n b) = 3^(n + 1) a. This is the general form of the solutions.
- a1369209993 7y ago∅ assume f exists increasing requires that x < f(x) < f(f(x)) f(f(0)) = 3*0 = 0 ≮ 0 therefore f does not exist, qed
- AnimalMuppet 7y agof(x) = sqrt(3) * x. Then f(f(x)) = sqrt(3) * sqrt(3) * x = 3x. So there is at least one solution.
- zw123456 7y agoI couldn't resist chucking it into wolfram alpha https://www.wolframalpha.com/input/?i=solve+x^x+-+y+=+0 https://www.wolframalpha.com/input/?i=solve+x^x+-+y+=+0 https://www.wolframalpha.com/input/?i=x%5Ex%3Dy https://www.wolframalpha.com/input/?i=x%5Ex%3Dy I think someone else mentioned W function, which is shown in the wolfram solution The thing I found interesting is the graph, there is a local min at 1/e, so the solution depends on y >1 or e^-1/e <= 1 very interesting curve.
- anon1253 7y agoI asked the same question a while ago, https://math.stackexchange.com/questions/613946/xx-y-given-y-solve-for-x-analytically https://math.stackexchange.com/questions/613946/xx-y-given-y... Interesting analysis of the problem :-) it has been bugging me since high school! Might be worth linking to the Lambert W function https://en.wikipedia.org/wiki/Lambert_W_function https://en.wikipedia.org/wiki/Lambert_W_function This was the best comment I'd reckon: > As you probably saw, the solution of x^x = y is x = Log(y) / W[Log(y)]. Now you take us in a highly philosophical debate. What is the limit of elementary functions ? Thanks for this question. Cheers. – Claude Leibovici
- edflsafoiewq 7y agoThat comment references the worked examples that used to be on the Lambert W wiki page, including this exact problem, x^x=y. Here's the last version before it was deleted if anyone wants to see it: https://en.wikipedia.org/w/index.php?title=Lambert_W_function&oldid=910867451#Example_2 https://en.wikipedia.org/w/index.php?title=Lambert_W_functio...
- pickdenis 7y agoI'm glad to see that this problem bugged other high schoolers. I spent a lot of time learning about the lambert W function and real analysis in general due to this problem in high school.
- chewzerita 7y agoAll this talks about centers, operations and inverse operations reminds me of monoids from learning haskell: https://en.wikibooks.org/wiki/Haskell/Monoids https://en.wikibooks.org/wiki/Haskell/Monoids
- DoctorOetker 7y agois it just belgium where we call these "center's" neutral elements of an operation, or did the rest of the HN geography just forget that term?
- 47348436885325 7y agoI think what the original author meant by "centers" of addition and multiplication is closer to "empty sum" and "empty product" respectively. From what they wrote, it seems that they wanted more than just neutrality. In any case I don't think we should retroactively label their novel and necessarily unique concept with a familiar name.
- macawfish 7y agoReminds me of this fascinating paper: https://arxiv.org/pdf/math/0112050.pdf https://arxiv.org/pdf/math/0112050.pdf It's about an infinite chain of operations where each is to the last as multiplication is to addition.