10 ms·
How do you find integer solutions to x/(y + z) + y/(x + z) + z/(x + y) = 4?
- drfuchs 9y agoIn the title, read "and" as "plus". (For a while I thought they meant "logical AND", given the HN context.)
- jordigh 9y agoYeah, I wrote "+" but HN turned it to "and".
- dang 9y agoSorry, that's the rare case where we actually want +. Fixed above.
- krapp 9y agoWhy does that have to be the rare case? What's the common case of using "+" that you're trying to avoid?
- zulln 9y ago"Microsoft + Apple will both.." I imagine people use + to get by character limit in the title.
- snakeanus 9y agoThey should just get their threads removed then. There is no reason to silently apply that weird behaviour instead. In fact, I would expect this to be quite rare as most people would probably use & instead.
- krapp 9y ago>I imagine people use + to get by character limit in the title. What's wrong with that? The same phenomenon occurs on Twitter - people find a way to optimize every character. Isn't an 80 character limit for titles on a modern web forum really the problem?
- tzs 9y agoFor future reference, when someone really wants a plus sign would using Unicode FF0B (full width plus) get past the automatic "and" conversion?
- dang 9y agoWe started stripping out a bunch of character ranges a few years ago because people were using them to play Unicode games in HN titles and the idea here is plain text. But I'm not sure in that case. You could test it if you wanted.
- tzs 9y agoI tried it and it works. U+FF0B gives a plus sign when used in an HN title. It's a fair bit wider than normal, so may look a little off but not as off as "and". Here's a line of 10 U+FF0B's and a line of 10 +'s for comparison: ＋＋＋＋＋＋＋＋＋＋ ++++++++++
- comex 9y agoJust for fun, what if it is read as AND: that is, bitwise AND? x/(y&z) & y/(x&z) & z/(x&y) = 4. If the / becomes integer (flooring) division, there are many solutions, such as (6, 13, 19). But if the division results are required to actually be integers, there are no small solutions - at least, none where x, y, and z <= 10000 (checked by brute force with minor optimization). I suspect that unlike the original problem, there are actually no solutions, but it’s just a guess. Anyone want to come up with a proof? :)
- madez 9y agoIt might be fun and surprising to come up with seemingly unsolveable problems in math, but it isn't actually that hard. Especially if you come from the angle of computer science. Math does not have common tools I'm aware of to deal with many of those problems. Bitwise AND is not a linear function, which is a first obstacle.
- AstralStorm 9y agoFor bitwise and you have to be solving it in a Galois field (And consider what AND does) which is actually easier than the general solution but points you more accurately at the cryptographic origin of the question.
- jwilk 9y agoLet's consider the lexicographically smallest triplet (x, y, z) such that: x/(y&z) & y/(x&z) & z/(x&y) is even That means that x/(y&z) is even, or y/(x&z) is even, or z/(x&y) is even. If x/(y&z) is even, then x is even too, so x&z is even, so y is even (otherwise y/(x&z) wouldn't be integer). Similarly, we can conclude that all x, y, z are even. But if we substitute x=x/2, y=y/2, z=z/2, the value of x/(y&z) & y/(x&z) & z/(x&y) doesn't change. So the (x, y, z) triplet we considered wasn't the smallest. Contradiction.
- comex 9y agoMakes sense. Nice proof :)
- rsj_hn 9y agoThis is a great article. Little puzzles like these are often the gateways to enormous mathematical journeys. Here, I only wished the journey was more detailed -- you could motivate all of these operations -- but that would take many pages.
- pmiller2 9y agoI admit, I had low expectations with it being on Quora. I was far from disappointed, though.
- vecter 9y agoReally? The math content on Quora is generally top notch. It depends on who answers the question of course, but there are many high quality writers on Quora with deep understandings of mathematics.
- jnbiche 9y agoAgreed. Besides HN, and Reddit for occasionally indulging my darker political side, Quora is the only social content I regularly consume. Besides math, there's also some excellent writers on machine learning and computer science.
- faitswulff 9y agoAny questions/answers in particular you would recommend reading?
- vecter 9y agoNo particular answers (honestly there are so many good ones), but here are two writers off the top of my head I used to read many years ago: https://www.quora.com/profile/Daniel-McLaury https://www.quora.com/profile/Daniel-McLaury https://www.quora.com/profile/Sridhar-Ramesh https://www.quora.com/profile/Sridhar-Ramesh
- vbezhenar 9y ago
- theophrastus 9y agousing the rearranged form: ((x + (((2*y*z) + (y*y) + (z*z) + (((z*z*z) - (z*y*y))/(x + y)))/(x + z)))/(y + z)) I find by brute force (no pride!) the first solution triplet: 35, 132, 627 Edit: of course, this is not a solution. It's now just an example to others to beware of floating point errors.
- jackgolding 9y agoIf only that worked in uni maths, my lecturers wouldn't even give one mark for giving the correct answer by the end of the course!
- gefh 9y agoUnfortunately, 4.00000009534 is not 4 :)
- MereInterest 9y agoComes out as 167820976/41955243 in lowest terms, which isn't quite 4.
- glitcher 9y agoLanguage nitpick (because maths): I realize when you say "isn't quite 4" you mean the solution is not quite equal to 4, but it could also be incorrectly interpreted as a solution that is slightly less than 4. 167820976/41955243 = 4 + 4/41955243
- hawkice 9y agoThat doesn't equal 4 it equals 4.00000009534. So, there is a precision issue, probably using floats to keep division results.
- deleted 9y ago[deleted]
- vacri 9y agoI once saw a youtube video which said that an object moving at 4m/s would be slowed down by [thing] by 0.00006m/s, so its new velocity would be 3.99994m/s ... except that no, its new velocity would be 4m/s. The author, a physicist, ignored sig figs. 4 - 0.00006 = 4, when you're dealing with measurements :)
- DrTung 9y agoAgree, good article. Thanks to it I think I understand more why cryptography based on elliptic curves (like Curve25519) is considered pretty safe for now.
- bmc7505 9y agoWhat are some other problems that appear deceptively simple, but are extremely difficult to solve?
- yen223 9y agoFermat's last theorem is probably the most obvious one.
- guruparan18 9y agoFrom the past, we had Fermat's Last Theorem. Looking for ones that are not solved yet? How about "Collatz conjecture "? I think there are more complex ones, but yeah, not so simple to explain.
- ouid 9y agofrom everything I've read, collatz has not merely resisted proof, but anything resembling progress. Erdos said that mathematics is not yet ready for such problems.
- guruparan18 9y agoTrue. And there could be many more ridiculously simple problems with hard or no applications (at least for now) we may not be able to solve or progress at all. Math as we know and practice might still fall short. I, for one, be happy that simple to state but solved, Godel's Incompleteness theorem, about the imperfection of the tools, had set the things firmly on stone. Solving them or progress? May be I don't care, but these little problem, simple ones does encourage one to start thinking about solving problems, they make math accessible to masses.
- zzazzdsa 9y agoConway showed that the generalized Collatz conjecture (recurrences with arbitrary cases dependent on the modulus) is computationally undecidable (halting problem reduces to it). The choice of modulus doesn't even need to be that big to get this result, only ~6500 or so. As far as I know, this is the only substantial result in either direction for this problem.
- Houshalter 9y agoI wonder if a SAT solver would be able to solve this faster than brute force.
- ekiwi 9y agoYes. You can try the following smt2 script with yices2 [0]: (set-logic QF_UFNIA) (declare-fun x () Int) (declare-fun y () Int) (declare-fun z () Int) (define-fun left-side () Int (+ (+ (* (* x (+ x z)) (+ x y)) (* (* y (+ y z)) (+ x y))) (* (* z (+ y z)) (+ x z))) ) (define-fun right-side () Int (* (* (* 4 (+ y z)) (+ x z)) (+ x y)) ) ; disallow division by zero (assert (not (= 0 (+ y z)))) (assert (not (= 0 (+ x z)))) (assert (not (= 0 (+ x y)))) (assert (= left-side right-side)) (check-sat) (get-model) Run this by calling yices-smt2 on it. [0]: http://yices.csl.sri.com/ http://yices.csl.sri.com/
- ufo 9y agoDoes the `Int` datatype allow negative integers or is it non-negative only? This problem gets much more difficult if you restrict it to positive solutions only.
- samfisher83 9y agoInt is usually signed. Unsigned int is not signed.
- gizmo686 9y agoYou need to add: (assert (> z 0)) (assert (> x 0)) (assert (> y 0)) or it will give you negative solutions. I am running this on my machine now. Will report back if it comes up with a solution.
- jfoutz 9y agoAnything is possible, but I really doubt you'll find those 80 digit numbers. Maybe the sat solver includes some serious number theory though. I doubt it.
- jfaat 9y ago> Next up: what is the degree of our equation? The degree is the highest power of any term showing up. For example, if you have (a^2)b(c^4), that’s a term of degree 7 = 2 + 1 + 4 I thought that equation was degree 4, which aligns with what the author says later on. Am I missing something? It seems odd that he would write out that equation accidentally, maybe just crossed wires though. I'm sure we've all been there.
- gizmo686 9y agoThe wording in that paragraph is a bit confusing. In this context, "term" refers to the entire product, For example, the equation "(a^2)b + (b)c^4 = 0" has two terms: (a^2)b, and (b)c^4. The degree of the entire equation is the maximum of the degree of the individual terms. However, the degree of a term is the sum of the degree of all of the factors. For example, the equation "a+b+c=10" is degree 1, but "abc=10" is degree 3.
- jfaat 9y agoAh ok so he was talking about the degree of the equation but gave an example of calculating the degree of a term, the highest of which in any equation is its degree. That makes sense, thanks for clearing it up!
- ufo 9y agoIf I understood your question correctly, you are saying that the degree of a term should be the maximum degree between the vatiables in that term. So (a^2)(b^1)(c^4) ) would be of degree max(2,1,4) = 4. But with the definition he is using, the degree of a term in the equation is the sum of the degrees of the variables. So (a^2)(b^1)(c^4) has degree 2 + 1 + 4 = 7.
- jfaat 9y agoI don't think that's right. See the sibling comment, which made it click for me. He is saying the degree of a single term is the sum of the exponents in that term, and the degree of the equation is max(...all term degrees).
- mrkgnao 9y agoFor anyone looking to learn more about elliptic curves, which are astoundingly "well-connected" as math topics go, here's a good book that should be accessible to anyone with some calculus under their belt: https://www.amazon.com/Elliptic-Tales-Curves-Counting-Number/dp/0691151199 https://www.amazon.com/Elliptic-Tales-Curves-Counting-Number... It's not a textbook, which is both good and bad. In my case, it did a good job whetting my appetite for more! A really well-written and not-extremely-difficult undergrad textbook on elliptic curves: https://www.amazon.com/Rational-Points-Elliptic-Undergraduate-Mathematics/dp/331918587X https://www.amazon.com/Rational-Points-Elliptic-Undergraduat... (Non-affiliate links, just so you know.)
- mrkgnao 9y agoSo what do I mean by "well-connected"? Elliptic curves are associated with a) number theory - many questions about number theory boil down to finding points on elliptic curves with rational coordinates b) algebraic geometry - elliptic curves are very "nice" from this point of view, and they are complicated enough that you can say interesting things, but not so complicated that you can't say anything c) complex analysis - over the complex plane, an elliptic curve is a torus. You might have seen how a torus can be formed by identifying opposite edges of a square, and an elliptic curve is hence "a quotient of C by a square lattice". Modular forms, which are creatures of complex analysis with deep applications to number theory, are naturally defined in this framework. and many more things I don't know about. They're in a sort of "sweet spot" and act as a bridge between multiple parts of mathematics.
- onuralp 9y agoThese look fascinating, thanks. I tried to crack this problem, and ended up (very naively) resorting to substituting division with modulo operation that is, a%(b+c) + b%(a+c) + c%(a+b) = 4 of which the min solution is a=1, b=2, and c=4. I am glad that the true solution involved EC which, if my understanding is correct, is basically modular operations in high-dimensional space.
- mrkgnao 9y agoElliptic curves are "generalized modular arithmetic" only in the sense that they involve a different kind of addition law (the set of points on a nice EC is a group). Also, you can look at the points on an elliptic curve where you allow the coordinates to be real, complex, rational, or even the integers mod p (any field will do), so the last choice gives you a closer link with modular arithmetic. It's best to treat ECs as their own weird, wonderful beasts!
- ramshanker 9y agoNow eagerly waiting for Letsencrypt to make Elliptic curve as default. Respect to the author of the article.
- AbacusAvenger 9y agoThe Wolfram Alpha results for this one are pretty intimidating: http://www.wolframalpha.com/input/?i=(a%2F(b%2Bc))%2B(b%2F(a%2Bc))%2B(c%2F(a%2Bb))%3D4 http://www.wolframalpha.com/input/?i=(a%2F(b%2Bc))%2B(b%2F(a...
- masthead 9y agoOh, for the love of God, no forwards/quora/facebook/whatsapp forwards, atleast on HN! #cleanHN
- chegra 9y agox = 702 y = -390 z = 858 [ http://www.wolframalpha.com/input/?i=(702%2F(-390%2B858))%2B(-390%2F(702%2B858))%2B(858%2F(702%2B-390) http://www.wolframalpha.com/input/?i=(702%2F(-390%2B858))%2B...) ] Found the above solution using a hillclimbing algorithm. http://codepad.org/PixRUl0N http://codepad.org/PixRUl0N
- Ended 9y agoThe question asks for positive solutions, which turns out to be a bit harder!
- chegra 9y agoSorry...I was only going off of the title of the thread.
- sweezyjeezy 9y agoThey need to all be positive. FTA (on the solution x = 4, y = -1, y = 11) : > This solution is not easy to see by hand, but it’s also not hard to discover with some patience without all the machinery we are reviewing here. It’s the positive solutions that are the lair of dragons.
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- hazeii 9y ago~$ calc calc 2.12.4.1 > a=154476802108746166441951315019919837485664325669565431700026634898253202035277999 > b=36875131794129999827197811565225474825492979968971970996283137471637224634055579 > c=4373612677928697257861252602371390152816537558161613618621437993378423467772036 > a/(b+c) + b/(a+c) + c/(a+b) 4 > a/(b+c) ~3.74500615923925922050 > b/(a+c) ~0.23213745990937924275 > c/(a+b) ~0.02285638085136153676
- tim333 9y agoA bit tangential but I wonder if something like that could relate to the slightly odd collection of fundamental particles we find in physics. They have properties that have to come out integral like spin x 2 and charge x 3 and have odd values like muons and tao particle being basically electrons but approx 200 and 3500 times heavier.
- raybb 9y agoIf you count zero as a positive number then one solution is: 0, 109552575, 29354524 :)