Hacker News new | past | comments | ask | show | jobs | submit login
How do you find integer solutions to x/(y + z) + y/(x + z) + z/(x + y) = 4? (quora.com)
446 points by jordigh on Aug 6, 2017 | hide | past | web | favorite | 94 comments



For 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...

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-Undergraduat...

(Non-affiliate links, just so you know.)


So 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.


These 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.


Elliptic 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!


This 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.


I admit, I had low expectations with it being on Quora. I was far from disappointed, though.


Really? 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.


Agreed. 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.


How does Quora works? I regularly see very interesting answers there. While it looks like SO clone, its content is different. Do they pay for good answers? Or they just happen to have bright people in their community?


The difference seems to be in the culture of the community, which they've done a good job of cultivating from day 1.

Quality is valued, and so are expert opinions. I doubt they pay anybody.


Any questions/answers in particular you would recommend reading?


No 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/Sridhar-Ramesh


The Wolfram Alpha results for this one are pretty intimidating:

http://www.wolframalpha.com/input/?i=(a%2F(b%2Bc))%2B(b%2F(a...


You can ask for integer solutions in Mathematica with

> Solve[x/(y + z) + y/(z + x) + z/(x + y) == 4, {x, y, z}, Integers]

but it gives a very long output in terms of Root[]s and conditional expressions.


I initially tried that on WolframAlpha but it doesn't understand Mathematica syntax. But one can enter it on https://lab.wolframcloud.com after creating an account.


Thanks. At least I could check the solution there and it is correct.


I got "Standard computation time exceeded...".


In the title, read "and" as "plus". (For a while I thought they meant "logical AND", given the HN context.)


Yeah, I wrote "+" but HN turned it to "and".


Just 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? :)


Let'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.


Makes sense. Nice proof :)


It 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.


For 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.


Sorry, that's the rare case where we actually want +. Fixed above.


Why does that have to be the rare case? What's the common case of using "+" that you're trying to avoid?


"Microsoft + Apple will both.." I imagine people use + to get by character limit in the title.


>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?


They 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.


For future reference, when someone really wants a plus sign would using Unicode FF0B (full width plus) get past the automatic "and" conversion?


We 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.


I 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:

++++++++++

++++++++++


> 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.


The 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.


Ah 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!


The author defined degree poorly. a monomial x0^e0x1^e1...xn^en has degree e1+e2+...+en. A polynomial's degree is the highest degree of any of it's monomials.

Degree has the property that Deg(P1P2)=Deg(P1)Deg(P2)

How do I escape asterisks?


If 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.


I 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).


Thanks for the comments everyone. I clarified the definition of "degree" in that paragraph, it indeed wasn't well written.


What are some other problems that appear deceptively simple, but are extremely difficult to solve?


Let n be a positive integer.

Let s(n) be the sum of all positive divisors of n. E.g., s(2) = 1 + 2, s(4) = 1 + 2 + 4, s(20) = 1 + 2 + 4 + 5 + 10 + 20.

Let H(n) = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n.

Question: is it true that s(n) < H(n) + log(H(n)) exp(H(n)) for all n > 1?

(log is natural logarithm)

It turns out that this simple looking problem is equivalent to the Riemann Hypothesis, which is perhaps the most important unsolved problem in pure mathematics. Many of the best minds in mathematics have attempted it in the approximately 160 years since Riemann posed it.

What equivalent means in this context is that if the Riemann Hypothesis is true, than the inequality above is also true, and if the inequality above is true, then the Riemann hypothesis is true.


Maybe just me, but that problem does not look very simple at all. One reason OP's problem is appealing, is because the solution can be easily checked. The solution is a kind of "proof of work". You could never guess the solution without a deep understanding of the problem. But once found, the solution is immediately verifiable.

For many problems one can easily guess the solution, without necessarily knowing the proof (like Fermat did). The answer is almost certainly negative, and a complete solution requires a very long and tedious proof that cannot be checked without a deep understanding of the field and many years of collective effort.

I am specifically interested in problems which can be understood by a child, have hard solutions which cannot be easily guessed, but are easily verified (ex. factoring the product of two large primes). It seems like these problems would make good candidates for one-way-functions, like the diophantine equations and ECC. But elliptic curve cryptology is too difficult to describe to a child.


Quite easy to explain given a few graphs. The explanation boils down on how hard is to accurately draw a curve of such an elliptic function at big x (P3) and then figure out which two other points intersect with a given line near. You can even show it on a big whiteboard.

You can even show how easy out would be for a simple curve where the left part is an easy equation.

The hard part is what makes an equation easy to solve. (And how some elliptic are broken.) It takes at least some high school math to hint at this.


Try this, find the cubic root of 27 by hand. No computer!


Speaking of divisors, there are infinite numbers n such that n and n+1 have the same number of divisors. AFAIK we do not have a way to find such an n > N for any given N without calculating an infinitely growing sequence.


Is there a number which can be written in base 2,3,4,5,6 using only 0 and 1?

What's mind blowing here is that if you ask for base 2, 3, 4 the answers are trivial but for bases 2,3,4,5 somehow you get 82000 and we do not know whether there is another and for 6 it's unknown.


