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

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, 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, 4, 1, 3, 2, 2, 3, 1, 4, 2, 3, 3, 4, 4, 3, 3, 5, 0, 5

Offset: 1

Author

Clark Kimberling, Jun 08 2013

Keywords

• nonn
• tabl
• base
• easy

Comments

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)).

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).

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,...

D(n,1)+1 is the number of digits in (n base 2); D(n,n+1) = A101688(n) for n>=1.

Examples

			Northwest corner of the distance table:
0 1 1 2 2 2 2 3 3 3
1 0 2 1 1 3 3 2 2 2
1 2 0 3 3 1 1 4 4 4
2 1 3 0 2 4 4 1 1 3
2 1 3 2 0 4 4 3 3 1
2 3 1 4 4 0 2 5 5 5
2 3 1 4 4 2 0 5 5 5
3 2 4 1 3 5 5 0 2 4
3 2 4 1 3 5 5 2 0 4
3 2 4 3 1 5 5 4 4 0
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.
		

Links

• Clark Kimberling, Antidiagonals n=1..60, flattened

Crossrefs

Cf. A226080, A226207, A226247, A101688.

Programs

Mathematica

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 *)
Flatten[Table[d[k, n + 1 - k], {n, 1, z}, {k, 1, n}]] (* A226456 sequence *)
Table[d[n, n + 1], {n, 1, 100}] (* A101688 *)
Table[d[n, 2^n], {n, 1, 100}]   (* A226457 *)