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

%I #22 Oct 09 2019 13:35:42

%S 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,

%T 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,

%U 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

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

%C 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.

%C 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.

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

%H Pontus von Brömssen, <a href="/A322285/b322285.txt">Rows n = 0..200, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance">Damerau-Levenshtein distance</a>

%H <a href="http://oeis.org/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%e The triangle T(n, k) begins:

%e n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...

%e 0: 0

%e 1: 1 0

%e 2: 1 1 0

%e 3: 2 1 1 0

%e 4: 2 2 1 2 0

%e 5: 2 2 1 1 1 0

%e 6: 2 2 1 1 1 1 0

%e 7: 3 2 2 1 2 1 1 0

%e 8: 3 3 2 3 1 2 2 3 0

%e 9: 3 3 2 2 1 1 2 2 1 0

%e 10: 3 3 2 2 1 1 1 2 1 1 0

%e 11: 3 3 2 2 2 1 2 1 2 1 1 0

%e 12: 3 3 2 2 1 2 1 2 1 2 1 2 0

%e 13: 3 3 2 2 2 1 1 1 2 1 2 1 1 0

%e ...

%e The distance between the binary representations of 46 and 25 is 3 (via the edits "101110" - "10111" - "11011" - "11001"), so T(46,25) = 3.

%Y Cf. A152487.

%K nonn,base,tabl

%O 0,7

%A _Pontus von Brömssen_, Dec 02 2018