Am I missing something? the number 1 is 1 in all of those bases and therefore can be written using 0 (0 times) and 1 (1 time).


Sometimes mathematicians forget to say "non-trivial", that's what you're missing.


Often in mathematics, we look for the nontrivial solutions to questions like this.


In general, number theory is notorious for containing many questions that are accessible to a layperson but whose proofs rely on arguments that are so difficult that even the basic idea of how the argument works takes many years of study.

Fermat's last theorem is an example, because it can be shown to be equivalent to, among other things, a very deep statement about elliptic curves (yep, the same thing The Fine Answer is about!) that Andrew Wiles proved.

https://en.wikipedia.org/wiki/Modularity_theorem


From 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.


from 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.


Conway 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.


I suspect it is due to the lack of application for the solution.

I analyzed the problem for a while and theorized ways to collaboratively contribute to the solution. I settled on submitting an integer sequence to OEIS.

http://oeis.org/A261393


True. 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.


My favorite example are a few simple-seeming polynomials with integer solutions. (Equations that we want to solve for integers are called "Diophantene equations".)

Here's one that's genuinely easy:

  x^3 + y^3 + z^3 = 29
The solution is x = 1, y = 1, z = 3 (or any permutation thereof).

So how about this one?

  x^3 + y^3 + z^3 = 30
Play around a bit.

Not so easy.

But it does have a solution!

Here it is:

  x = -283059965	

  y = -2218888517	

  z = 2220422932
And what about x^3 + y^3 + z^3 = 33? There is no known solution. It's an open problem!

This is a great visceral demonstration that Diophantene equations are hard: there can exist no algorithm that solves all of them. Diophantene equations, like the Halting Problem, are undecidable.


Can you find (possibly negative) integers x, y, and z, such that x ^ 3 + y ^ 3 + z ^ 3 == 33? If so, it's publication-worthy.


Is the constant 33 important (ie. would it be any less significant if it were 42, or 74 instead) and if so, why?


I was replying that the constants in question include 33, 42 and 74... and realized that I'm late :-) In a more recent survey, though, it is now known that:

> 74 = −284650292555885^3 + 66229832190556^3 + 283450105697727^3 [1] [2].

[1] https://arxiv.org/pdf/1604.07746v1.pdf

[2] https://mathoverflow.net/a/223121


what if I can prove there is no integer solution for it? Is it still publication-worthy?


Even more so!


Another one is Goldbach's Conjecture, which has been verified upto 4E18, but is still unproved.


I would say the collatz conjecture is up there. It's been an entry point for many people into the computational side of mathematics.

Take any positive whole number, n.

If it is even, divide it by 2. (n = 2n)

If it odd, multiply it by 3 and add one. (n = 3n + 1)

Repeat. If n = 1, stop.

Does this process always lead to 1? It seems to, but who knows.

https://en.wikipedia.org/wiki/Collatz_conjecture


Fermat's last theorem is probably the most obvious one.


On an infinite square grid where lines are 1 unit apart, if a circle of radius "r" is centered on an intersection, how many intersections lie within the circle? Answer in terms of "r".


Does n^pi = m have any nontrivial integer solutions?

Does the fractional part of e^n tend to zero?


Agree, good article. Thanks to it I think I understand more why cryptography based on elliptic curves (like Curve25519) is considered pretty safe for now.


x = 702

y = -390

z = 858

[ http://www.wolframalpha.com/input/?i=(702%2F(-390%2B858))%2B...) ]

Found the above solution using a hillclimbing algorithm.

http://codepad.org/PixRUl0N


They 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.


The question asks for positive solutions, which turns out to be a bit harder!


Sorry...I was only going off of the title of the thread.


~$ 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


A 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.


I wonder if a SAT solver would be able to solve this faster than brute force.


Yes. 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/


You 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.


Anything 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.


Does 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.


Int is usually signed. Unsigned int is not signed.


using 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.


That doesn't equal 4 it equals 4.00000009534. So, there is a precision issue, probably using floats to keep division results.


I 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 :)


sig figs are just an informal way of dealing with uncertainty that can be applied procedurally by high school students.


It's not about uncertainty, it's about precision. Unless, of course, you think that scientific notation is limited to only high schools.


What do you think the difference between precision and uncertainty is?


'Uncertainty' is a much more ambiguous term that means many more things than 'imprecision of measurement'.

Still, I'm interested to hear why you think sig figs are high-school only when they're the standard way of writing in scientific notation. Do you genuinely think that the example I gave from the video is reasonable? It sounds like you're a theorist and have no experience in real-world application.


Comes out as 167820976/41955243 in lowest terms, which isn't quite 4.


Language 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


Unfortunately, 4.00000009534 is not 4 :)


If 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!


Now eagerly waiting for Letsencrypt to make Elliptic curve as default. Respect to the author of the article.


If you count zero as a positive number then one solution is:

0, 109552575, 29354524 :)


[flagged]


This is a fantastic article. Perhaps a case of "don't judge a book by it's cover."


What's the problem that you have with the content? I thought that it was a pretty cool dive into elliptic curve mathematics.




Registration is open for Startup School 2019. Classes start July 22nd.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: