OFFSET
1,7
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.
LINKS
Clark Kimberling, Antidiagonals n=1..60, flattened
EXAMPLE
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.
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 *)
CROSSREFS
KEYWORD
AUTHOR
Clark Kimberling, Jun 08 2013
STATUS
approved