A possible approach: Suppose a consecutive pair of fractions is p/q, t/u, with mediant r/s. Define the Gap between two fractions as den1*num2-den2*num1. If the mediant doesn't reduce, r = p+t, s=q+u. The gaps between the fractions are tq-pu before inserting the mediant, and rq-ps = st-ru (= tq-pu) after the insertion. If the mediant reduces by g, the new gaps are equal to the old gap divided by g. As we proceed through the Propp iteration, the gaps never increase, and some are replaced by divisors. In a Farey sequence, the gaps are all 1. Whenever a Propp gap is 1, all the intermediate rationals appear -- just as in that section of the Farey sequence, although the time of appearance is jumbled. (Jim puts in all mediants in each iteration, while the regular Farey iteration is slower, limiting the new mediants at each stage to restrict the denominators.) Maybe analyzing the denominators mod g would be useful. Rich ----- Quoting James Propp <jamespropp@gmail.com>:
If you start with two arbitrary (positive) rational numbers p,q and start iteratively interpolating mediants, and you reduce every unreduced fraction you encounter to lowest terms, do you get all the rationals between p and q?
Example: Start with 1/2 and 3/1. 1/2 3/1 gives 1/2 4/3 3/1 gives 1/2 1/1 4/3 7/4 3/1 gives 1/2 2/3 1/1 5/4 4/3 11/7 7/4 2/1 3/1 etc.
After n rounds of mediant interpolation, you have 2^n+1 fractions.
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun