A115778 - OEIS

%I #14 Jul 16 2015 05:11:32

%S 1,0,2,4,8,22,32,64,222,256,512,2044,2222,4222,8192,22222,32768,65536,

%T 222222,262144,524288,2097152,2222222,4194322,8388622,22222222,

%U 33554432,67222222,222222222,268435456,536872222,2147483650,2147483648,4294967296,8589934592,22222222222

%N Consider the Levenshtein distance between k considered as a decimal string and k considered as a binary string. Then a(n) is the least number m such that the Levenshtein distance is n or 0 if no such number exists.

%C Difference between A115779 and A115778: 1, 0, 9, 11, 103, 99, 979, 1047, 1789, 10855, 15599, 109067, 128789, 1006889, 1102919, 1988889, 11078343, ...,.

%F a(1)=0 since no number satisfies the definition and generally a(n)>= 2^(n+1).

%p f:= n -> StringTools:-Levenshtein(convert(n,string), convert(convert(n,binary),string)):

%p A:= Vector(20):

%p for n from 3 to 10^6 do

%p   v:= f(n);

%p   if A[v] = 0 then A[v]:= n fi

%p od:

%p 1,0,seq(A[n],n=2..20); # _Robert Israel_, Jul 16 2015

%t levenshtein[s_List, t_List] := Module[{d, n = Length@s, m = Length@t}, Which[s === t, 0, n == 0, m, m == 0, n, s != t, d = Table[0, {m + 1}, {n + 1}]; d[[1, Range[n + 1]]] = Range[0, n]; d[[Range[m + 1], 1]] = Range[0, m]; Do[d[[j + 1, i + 1]] = Min[d[[j, i + 1]] + 1, d[[j + 1, i]] + 1, d[[j, i]] + If[s[[i]] === t[[j]], 0, 1]], {j, m}, {i, n}]; d[[ -1, -1]]]];

%t t = Table[0, {25}]; f[n_] := levenshtein[ IntegerDigits[n], IntegerDigits[n, 2]]; Do[a = f[n]; If[ t[[a+1]] == 0, t[[a+1]] = n; Print[{a, n}]], {n, 10^6}]; t

%Y Cf. A000027, A007088, A115777.

%K nonn,base

%O 0,3

%A _Robert G. Wilson v_, Jan 26 2006

%E a(26)-a(35) from _Lars Blomberg_, Jul 16 2015