|
Search: id:A152487
|
|
|
| A152487 |
|
Triangle read by rows, 0<=k<=n: T(n,k) = Levenshtein distance of n and k in binary representation. |
|
+0
7
|
|
| 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; listen)
|
|
|
OFFSET
|
0,7
|
|
|
COMMENT
|
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: A060450 A152146 A025860 this_sequence A058394 A113661 A113974
Adjacent sequences: A152484 A152485 A152486 this_sequence A152488 A152489 A152490
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Dec 06 2008
|
|
|
Search completed in 0.002 seconds
|
