Bill Gosper wrote: If your developers are leery of GCD[1,π]→0, I think I can muster authoritative corroborators, if not corroborative literature. Motivation: The gcd of two real quantities is the largest quantity that goes into each a whole number of times. [me:] I'm unconvinced. In this context (multiplicative rather than additive) 0 is *larger* than everything else, not *smaller*, no? [Bill:] Well, we *are* looking for the "greatest".-) Do you propose a different answer, or deny there is one?
I deny there is one, or at least that there is any number that has a good claim.
Please name one.
And 0 emphatically doesn't "go into" anything "a whole number of times".
Touché. New wording: GCD(a,b):= the limit of the Euclidean process of iteratively subtracting the smaller from the larger.
The *limit* of doing this for commensurable quantities is zero. The gcd is the last thing you get immediately before 0.
n[755]:= NestList[ Simplify[{Max[#] - Min[#], Min[#]}] &, {GoldenRatio - 1/2, 1/√5}, 6] Out[755]= {{-(1/2) + GoldenRatio, 1/√5}, {3/(2 √5), 1/√5}, {1/(2 √5), 1/√5}, {1/(2 √5), 1/(2 √5)}, {0, 1/(2 √5)}, {1/(2 √5), 0}, {1/(2 √5), 0}} So GCD[GoldenRatio - 1/2, 1/√5] is 1/(2√5) In[758]:= NestList[Simplify[{Max[#] - Min[#], Min[#]}] &, {69, 105}, 16] Out[758]= {{69, 105}, {36, 69}, {33, 36}, {3, 33}, {30, 3}, {27, 3}, {24, 3}, {21, 3}, {18, 3}, {15, 3}, {12, 3}, {9, 3}, {6, 3}, {3, 3}, {0, 3}, {3, 0}, {3, 0}} So GCD[69,105] is 3. In[761]:= NestList[Simplify[{Max[#] - Min[#], Min[#]}] &, {1, π}, 3 + 7 + 15 + 1] Out[761]= {{1, π}, {-1 + π, 1}, {-2 + π, 1}, {-3 + π, 1}, {4 - π, -3 + π}, {7 - 2 π, -3 + π}, {10 - 3 π, -3 + π}, {13 - 4 π, -3 + π}, {16 - 5 π, -3 + π}, {19 - 6 π, -3 + π}, {22 - 7 π, -3 + π}, {-25 + 8 π, 22 - 7 π}, {-47 + 15 π, 22 - 7 π}, {-69 + 22 π, 22 - 7 π}, {-91 + 29 π, 22 - 7 π}, {-113 + 36 π, 22 - 7 π}, {-135 + 43 π, 22 - 7 π}, {-157 + 50 π, 22 - 7 π}, {-179 + 57 π, 22 - 7 π}, {-201 + 64 π, 22 - 7 π}, {-223 + 71 π, 22 - 7 π}, {-245 + 78 π, 22 - 7 π}, {-267 + 85 π, 22 - 7 π}, {-289 + 92 π, 22 - 7 π}, {-311 + 99 π, 22 - 7 π}, {-333 + 106 π, 22 - 7 π}, {355 - 113 π, -333 + 106 π}} In[762]:= N[%] Out[762]= {{1., 3.14159}, {2.14159, 1.}, {1.14159, 1.}, {0.141593, 1.}, {0.858407, 0.141593}, {0.716815, 0.141593}, {0.575222, 0.141593}, {0.433629, 0.141593}, {0.292037, 0.141593}, {0.150444, 0.141593}, {0.00885142, 0.141593}, {0.132741, 0.00885142}, {0.12389, 0.00885142}, {0.115038, 0.00885142}, {0.106187, 0.00885142}, {0.0973355, 0.00885142}, {0.0884841, 0.00885142}, {0.0796327, 0.00885142}, {0.0707813, 0.00885142}, {0.0619298, 0.00885142}, {0.0530784, 0.00885142}, {0.044227, 0.00885142}, {0.0353756, 0.00885142}, {0.0265241, 0.00885142}, {0.0176727, 0.00885142}, {0.00882128, 0.00885142}, {0.0000301444, 0.00882128}} So GCD[1, π] is going to 0. Gareth>I agree that gcd(1,pi) can be thought of as a certain sort of
limit of real numbers that tend to 0 -- but I don't think the usual sort of limit is the right one, because the metric it implicitly invokes isn't the right one. --
g What's the right one? The smallest square you can make by dividing a rectangle into squares by the greedy algorithm is GCD(length,width). What could be more natural? --rwg
[The combination of the quoting convention I've been using and the quoting convention Bill's been using is incredibly confusing...] Bill Gosper wrote:
Well, we *are* looking for the "greatest".-) Do you propose a different answer, or deny there is one?
I (Gareth) replied:
I deny there is one, or at least that there is any number that has a good claim.
And Bill replied:
Please name one.
No, I *deny* that there is any number that has a good claim, so of course I can't name one. I'm sorry if I wasn't clear enough. To me, the gcd is defined by properties like these: "gcd(a,b) divides both a and b and is a multiple of anything else that does." "gcd(a,b) is the single generator of the (fractional) ideal generated by a,b." Zero doesn't have any of the right properties to be the gcd of 1 and pi. Nothing does. * Bill:
Touché. New wording: GCD(a,b):= the limit of the Euclidean process of iteratively subtracting the smaller from the larger.
Gareth:
The *limit* of doing this for commensurable quantities is zero. The gcd is the last thing you get immediately before 0.
Bill:
n[755]:= NestList[ Simplify[{Max[#] - Min[#], Min[#]}] &, {GoldenRatio - 1/2, 1/√5}, 6]
Out[755]= {{-(1/2) + GoldenRatio, 1/√5}, {3/(2 √5), 1/√5}, {1/(2 √5), 1/√5}, {1/(2 √5), 1/(2 √5)}, {0, 1/(2 √5)}, {1/(2 √5), 0}, {1/(2 √5), 0}}
So GCD[GoldenRatio - 1/2, 1/√5] is 1/(2√5)
Oh, OK, so you mean the limit of the larger one. Fair enough. (I still don't see that when you have a process that in "uncontroversial" cases terminates after finitely many steps it's necessarily right to say that in cases where it approaches a limit that's the right value to use.) -- g
GCD satisfies a universal property; in particular, it is a categorical product. We take as the category the poset whose objects are natural numbers ordered by divisibility (that is, we read x ≤ y as "x is a factor of y"). Then GCD(x,y) ≤ x and GCD(x,y) ≤ y such that for all z satisfying z ≤ x and z ≤ y, we have z ≤ GCD(x,y). If we want to allow rationals, then we can define x ≤ y to mean that for all i, the exponent on p_i in x is less than or equal to the exponent on p_i in y. Then GCD(1/2, 2/3) is 1/6. If we use the usual definition of ≤, we get MIN. If we use the subset relation, we get INTERSECT. If we use functions between sets, we get the cartesian product PAIR. Etc. On Thu, Nov 28, 2013 at 1:37 PM, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
[The combination of the quoting convention I've been using and the quoting convention Bill's been using is incredibly confusing...]
Bill Gosper wrote:
Well, we *are* looking for the "greatest".-) Do you propose a different answer, or deny there is one?
I (Gareth) replied:
I deny there is one, or at least that there is any number that has a good claim.
And Bill replied:
Please name one.
No, I *deny* that there is any number that has a good claim, so of course I can't name one. I'm sorry if I wasn't clear enough.
To me, the gcd is defined by properties like these: "gcd(a,b) divides both a and b and is a multiple of anything else that does." "gcd(a,b) is the single generator of the (fractional) ideal generated by a,b." Zero doesn't have any of the right properties to be the gcd of 1 and pi. Nothing does.
*
Bill:
Touché. New wording: GCD(a,b):= the limit of the Euclidean process of iteratively subtracting the smaller from the larger.
Gareth:
The *limit* of doing this for commensurable quantities is zero. The gcd is the last thing you get immediately before 0.
Bill:
n[755]:= NestList[ Simplify[{Max[#] - Min[#], Min[#]}] &, {GoldenRatio - 1/2, 1/√5}, 6]
Out[755]= {{-(1/2) + GoldenRatio, 1/√5}, {3/(2 √5), 1/√5}, {1/(2 √5), 1/√5}, {1/(2 √5), 1/(2 √5)}, {0, 1/(2 √5)}, {1/(2 √5), 0}, {1/(2 √5), 0}}
So GCD[GoldenRatio - 1/2, 1/√5] is 1/(2√5)
Oh, OK, so you mean the limit of the larger one. Fair enough.
(I still don't see that when you have a process that in "uncontroversial" cases terminates after finitely many steps it's necessarily right to say that in cases where it approaches a limit that's the right value to use.)
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (3)
-
Bill Gosper -
Gareth McCaughan -
Mike Stay