Perhaps our two approaches can be reconciled with the following idea. Instead of starting with (0/1, 1/1), let's extend our ambit to all the positive rationals, and begin with (0/1, 1/0), and call that the 0-th row. Then the first row is (0/1, 1/1, 1/0), the second is (0/1, 1/2, 1/1, 2/1, 1/0), and so on. Because the interval from 0/1 to 1/1 has a head start on the rest of the rationals, the first occurrence of any given denominator will always be in the left half of the row; furthermore, it will be in the left half of the left half. Jim's indices are one smaller than mine, because he starts with just the left half. Now a little bit of new insight, and a connection to some existing sequences at OEIS. If we look at the denominators, on the 0-th row I have (1,0); on the first row (1, 1, 0); on the second row (1, 2, 1, 1, 0); and on the third row (1, 3, 2, 3, 1, 2, 1, 1, 0). Note that each row is a proper suffix of the following row. Reading from the right, we obtain a sequence with the definition a(0) = 0, a(1) = 1, a(2n) = a(n), a(2n+1) = a(n) + a(n+1). This is OEIS's A002487, "Stern's diatomic series[sic]", which is connected to Farey's construction and the Stern-Brocot tree, although this connection is not mentioned in OEIS. As noted in the Encyclopedia, a(2^n) = 1 for all n, and the material between a(2^n) and a(2^(n+1)) is the denominator sequence for the unit interval on the nth row of Jim's tableau. In other words, the new sequence's nth element gives the number of bits in the index of the first occurrence of n in Stern's diatomic series, perhaps with some off-by-one adjustments depending on whether you use Jim's coordinate system or mine. If we leave out the "number of bits" part, and just look for the first occurrence of a given number in A002487, we get A020946. The integer part of the binary log of A020946 gives 0, 1, 2, 3, 3, 5, 4 ... which should look familiar by now. On Fri, Dec 17, 2010 at 6:07 PM, James Propp <jpropp@cs.uml.edu> wrote:

Allan Wechsler wrote:

...

Aaaaaand I screwed up.

123446556666677777787; I left out a(6)=6.

My Mathematica code gives

{0,1,2,3,3,5,4,4,5,5,5,5,5,6,6,6,6,6,6,7,6,7,7,7,7,7,7,8,7,7,7,8,8,7,8,8,8,9,8,8,8,9,8,8,8,8,8,9,8,8,9,9,9,10,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,10,9,9,9,9,10,10,9,9,9,10,10,10,10,10,10,10,9,11,10,10,10,10,10,11,10,10,10,10}

as the earliest occurrences of the respective denominators (though mathematically speaking that initial "1" is a glitch and should really be a "0"). I can easily generate more terms if anyone wants me to, or you can do it yourself with my code:

FLengthen[L_] := Module[{i, M}, M = Table[0, {2 Length[L]}]; M[[1]] = Numerator[L[[1]]]/(1 + Denominator[L[[1]]]); For[i = 1, i < Length[L], i++, M[[2 i]] = L[[i]]; M[[2 i + 1]] = (Numerator[L[[i]]] + Numerator[L[[i + 1]]])/(Denominator[L[[i]]] + Denominator[L[[i + 1]]])]; M[[2 Length[L]]] = L[[Length[L]]]; Return[M]] F[n_] := F[n] = If[n == 0, {1}, FLengthen[F[n - 1]]] FEarliest[k_] := Module[{i}, For[i = 0, Length[Denom[F[i], k]] == 0, i++]; Return[i]]

To reconcile this with Allan's numbers, note that I call {0/0,1/1} the 0th row, {0/1,1/2,1/1} the 1st row, etc. My rationale for this choice is that the nth row has (2^n)+1 elements under my convention.

Jim

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun