A115778 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.

1, 0, 2, 4, 8, 22, 32, 64, 222, 256, 512, 2044, 2222, 4222, 8192, 22222, 32768, 65536, 222222, 262144, 524288, 2097152, 2222222, 4194322, 8388622, 22222222, 33554432, 67222222, 222222222, 268435456, 536872222, 2147483650, 2147483648, 4294967296, 8589934592, 22222222222

Offset

0,3

Comments

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

Links

Table of n, a(n) for n=0..35.

Formula

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

Maple

f:= n -> StringTools:-Levenshtein(convert(n, string), convert(convert(n, binary), string)):
A:= Vector(20):
for n from 3 to 10^6 do
  v:= f(n);
  if A[v] = 0 then A[v]:= n fi
od:
1, 0, seq(A[n], n=2..20); # Robert Israel, Jul 16 2015

Mathematica

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 = 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

Crossrefs

Cf. A000027, A007088, A115777.

Sequence in context: A133604 A262345 A192149 * A333016 A295628 A027713

Adjacent sequences: A115775 A115776 A115777 * A115779 A115780 A115781

Keyword

nonn,base

Author

Robert G. Wilson v, Jan 26 2006

Extensions

a(26)-a(35) from Lars Blomberg, Jul 16 2015

Status

approved