A174981 Numerators of the L-tree, left-to-right enumeration.
0, 1, 1, 2, 3, 1, 2, 3, 5, 2, 5, 3, 4, 1, 3, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 4, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 5, 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
Offset: 0
Examples
The sequence splits into rows of length 2^k: 0, 1, 1, 2, 3, 1, 2, 3, 5, 2, 5, 3, 4, 1, 3, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 4, ... The fractions are 0/1, 1/2, 1/1, 2/3, 3/2, 1/3, 2/1, 3/4, 5/3, 2/5, 5/2, 3/5, 4/3, 1/4, 3/1, 4/5, 7/4, 3/7, 8/3, 5/8, 7/5, 2/7, 7/2, 5/7, 8/5, 3/8, 7/3, 4/7, 5/4, 1/5, 4/1, ...
Links
- Edsger Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232. EWD 578: More about the function fusc.
- Peter Luschny, Rational Trees and Binary Partitions.
- Moritz A. Stern, Über eine zahlentheoretische Funktion, J. Reine Angew. Math., 55 (1858), 193-220.
Programs
-
Maple
SternDijkstra := proc(L, p, n) local k, i, len, M; len := nops(L); M := L; k := n; while k > 0 do M[1+(k mod len)] := add(M[i], i = 1..len); k := iquo(k, len); od; op(p, M) end: Ltree := proc(n) 5*2^ilog2(n+1); SternDijkstra([0,1], 1, n + 2 + %) / SternDijkstra([1,0], 2, n + 2) end: a := proc(n) 5*2^ilog2(n+1); SternDijkstra([0,1], 1, n + 2 + %) end: seq(a(n), n=0..90);
-
Mathematica
SternDijkstra[L_, p_, n_] := Module[{k, i, len, M}, len := Length[L]; M = L; k = n; While[k > 0, M[[1 + Mod[k, len]]] = Sum[M[[i]], {i, 1, len}]; k = Quotient[k, len]]; M[[p]]]; Ltree[n_] := With[{k = 5*2^Simplify[ Floor[ Log[2, n + 1]]]}, SternDijkstra[{0, 1}, 1, n + 2 + k]/ SternDijkstra[{1, 0}, 2, n + 2]]; a[0] = 0; a[n_] := With[{k = 5*2^Simplify[ Floor[ Log[2, n + 1]]]}, SternDijkstra[{1, 0}, 1, n + 2 + k]]; row[0] = {a[0]}; row[n_] := Table[a[k], {k, 2^n - 3, 2^(n+1) - 4}] // Reverse; Table[row[n], {n, 0, 6}] // Flatten (* Jean-François Alcover, Jul 26 2013, after Maple *)
Comments