|
|
A152487
|
|
Triangle read by rows, 0<=k<=n: T(n,k) = Levenshtein distance of n and k in binary representation.
|
|
10
|
|
|
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, 2, 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, 2, 0, 3, 3, 2, 2, 2, 1, 2, 1, 2, 1, 1, 0, 3, 3, 2, 2, 1, 2, 1, 2, 1, 2, 2, 3, 0, 3, 3, 2, 2, 2, 1, 1, 1, 2, 1, 2, 2, 1, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,7
|
|
COMMENTS
|
T(n,k) gives number of editing steps (replace, delete and insert) to transform n to k in binary representations;
T(n,k) <= Hamming-distance(n,k) for n and k with A070939(n)=A070939(k);
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = f(n,k) with f(x,y) = if x>y then f(y,x) else if x<=1 then Log2(y)-0^y+(1-x)*0^(y+1-2^(y+1)) else Min{f([x/2],[y/2]) + (x mod 2) XOR (y mod 2), f([x/2],y)+1, f(x,[y/2])+1}, where Log2=A000523.
|
|
EXAMPLE
|
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 2 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 2 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 2 3 0
13: 3 3 2 2 2 1 1 1 2 1 2 2 1 0
...
The distance between the binary representations of 46 and 25 is 4 (via the edits "101110" - "10111" - "10011" - "11011" - "11001"), so T(46,25) = 4. - Pontus von Brömssen, Dec 02 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|