cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A152487 Triangle read by rows, 0<=k<=n: T(n,k) = Levenshtein distance of n and k in binary representation.

This page as a plain text file.
%I A152487 #17 Dec 26 2018 16:57:01
%S A152487 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,
%T A152487 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,
%U A152487 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
%N A152487 Triangle read by rows, 0<=k<=n: T(n,k) = Levenshtein distance of n and k in binary representation.
%C A152487 T(n,k) gives number of editing steps (replace, delete and insert) to transform n to k in binary representations;
%C A152487 row sums give A152488; central terms give A057427;
%C A152487 T(n,k) <= Hamming-distance(n,k) for n and k with A070939(n)=A070939(k);
%C A152487 T(n,0) = A000523(n+1);
%C A152487 T(n,1) = A000523(n) for n>0;
%C A152487 T(n,3) = A106348(n-2) for n>2;
%C A152487 T(n,n-1) = A091090(n-1) for n>0;
%C A152487 T(n,n) = A000004(n);
%C A152487 T(A000290(n),n) = A091092(n).
%C A152487 T(n,k) >= A322285(n,k) - _Pontus von Brömssen_, Dec 02 2018
%H A152487 Alois P. Heinz, <a href="/A152487/b152487.txt">Rows n = 0..200, flattened</a>
%H A152487 Michael Gilleland, <a href="http://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Fall2006/Assignments/editdistance/Levenshtein%20Distance.htm">Levenshtein Distance</a>
%H A152487 Wikipedia, <a href="https://en.wikipedia.org/wiki/Levenshtein_distance">Levenshtein Distance</a>
%H A152487 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A152487 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.
%e A152487 The triangle T(n, k) begins:
%e A152487   n\k  0  1  2  3  4  5  6  7  8  9 10 11 12 13 ...
%e A152487    0:  0
%e A152487    1:  1  0
%e A152487    2:  1  1  0
%e A152487    3:  2  1  1  0
%e A152487    4:  2  2  1  2  0
%e A152487    5:  2  2  1  1  1  0
%e A152487    6:  2  2  1  1  1  2  0
%e A152487    7:  3  2  2  1  2  1  1  0
%e A152487    8:  3  3  2  3  1  2  2  3  0
%e A152487    9:  3  3  2  2  1  1  2  2  1  0
%e A152487   10:  3  3  2  2  1  1  1  2  1  2  0
%e A152487   11:  3  3  2  2  2  1  2  1  2  1  1  0
%e A152487   12:  3  3  2  2  1  2  1  2  1  2  2  3  0
%e A152487   13:  3  3  2  2  2  1  1  1  2  1  2  2  1  0
%e A152487   ...
%e A152487 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
%Y A152487 Cf. A000004, A000290, A000523, A057427, A070939, A091090, A091092, A106348, A152488, A322285.
%K A152487 nonn,base,tabl
%O A152487 0,7
%A A152487 _Reinhard Zumkeller_, Dec 06 2008