|
| |
|
|
A152487
|
|
Triangle read by rows, 0<=k<=n: T(n,k) = Levenshtein distance of n and k in binary representation.
|
|
6
| |
|
|
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; 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;
row sums give A152488; central terms give A057427;
T(n,k) <= Hamming-distance(n,k) for n and k with A070939(n)=A070939(k);
T(n,0) = A000523(n+1);
T(n,1) = A000523(n) for n>0;
T(n,3) = A106348(n-2) for n>2;
T(n,n-1) = A091090(n-1) for n>0;
T(n,n) = A000004(n);
T(A000290(n),n) = A091092(n).
|
|
|
LINKS
| Wikipedia, Levenshtein Distance
Michael Gilleland, Levenshtein Distance
Index entries for sequences related to binary expansion of n
|
|
|
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.
|
|
|
CROSSREFS
| Sequence in context: A180918 A152146 A025860 * A058394 A113661 A113974
Adjacent sequences: A152484 A152485 A152486 * A152488 A152489 A152490
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Dec 06 2008
|
| |
|
|
