3 ms·

Oh, wow, beautiful. I wonder if there's a way to rephrase this as a diophantine approximation problem? If one ray must be axis-aligned then of course it's just

Oh, wow, beautiful. I wonder if there's a way to rephrase this as a diophantine approximation problem? If one ray must be axis-aligned then of course it's just the convergents for √3, but with two rays it's a little trickier.

Snawoot 8y ago
One can build arbitrary approximate angles using lattices. Lets assume we need 50 degrees angle and we have piece of paper with 100x100 cells. We can construct rightangled triangle and seek for closest legs proportion which gives desired angle between one of legs and hypotenuse. Desired proportion must be rational number closest to tan(50 deg). We can find such rational number by seeking Farey sequence limited with denominator less than 100. So, for this case triangle with 87 and 73 cell legs will give us 50.000644597558434 degrees angle. Looks pretty good result to me. I think, in case with two non-aligned rays we can reduce it to first case by building two triangles and constructing angle between hypotenuses. Useful links: https://en.wikipedia.org/wiki/Farey_sequence https://en.wikipedia.org/wiki/Farey_sequence https://www.oreilly.com/library/view/python-cookbook/0596001673/ch17s17.html https://www.oreilly.com/library/view/python-cookbook/0596001... - python implementation of search in Farey sequence.
svat 8y ago
We can indeed relate this problem to the “usual” Diophantine approximation problem of approximating a number α by a rational number p/q, but there's a twist. The “usual” problem, where we want p/q to be close to a real number α, can be thought of as finding Gaussian integers (q + ip) that lie close to the line y=αx in the complex plane, i.e. points z on the lattice such that Im(z)/Re(z) ≈ α. Here, with α=√3, we want to solve the same problem, i.e. find rational numbers p/q close to α, except that p/q must further be of the form (ad-bc)/(ac+bd) for some (a, b, c, d). Here's the thing: this is precisely the same as saying that (q + ip) is not a Gaussian prime! This is because (a-ib)(c+id) = (ac+bd) + i(ad-bc). (https://en.wikipedia.org/w/index.php?title=Brahmagupta%E2%80%93Fibonacci_identity&oldid=863796842 https://en.wikipedia.org/w/index.php?title=Brahmagupta%E2%80...) So any (q + ip) of the form (ac+bd) + i(ad-bc) can be written as the product of two Gaussian integers, and vice-versa. So the relation between the Diophantine approximation problem and this one is that while there we want to find Gaussian integers close to the line Im(z)=αRe(z), here we want to find composite Gaussian integers close to the line Im(z)=αRe(z). (Note we can get different "best" approximations depending on how we measure closeness; see my other comment here: https://news.ycombinator.com/item?id=18555240 https://news.ycombinator.com/item?id=18555240 Also, I expect that as denominators get larger, the primes get sparser, so this becomes closer to the usual problem. Of course in the original post linked here, the goal is to find small solutions, so the difference matters.)

Snawoot 8y ago

One can build arbitrary approximate angles using lattices. Lets assume we need 50 degrees angle and we have piece of paper with 100x100 cells. We can construct rightangled triangle and seek for closest legs proportion which gives desired angle between one of legs and hypotenuse. Desired proportion must be rational number closest to tan(50 deg). We can find such rational number by seeking Farey sequence limited with denominator less than 100. So, for this case triangle with 87 and 73 cell legs will give us 50.000644597558434 degrees angle. Looks pretty good result to me. I think, in case with two non-aligned rays we can reduce it to first case by building two triangles and constructing angle between hypotenuses. Useful links: https://en.wikipedia.org/wiki/Farey_sequence https://en.wikipedia.org/wiki/Farey_sequence https://www.oreilly.com/library/view/python-cookbook/0596001673/ch17s17.html https://www.oreilly.com/library/view/python-cookbook/0596001... - python implementation of search in Farey sequence.

svat 8y ago

We can indeed relate this problem to the “usual” Diophantine approximation problem of approximating a number α by a rational number p/q, but there's a twist. The “usual” problem, where we want p/q to be close to a real number α, can be thought of as finding Gaussian integers (q + ip) that lie close to the line y=αx in the complex plane, i.e. points z on the lattice such that Im(z)/Re(z) ≈ α. Here, with α=√3, we want to solve the same problem, i.e. find rational numbers p/q close to α, except that p/q must further be of the form (ad-bc)/(ac+bd) for some (a, b, c, d). Here's the thing: this is precisely the same as saying that (q + ip) is not a Gaussian prime! This is because (a-ib)(c+id) = (ac+bd) + i(ad-bc). (https://en.wikipedia.org/w/index.php?title=Brahmagupta%E2%80%93Fibonacci_identity&oldid=863796842 https://en.wikipedia.org/w/index.php?title=Brahmagupta%E2%80...) So any (q + ip) of the form (ac+bd) + i(ad-bc) can be written as the product of two Gaussian integers, and vice-versa. So the relation between the Diophantine approximation problem and this one is that while there we want to find Gaussian integers close to the line Im(z)=αRe(z), here we want to find composite Gaussian integers close to the line Im(z)=αRe(z). (Note we can get different "best" approximations depending on how we measure closeness; see my other comment here: https://news.ycombinator.com/item?id=18555240 https://news.ycombinator.com/item?id=18555240 Also, I expect that as denominators get larger, the primes get sparser, so this becomes closer to the usual problem. Of course in the original post linked here, the goal is to find small solutions, so the difference matters.)