A064881 Eisenstein array Ei(1,2).

1, 2, 1, 3, 2, 1, 4, 3, 5, 2, 1, 5, 4, 7, 3, 8, 5, 7, 2, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19, 7, 16, 9, 11, 2

Offset: 1

Author

Wolfdieter Lang, Oct 19 2001

Keywords

• nonn
• easy
• tabf

Comments

In Eisenstein's notation this is the array for m=1 and n=2; see example in given reference p. 42. The array for m=n=1 is A049456.

For n >= 1, the number of entries of row n is 2^(n-1)+1 with the difference sequence [2,1,2,4,8,16,...]. Row sums give 3*A007051(n-1).

The binary tree built from the rationals a(n,m)/a(n,m+1), m=0..2^(n-1), for each row n >= 1 gives the subtree of the (Eisenstein-)Stern-Brocot tree in the version of, e.g., Calkin and Wilf (for the reference see A002487 and the link) with root 1/2. The composition rule for this tree is i/j -> i/(i+j), (i+j)/j.

Examples

			{1,2};
{1,3,2};
{1,4,3,5,2};
{1,5,4,7,3,8,5,7,2}; ...
This binary subtree of rationals is built from
1/2;
1/3, 3/2;
1/4, 4/3, 3/5, 5/2; ...
		

Links

• R. Backhouse, J. F. Ferreira, On Euclid’s algorithm and elementary number theory, Sci. Comput. Program. 76, No. 3, 160-180 (2011).
• N. Calkin and H. S. Wilf, Recounting the Rationals, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.
• F. G. M. Eisenstein, Eine neue Gattung zahlentheoretischer Funktionen, welche von zwei Elementen abhaengen und durch gewisse lineare Funktional-Gleichungen definirt werden, Verhandlungen der Koenigl. Preuss. Akademie der Wiss. Berlin (1850) 36-42, Feb 18, 1850. Werke, II, pp. 705-711.
• Index entries for sequences related to Stern's sequences

Programs

Mathematica

nmax = 6; a[n_, m_?EvenQ] := a[n - 1, m/2]; a[n_, m_?OddQ] := a[n, m] = a[n - 1, (m - 1)/2] + a[n - 1, (m + 1)/2]; a[1, 0] = 1; a[1, 1] = 2; Flatten[ Table[a[n, m], {n, 1, nmax}, {m, 0, 2^(n - 1)}]] (* Jean-François Alcover, Sep 27 2011 *)
eisen = Most@Flatten@Transpose[{#, # + RotateLeft[#]}] &;
Flatten@NestList[eisen, {1, 2}, 6] (* Harlan J. Brothers, Feb 18 2015 *)

Formula

a(n, m) = a(n-1, m/2) if m is even, else a(n, m) = a(n-1, (m-1)/2) + a(n-1, (m+1)/2), a(1, 0)=1, a(1, 1)=2.