[math-fun] Defending fractions as a Countable Set
Over at Reddit, http://i.imgur.com/tDSX24E.jpg is getting a lot of attention. https://www.reddit.com/r/math/comments/3k1qe6/this_is_in_a_high_school_math_... In short, the textbook Glencoe Algebra II claims that there is no relation between the integers and the rationals. Georg Cantor showed it in the 1870's. There is also Calkin-Wilf and Stern-Brocat CalkinWilfPosition[r_] := With[{cf = ContinuedFraction[r]}, First@FromDigits[ Flatten@MapIndexed[Table[Mod[#2[[1]], 2], {#1}] &, Reverse@#], {2}] &@ If[EvenQ[Length[cf]], MapAt[Sequence @@ {# - 1, 1} &, cf, -1], cf]]; CalkinWilfRational[n_Integer] := Module[{s0, s1}, s0 = IntegerDigits[n, 2]; s1 = If[EvenQ[Length[#]], MapAt[(Sequence @@ {#, {}}) &, #, -1], #] &@Split[s0]; FromContinuedFraction[Reverse[Length /@ s1]]]; AlmostBitReverse[n_] := FromDigits[ Prepend[Reverse[Drop[IntegerDigits[n, 2], 1]], 1], 2]; SternBrocatPosition[fraction_] := AlmostBitReverse[CalkinWilfPosition[fraction]]; SternBrocatRational[n_Integer] := CalkinWilfRational[AlmostBitReverse[n]]; I figured that the relationship between these would be in OEIS -- and they are. https://oeis.org/A059893 -- but this doesn't mention the relation. But it's how I came up with the Stern-Brocat code. If you order either set of fractions, the position in the other set is given by A059893 --Ed Pegg Jr.
Apparently it's only in a "chapter study guide" that goes along with the algebra book: http://nseuntj.weebly.com/uploads/1/8/2/0/18201983/2.1relations_and_function... page 10 On Tue, Sep 8, 2015 at 2:02 PM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
Over at Reddit, http://i.imgur.com/tDSX24E.jpg is getting a lot of attention.
https://www.reddit.com/r/math/comments/3k1qe6/this_is_in_a_high_school_math_...
In short, the textbook Glencoe Algebra II claims that there is no relation between the integers and the rationals. Georg Cantor showed it in the 1870's.
There is also Calkin-Wilf and Stern-Brocat
CalkinWilfPosition[r_] := With[{cf = ContinuedFraction[r]}, First@FromDigits[ Flatten@MapIndexed[Table[Mod[#2[[1]], 2], {#1}] &, Reverse@#], {2}] &@ If[EvenQ[Length[cf]], MapAt[Sequence @@ {# - 1, 1} &, cf, -1], cf]];
CalkinWilfRational[n_Integer] := Module[{s0, s1}, s0 = IntegerDigits[n, 2]; s1 = If[EvenQ[Length[#]], MapAt[(Sequence @@ {#, {}}) &, #, -1], #] &@Split[s0]; FromContinuedFraction[Reverse[Length /@ s1]]];
AlmostBitReverse[n_] := FromDigits[ Prepend[Reverse[Drop[IntegerDigits[n, 2], 1]], 1], 2];
SternBrocatPosition[fraction_] := AlmostBitReverse[CalkinWilfPosition[fraction]];
SternBrocatRational[n_Integer] := CalkinWilfRational[AlmostBitReverse[n]];
I figured that the relationship between these would be in OEIS -- and they are. https://oeis.org/A059893 -- but this doesn't mention the relation. But it's how I came up with the Stern-Brocat code. If you order either set of fractions, the position in the other set is given by A059893
--Ed Pegg Jr. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://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
On 2015-09-08 14:49, Mike Stay wrote:
Apparently it's only in a "chapter study guide" that goes along with the algebra book: http://nseuntj.weebly.com/uploads/1/8/2/0/18201983/2.1relations_and_function... page 10
Good grief, after miscounting the rationals, Exercise 3 wants you to discover Cantor diagonalization! I wonder if any clever young Texans thought of: Write all the positive integers in some base like decimal or binary. For each integer, delete alternate digits, and divide by the integer the deleted digits represent. This will create every rational number endlessly often. Clearly there can't be a 1-1 correspondence--there are vastly too many integers. Really bijecting requires proving Ed's code, below. The forward single-step: newman[x_] := 1/(2*Floor[x] - x + 1) = -1/oldman[-1/x], where oldman is the backward step: oldman[x_] := 2*Ceiling[1/x] - 1 - 1/x = -1/newman[-1/x] E.g., In[523]:= NestList[newman, 0, 9] Out[523]= {0, 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3} In[529]:= NestList[oldman, 4/3, 9 + 1] During evaluation of In[529]:= Infinity::indet: Indeterminate expression -1+ComplexInfinity+ComplexInfinity encountered. >> Out[529]= {4/3, 1/4, 3, 2/3, 3/2, 1/3, 2, 1/2, 1, 0, Indeterminate} On 11/21/13 I posted here NeilB's version of Ed's code below, along with noting that iterating oldman on an irrational *very* gradually eats off the leading terms of its continued fraction. --rwg
On Tue, Sep 8, 2015 at 2:02 PM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
Over at Reddit, http://i.imgur.com/tDSX24E.jpg is getting a lot of attention.
https://www.reddit.com/r/math/comments/3k1qe6/this_is_in_a_high_school_math_...
In short, the textbook Glencoe Algebra II claims that there is no relation between the integers and the rationals. Georg Cantor showed it in the 1870's.
There is also Calkin-Wilf and Stern-Brocat
(Moritz Stern's credit-sharer was Achille Brocot.)
CalkinWilfPosition[r_] := With[{cf = ContinuedFraction[r]}, First@FromDigits[ Flatten@MapIndexed[Table[Mod[#2[[1]], 2], {#1}] &, Reverse@#], {2}] &@ If[EvenQ[Length[cf]], MapAt[Sequence @@ {# - 1, 1} &, cf, -1], cf]];
CalkinWilfRational[n_Integer] := Module[{s0, s1}, s0 = IntegerDigits[n, 2]; s1 = If[EvenQ[Length[#]], MapAt[(Sequence @@ {#, {}}) &, #, -1], #] &@Split[s0]; FromContinuedFraction[Reverse[Length /@ s1]]];
AlmostBitReverse[n_] := FromDigits[ Prepend[Reverse[Drop[IntegerDigits[n, 2], 1]], 1], 2];
SternBrocatPosition[fraction_] := AlmostBitReverse[CalkinWilfPosition[fraction]];
SternBrocatRational[n_Integer] := CalkinWilfRational[AlmostBitReverse[n]];
I figured that the relationship between these would be in OEIS -- and they are. https://oeis.org/A059893 -- but this doesn't mention the relation. But it's how I came up with the Stern-Brocat code. If you order either set of fractions, the position in the other set is given by A059893
--Ed Pegg Jr. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Ed Pegg Jr -
Mike Stay -
rwg