login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Lexicographically earliest sequence of nonnegative integers such that two distinct terms differ by at least 4 decimal digits.
5

%I #19 Jul 20 2021 15:35:15

%S 0,1111,2222,3333,4444,5555,6666,7777,8888,9999,10123,11032,12301,

%T 13210,14567,15476,16745,17654,20231,21320,22013,23102,24675,25764,

%U 26457,27546,30312,31203,32130,33021,34756,35647,36574,37465

%N Lexicographically earliest sequence of nonnegative integers such that two distinct terms differ by at least 4 decimal digits.

%C This is the distance 4 lexicode over the decimal alphabet.

%H J. H. Conway, <a href="https://doi.org/10.1016/0012-365X(90)90008-6">Integral lexicographic codes</a>, Discrete Mathematics 83.2-3 (1990): 219-235.

%H J. H. Conway and N. J. A. Sloane, <a href="https://doi.org/10.1109/TIT.1986.1057187">Lexicographic codes: error-correcting codes from game theory</a>, IEEE Transactions on Information Theory, 32:337-348, 1986.

%p # Hamming distance in base b

%p Hammdist:=proc(m,n,b) local t1,t2,L1,L2,L,d,i;

%p t1:=convert(m,base,b); L1:=nops(t1);

%p t2:=convert(n,base,b); L2:=nops(t2); L:=L1;

%p if L2<L1 then for i from 1 to L1-L2 do t2:=[op(t2),0]; od;

%p elif L1<L2 then for i from 1 to L2-L1 do t1:=[op(t1),0]; od; L:=L2;

%p fi;

%p d:=0;

%p for i from 1 to L do if t1[i]<>t2[i] then d:=d+1; fi; od;

%p d; end;

%p # Build lexicode with min distance D in base b, search up to M

%p # C = size of code found, tooc = 1 means too close to code

%p unprotect(D);

%p lexicode := proc(D,b,M) local cod,v,i,tooc,C;

%p cod:=[0]; C:=1;

%p # can we add v ?

%p for v from 0 to M do

%p tooc:=-1;

%p for i from 1 to C do

%p if Hammdist(v,cod[i],b)<D then tooc:=1; break; fi;

%p od:

%p if tooc = -1 then C:=C+1; cod:=[op(cod),v]; fi;

%p od:

%p cod;

%p end;

%Y Lexicodes of minimal distance 1,2,3,... over alphabets of size 2: A001477, A001969, A075926, A075928, A075931, A075934, ...; size 3: A001477, A346002, A346003; size 10: A001477, A343444, A333568, A346000, A346001.

%K nonn,base

%O 1,2

%A _N. J. A. Sloane_, Jul 20 2021