cp's OEIS Frontend

A253272 Triangular array read by rows: T(h,k) = number of steps from (h,k) to (0,0), where one step is (x,y) -> (x-1, y) if x is odd or (x,y) -> (y, x/2) if x is even, except that (2,0) -> (1,0).

%I A253272 #11 May 04 2015 15:33:15
%S A253272 0,1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,5,6,6,6,6,5,6,6,7,6,7,6,6,6,7,7,7,7,
%T A253272 7,7,6,7,7,8,7,8,7,8,7,7,7,8,8,8,8,8,8,8,8,7,8,7,9,8,9,8,9,8,9,8,8,8,
%U A253272 8,8,9,9,9,9,9,9,9,9,7,9,8,9,8,10,9,10
%N A253272 Triangular array read by rows: T(h,k) = number of steps from (h,k) to (0,0), where one step is (x,y) -> (x-1, y) if x is odd or (x,y) -> (y, x/2) if x is even, except that (2,0) -> (1,0).
%C A253272 For n>=3, the number of pairs (h,k) satisfying T(h,k) = n is L(n-1), where L = A000032, the Lucas numbers.  The number of such pairs having odd n is L(n-3) for n >= 4, and the number having even n is L(n-2) for n >= 3.
%C A253272 Let c(n,k) be the number of pairs (h,k) satisfying T(h,k) = n; in particular, c(n,0) is the number of integers (pairs of the form (h,0)) satisfying T(h,0) = n.  Let p(n) = A000931(n).  Then c(n,0) = p(n+3) for n >= 2.  More generally, for fixed k >=0, the sequence satisfies the recurrence r(n) = r(n-2) + r(n-3) except for initial terms.
%C A253272 The greatest h for which some (h,k) is n steps from (0,0) is H = A029744(n) for n >= 2, and the only such pair is (H,0).
%C A253272 See A257569 for a very similar array for which the number of pairs (h,k) satisfying T(h,k) = n is F(n), where F = A000045, the Fibonacci numbers.
%H A253272 Clark Kimberling, <a href="/A253272/b253272.txt">Table of n, a(n) for n = 1..1000</a>
%e A253272 First ten rows:
%e A253272 0
%e A253272 1  2
%e A253272 2  3  3
%e A253272 3  4  4  4
%e A253272 4  5  5  5  5
%e A253272 5  5  6  6  6  6
%e A253272 5  6  6  7  6  7  6
%e A253272 6  6  7  7  7  7  7  7
%e A253272 6  7  7  8  7  8  7  8  7
%e A253272 7  7  8  8  8  8  8  8  8  8
%e A253272 Row 3 counts the pairs (2,0), (1,1), (0,2), for which the paths are as shown here:
%e A253272 (2,0) -> (1,0) -> (0,0) (2 steps)
%e A253272 (1,1) -> (0,1) -> (1,0) -> (0,0) (3 steps)
%e A253272 (0,2) -> (2,0) -> (1,0) -> (0,0) (3 steps)
%t A253272 f[{x_, y_}] := If[EvenQ[x], {y, x/2}, {x - 1, y}]; f[{2, 0}] = {1, 0};
%t A253272 g[{x_, y_}] := Drop[FixedPointList[f, {x, y}], -1];
%t A253272 h[{x_, y_}] := -1 + Length[g[{x, y}]];
%t A253272 t = Table[h[{n - k, k}], {n, 0, 16}, {k, 0, n}]
%t A253272 TableForm[t]   (* A253272 array *)
%t A253272 u = Flatten[t] (* A253272 sequence *)
%Y A253272 Cf. A257569, A000032, A000931, A029744.
%K A253272 nonn,tabl,easy
%O A253272 1,3
%A A253272 _Clark Kimberling_, May 01 2015