A322285 Triangle read by rows: T(n,k) is the Damerau-Levenshtein distance between n and k in binary representation, 0 <= k <= n.

0, 1, 0, 1, 1, 0, 2, 1, 1, 0, 2, 2, 1, 2, 0, 2, 2, 1, 1, 1, 0, 2, 2, 1, 1, 1, 1, 0, 3, 2, 2, 1, 2, 1, 1, 0, 3, 3, 2, 3, 1, 2, 2, 3, 0, 3, 3, 2, 2, 1, 1, 2, 2, 1, 0, 3, 3, 2, 2, 1, 1, 1, 2, 1, 1, 0, 3, 3, 2, 2, 2, 1, 2, 1, 2, 1, 1, 0, 3, 3, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 0, 3, 3, 2, 2, 2, 1, 1, 1, 2, 1, 2, 1, 1, 0

Offset: 0

Author

Pontus von Brömssen, Dec 02 2018

Keywords

• nonn
• base
• tabl

Comments

The Damerau-Levenshtein distance between two sequences is the number of edit operations (deletions, insertions, substitutions, and adjacent transpositions) needed to transform one into the other.

For consistency with A152487, the binary representation of 0 is assumed to be "0". If instead 0 is represented as the empty sequence, T(n,0) should be increased by 1 for all n except those of the form 2^m-1 for m >= 0.

T(n,k) <= A152487(n,k).

Examples

			The triangle T(n, k) begins:
  n\k  0  1  2  3  4  5  6  7  8  9 10 11 12 13 ...
   0:  0
   1:  1  0
   2:  1  1  0
   3:  2  1  1  0
   4:  2  2  1  2  0
   5:  2  2  1  1  1  0
   6:  2  2  1  1  1  1  0
   7:  3  2  2  1  2  1  1  0
   8:  3  3  2  3  1  2  2  3  0
   9:  3  3  2  2  1  1  2  2  1  0
  10:  3  3  2  2  1  1  1  2  1  1  0
  11:  3  3  2  2  2  1  2  1  2  1  1  0
  12:  3  3  2  2  1  2  1  2  1  2  1  2  0
  13:  3  3  2  2  2  1  1  1  2  1  2  1  1  0
  ...
The distance between the binary representations of 46 and 25 is 3 (via the edits "101110" - "10111" - "11011" - "11001"), so T(46,25) = 3.
		

Links

• Pontus von Brömssen, Rows n = 0..200, flattened
• Wikipedia, Damerau-Levenshtein distance
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A152487.