cp's OEIS Frontend

A226456 Array by antidiagonals: D(m,n) = binary distance between m and n.

%I A226456 #5 Jun 10 2013 04:35:06
%S A226456 0,1,1,1,0,1,2,2,2,2,2,1,0,1,2,2,1,3,3,1,2,2,3,3,0,3,3,2,3,3,1,2,2,1,
%T A226456 3,3,3,2,1,4,0,4,1,2,3,3,2,4,4,4,4,4,4,2,3,3,2,4,1,4,0,4,1,4,2,3,3,2,
%U A226456 4,1,3,2,2,3,1,4,2,3,3,4,4,3,3,5,0,5
%N A226456 Array by antidiagonals:  D(m,n) = binary distance between m and n.
%C A226456 Method 1.  In base 2, write m = m(0) + m(1)*2 + ... + m(i)*2^i and n = n(0) + n(1)*2 + ... + n(j)*2^j.  Let c be the greatest h such that m(h) = n(h) for h = 0,...,c, and let r(m,n) = m(0) + m(1)*2 + ... + m(c)*2^c.  For every positive integer k, let g(k) be the number of binary digits of k.  Then D(m,n) = g(m) + g(n) - 2*g(r(m,n)).
%C A226456 Method 2.  Let S be the set determined by these rules:  1 is in S, and if x is in S, then x+1 and 1/(x+1) are in S.  As in A226080, grow the tree from the root 1, and then replace each number by the order in which it was generated.  In the resulting tree, D(m,n) is the number of edges from m to n; i.e., D is the graph metric of the tree.  The tree is also determined by the condition that if m < n, then m and n are connected by an edge if and only if m = floor(n/2).
%C A226456 The set S consists of all the positive rationals, of which the first 15 are indicated in generations by (1), (2, 1/2), (3 ,1/3, 3/2, 2/3), (4, 1/4, 4/3, 3/4, 5/2, 2/5, 5/3, 3/5).  One outermost branch of the tree consists of 1,2,3,4,... and the other involves Fibonacci numbers: 1, 1/2, 2/3, 3/5,...
%C A226456 D(n,1)+1 is the number of digits in (n base 2); D(n,n+1) = A101688(n) for n>=1.
%H A226456 Clark Kimberling, <a href="/A226456/b226456.txt">Antidiagonals n=1..60, flattened</a>
%e A226456 Northwest corner of the distance table:
%e A226456 0 1 1 2 2 2 2 3 3 3
%e A226456 1 0 2 1 1 3 3 2 2 2
%e A226456 1 2 0 3 3 1 1 4 4 4
%e A226456 2 1 3 0 2 4 4 1 1 3
%e A226456 2 1 3 2 0 4 4 3 3 1
%e A226456 2 3 1 4 4 0 2 5 5 5
%e A226456 2 3 1 4 4 2 0 5 5 5
%e A226456 3 2 4 1 3 5 5 0 2 4
%e A226456 3 2 4 1 3 5 5 2 0 4
%e A226456 3 2 4 3 1 5 5 4 4 0
%e A226456 Row 9, column 6 is occupied by 5, meaning that D(9,6) = 5, a count of edges in the subgraph 9 -> 4 -> 2 -> 1 -> 3 ->6.
%t A226456 r = 1/2; f[x_] := Floor[r*x]; z = 20; g[x_] := FixedPointList[f, x]; u[x_] := Length[g[x]];  v[x_, y_] := Max[Intersection[g[x], g[y]]]; d[x_, y_] := u[x] + u[y] - 2*Length[g[v[x, y]]]; TableForm[Table[d[m, n], {m, 1, z}, {n, 1, z}]] (* A226456 array *)
%t A226456 Flatten[Table[d[k, n + 1 - k], {n, 1, z}, {k, 1, n}]] (* A226456 sequence *)
%t A226456 Table[d[n, n + 1], {n, 1, 100}] (* A101688 *)
%t A226456 Table[d[n, 2^n], {n, 1, 100}]   (* A226457 *)
%Y A226456 Cf. A226080, A226207, A226247, A101688.
%K A226456 nonn,tabl,base,easy
%O A226456 1,7
%A A226456 _Clark Kimberling_, Jun 08 2013