Re: [math-fun] Z^2 scale/rotate/translate puzzle
As the Sesame Street Martians say, Yyyyyyyep. Yyyyep. Yep-yep-yep-yep-yep-yep. GCD is the next best thing to factoring. GCD of Gaussian integers looks slightly trickier than the ordinary version. My brain says "I don't want to learn a whole new skill!" and I have to tell it, "You put your shoes on, stop hiding in your comfort zone, go outside and have some math-fun young man." --Steve
From: Allan Wechsler <acwacw@gmail.com> Date: 10/22/20, 11:32 AM
Yes. Then take the GCD of all the remaining points (considered as Gaussian integers), and divide out by the GCD to obtain the solution.
On Thu, Oct 22, 2020 at 1:19 AM Steve Witham <sw@tiac.net> wrote:
Not only does reflection not matter to the problem, but translate the problem so that one original point is (0, 0) and let the same point in the solution be (0, 0).
From: Henry Baker <hbaker1@pipeline.com> Date: 10/21/20, 10:27 AM
I'm guessing factorization of Gaussian integers is involved...
At 12:51 AM 10/21/2020, Tom Karzes wrote:
Here's a puzzle some of you might like:
(fin)
Steve Witham writes:
GCD of Gaussian integers looks slightly trickier than the ordinary version. My brain says "I don't want to learn a whole new skill!" and I have to tell it, "You put your shoes on, stop hiding in your comfort zone, go outside and have some math-fun young man."
As I mentioned in my earlier mail, the Euclidean algorithm works perfectly well with Gaussian integers, provided you have the proper remainder function. Here's the core of the Python code for my Gaussian GCD method: while v2 != 0: v1, v2 = v2, v1.irem(v2) This is followed by a step that forces the result into a canonical form by multiplying by the proper unit, but that part is trivial. The irem method just returns: v1 - v2 * v1.idiv(v2) The idiv method is only slightly trickier. It divides v1 by v2 to obtain a Gaussian rational, then for both the real and imaginary rationals, it does an integer divide of the numerator by the denominator to obtain integer real and imaginary parts. Different results can be obtained depending on how the integer divide is done (i.e., how the result is rounded). For my version, I used floor(v + 1/2). This minimizes the norm of the difference between the Gaussian rational result and the Gaussian integer result. Specifically, if the (exact) Gaussian rational result is x + i*y, and the (rounded) Gaussian integer result is m * i*n, then this guarantees that: -1/2 <= x - m < 1/2 -1/2 <= y - n < 1/2 which is achieved with: m = floor(x + 1/2) n = floor(y + 1/2) Tom
On 23/10/2020 04:48, Tom Karzes wrote:
As I mentioned in my earlier mail, the Euclidean algorithm works perfectly well with Gaussian integers, provided you have the proper remainder function. Here's the core of the Python code for my Gaussian GCD method: [etc.]
The way I think it's usually expressed by fancypants algebraists is: a ring (actually, it had better be an integral domain) is "euclidean" if there's a function f mapping its nonzero elements to the non-negative integers (think of this as being like the absolute value) such that for any a,b in the ring either b=0 or else you can write a = qb+r with r=0 or f(r) < f(b). Then you define "remainder" to be the operation that takes a,b and gives you r (any such r). And then your GCD algorithm repeatedly replaces a,b with b,r until you have b=0. This works in the ordinary integers, of course. It works in the Gaussian integers, taking f(x) = |x| and (e.g.) picking q = nearest Gaussian integer to a/b. It works in Q[X], the polynomials with rational coefficients, picking f(p) = degree(p). (But not in Z[X], where you can't always reduce the degree that way; consider trying to divide X by 2.) The theorem beloved of those fancypants algebraists is that if your ring is euclidean then it's a "principal ideal domain", which in turn means that it's a "unique factorization domain", meaning that everything factors essentially-uniquely into irreducibles and units. -- g
It works with rationals and Gaussian rationals too. In the case of rationals, the integer quotient is an integer and the remainder is a rational. In the case of Gaussian rationals, the Gaussian integer quotient is a Gaussian integer and the remainder is a Gaussian rational. For example: gcd(6/5, 15/17) = 3/85 with: (6/5) / (3/85) = 34 (15/17) / (3/85) = 25 and: gcd((-21/5)+(69/10)*i, (-25/18)+(5/3)*i) = (1/30)+(2/45)*i with: ((-21/5)+(69/10)*i) / ((1/30)+(2/45)*i) = 54+135*i ((-25/18)+(5/3)*i) / ((1/30)+(2/45)*i) = 9+38*i The unique factorization domain property is useful. Prime factorization works for rationals and Gaussian rationals as well. You just end up with negative exponents for some of the prime factors. For example, the prime factorization of: (6/35)+(10/21)*i is: (1+i)^3 * (2+i)^-1 * (1+2*i)^-1 * 3^-1 * 7^-1 * (17+8*i) Tom Gareth McCaughan writes:
On 23/10/2020 04:48, Tom Karzes wrote:
As I mentioned in my earlier mail, the Euclidean algorithm works perfectly well with Gaussian integers, provided you have the proper remainder function. Here's the core of the Python code for my Gaussian GCD method: [etc.]
The way I think it's usually expressed by fancypants algebraists is: a ring (actually, it had better be an integral domain) is "euclidean" if there's a function f mapping its nonzero elements to the non-negative integers (think of this as being like the absolute value) such that for any a,b in the ring either b=0 or else you can write a = qb+r with r=0 or f(r) < f(b).
Then you define "remainder" to be the operation that takes a,b and gives you r (any such r). And then your GCD algorithm repeatedly replaces a,b with b,r until you have b=0.
This works in the ordinary integers, of course. It works in the Gaussian integers, taking f(x) = |x| and (e.g.) picking q = nearest Gaussian integer to a/b. It works in Q[X], the polynomials with rational coefficients, picking f(p) = degree(p). (But not in Z[X], where you can't always reduce the degree that way; consider trying to divide X by 2.)
The theorem beloved of those fancypants algebraists is that if your ring is euclidean then it's a "principal ideal domain", which in turn means that it's a "unique factorization domain", meaning that everything factors essentially-uniquely into irreducibles and units.
-- g
participants (3)
-
Gareth McCaughan -
Steve Witham -
Tom Karzes