A075934 -id:A075934 - cp's OEIS frontend

A075936 Positions of check bits in code in A075934.

31, 103, 171, 213, 301, 342, 439, 475, 494, 558, 595, 911, 1075, 1114, 1189, 1287, 1606, 1727, 1996, 2102, 2140, 2225, 2339, 2667, 2691, 3240, 3733, 4153, 4171, 4371, 4745, 4912, 5237, 5601, 5746, 6254, 6569, 6967, 7115, 7527, 8250, 8270

Offset: 0

Bob Jenkins (bob_jenkins(AT)burtleburtle.net)

nonn

J. H. Conway and N. J. A. Sloane, Lexicographic codes: error-correcting codes from game theory, IEEE Transactions on Information Theory, 32:337-348, 1986.

Bob Jenkins, Tables of Binary Lexicodes
Ari Trachtenberg, Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs

Cf. A075928, A075929, A075930, A075934, A075935, A075933, A075942.

A075935 Basis for code in A075934.

Original entry on oeis.org

63, 455, 1611, 2709, 12365, 20630, 37463, 70299, 135886, 786510, 1310867, 2363919, 12582995, 20971674, 37749317, 71307271, 138674310, 272892511, 541332108, 3221225558, 5368709276, 9663677009, 18253615171, 35433742539

Offset: 0

Bob Jenkins (bob_jenkins(AT)burtleburtle.net)

nonn

J. H. Conway and N. J. A. Sloane, Lexicographic codes: error-correcting codes from game theory, IEEE Transactions on Information Theory, 32:337-348, 1986.

Bob Jenkins, Tables of Binary Lexicodes
Ari Trachtenberg, Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs

Cf. A075928, A075929, A075930, A075934, A075936, A075932, A075941.

a(n) = b(2^n), where b is A075934, the binary lexicode, d=6.

b(n) = XOR(a(i)) for all i where the i-th bit is set in n.

A075928 List of codewords in binary lexicode with Hamming distance 4 written as decimal numbers.

Original entry on oeis.org

0, 15, 51, 60, 85, 90, 102, 105, 150, 153, 165, 170, 195, 204, 240, 255, 771, 780, 816, 831, 854, 857, 869, 874, 917, 922, 934, 937, 960, 975, 1011, 1020, 1285, 1290, 1334, 1337, 1360, 1375, 1379, 1388, 1427, 1436, 1440, 1455, 1478, 1481, 1525

Offset: 0

Bob Jenkins (bob_jenkins(AT)burtleburtle.net)

The lexicode of Hamming distance d is constructed greedily by stepping through the binary vectors in lexicographic order and accepting a vector if it is at Hamming distance at least d from all already-chosen vectors.
The code is linear and infinite.
This is also the (infinite) d=4 Hamming code.
Lexicodes with even Hamming distance can be constructed from the preceding lexicode of odd Hamming distance by prepending a single parity bit.

J. H. Conway and N. J. A. Sloane, Lexicographic codes: error-correcting codes from game theory, IEEE Transactions on Information Theory, 32:337-348, 1986.
R. W. Hamming, Error Detecting and Error Correcting Codes, Bell System Tech. J., Vol. 29, April, 1950, pp. 147-160.
Bob Jenkins, Tables of Binary Lexicodes
Ari Trachtenberg, Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs

Cf. A075929, A075930, A075926, A075934, A075944, A075945, A075946, A075937, A075949, etc.

A194851 is a subsequence.

A075940 List of codewords in binary lexicode with Hamming distance 8 written as decimal numbers.

Original entry on oeis.org

0, 255, 3855, 4080, 13107, 13260, 15420, 15555, 21845, 21930, 23130, 23205, 26214, 26265, 26985, 27030, 38505, 38550, 39270, 39321, 42330, 42405, 43605, 43690, 49980, 50115, 52275, 52428, 61455, 61680, 65280, 65535, 197462, 197545

Offset: 0

Bob Jenkins (bob_jenkins(AT)burtleburtle.net)

nonn

J. H. Conway and N. J. A. Sloane, Lexicographic codes: error-correcting codes from game theory, IEEE Transactions on Information Theory, 32:337-348, 1986.
Bob Jenkins, Tables of Binary Lexicodes
Ari Trachtenberg, Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs

Cf. A075928, A075929, A075930, A075941, A075942, A075937, A075934, A075946.

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

Original entry on oeis.org

0, 1111, 2222, 3333, 4444, 5555, 6666, 7777, 8888, 9999, 10123, 11032, 12301, 13210, 14567, 15476, 16745, 17654, 20231, 21320, 22013, 23102, 24675, 25764, 26457, 27546, 30312, 31203, 32130, 33021, 34756, 35647, 36574, 37465

Offset: 1

N. J. A. Sloane, Jul 20 2021

This is the distance 4 lexicode over the decimal alphabet.

J. H. Conway, Integral lexicographic codes, Discrete Mathematics 83.2-3 (1990): 219-235.
J. H. Conway and N. J. A. Sloane, Lexicographic codes: error-correcting codes from game theory, IEEE Transactions on Information Theory, 32:337-348, 1986.

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.

# Hamming distance in base b
Hammdist:=proc(m,n,b) local t1,t2,L1,L2,L,d,i;
t1:=convert(m,base,b); L1:=nops(t1);
t2:=convert(n,base,b); L2:=nops(t2); L:=L1;
if L2t2[i] then d:=d+1; fi; od;
d; end;
# Build lexicode with min distance D in base b, search up to M
# C = size of code found, tooc = 1 means too close to code
unprotect(D);
lexicode := proc(D,b,M) local cod,v,i,tooc,C;
cod:=[0]; C:=1;
# can we add v ?
for v from 0 to M do
   tooc:=-1;
   for i from 1 to C do
   if Hammdist(v,cod[i],b)

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

Original entry on oeis.org

0, 11111, 22222, 33333, 44444, 55555, 66666, 77777, 88888, 99999, 101234, 110325, 123016, 132107, 145670, 154761, 167452, 176543, 202318, 213209, 220153, 231042, 246735, 257624, 264580, 275491

Offset: 1

N. J. A. Sloane, Jul 20 2021

This is the distance 5 lexicode over the decimal alphabet.

J. H. Conway, Integral lexicographic codes, Discrete Mathematics 83.2-3 (1990): 219-235.
J. H. Conway and N. J. A. Sloane, Lexicographic codes: error-correcting codes from game theory, IEEE Transactions on Information Theory, 32:337-348, 1986.

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.

Maple
```
(See A346000)
```

A346002 Distance 2 lexicode over the alphabet {0,1,2}, with the codewords written in base 10.

Original entry on oeis.org

0, 4, 8, 10, 12, 20, 24, 28, 30, 36, 40, 44, 50, 52, 56, 60, 68, 70, 72, 76, 80, 82, 84, 90, 94, 98, 104, 106, 108, 112, 116, 118, 120, 128, 132, 140, 142, 146, 150, 154, 156, 164, 168, 176, 178, 180, 184, 188, 194, 196, 200, 204, 208, 210, 216, 220, 224, 226, 228, 236, 240

Offset: 1

N. J. A. Sloane, Jul 20 2021

Lexicographically earliest sequence of ternary words such that any two distinct words differ in at least 2 positions.

J. H. Conway, Integral lexicographic codes, Discrete Mathematics 83.2-3 (1990): 219-235.
J. H. Conway and N. J. A. Sloane, Lexicographic codes: error-correcting codes from game theory, IEEE Transactions on Information Theory, 32:337-348, 1986.

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.

Maple
```
(See A346000).
```

A346003 Distance 3 lexicode over the alphabet {0,1,2}, with the codewords written in base 10.

Original entry on oeis.org

0, 13, 26, 32, 42, 46, 61, 65, 75, 325, 336, 357, 362, 373, 383, 394, 396, 413, 584, 651, 658, 677, 699, 716, 812, 825, 832, 840, 847, 863, 878, 898, 909, 975, 982, 1001, 1023, 1043, 1048, 1148, 1165, 1170, 1194, 1208, 1223, 1254, 1269, 1330, 1341, 1421, 1452

Offset: 1

N. J. A. Sloane, Jul 20 2021

Lexicographically earliest sequence of ternary words such that any two distinct words differ in at least 3 positions.

Andrey Zabolotskiy, Table of n, a(n) for n = 1..6000
J. H. Conway, Integral lexicographic codes, Discrete Mathematics 83.2-3 (1990): 219-235.
J. H. Conway and N. J. A. Sloane, Lexicographic codes: error-correcting codes from game theory, IEEE Transactions on Information Theory, 32:337-348, 1986.

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.

Maple
```
(See A346000).
```

def t(n):
    d = []
    while n:
        d.append(n%3)
        n //= 3
    return d
def dif(n1, n2):
    return sum(d1 != d2 for d1, d2 in zip(n1 + [0] * (len(n2)-len(n1)), n2))
a = [0]
for n in range(2000):
    if all(dif(t(n1), t(n)) >= 3 for n1 in a):
        a.append(n)
print(a) # Andrey Zabolotskiy, Sep 30 2021

Terms a(36) and beyond from Andrey Zabolotskiy, Sep 30 2021

A346261 Lexicographically earliest sequence of decimal words starting with 10 such that each term has Hamming distance at least 2 from all earlier terms.

Original entry on oeis.org

10, 21, 32, 43, 54, 65, 76, 87, 98, 100, 111, 122, 133, 144, 155, 166, 177, 188, 199, 201, 212, 220, 234, 245, 253, 267, 278, 286, 302, 313, 324, 330, 341, 356, 368, 375, 389, 397, 403, 414, 425, 431, 440, 452, 469, 496, 504, 515, 523, 536, 542, 550, 561, 579, 605, 616, 627, 638, 649, 651

Offset: 1

Peter Woodward, Jul 11 2021

			a(1) = 10 by definition.
a(2) = 21 because '2' has not yet appeared in the tens place and '1' has not yet appeared in the ones place.

Michael S. Branicky, Table of n, a(n) for n = 1..10000
J. H. Conway and N. J. A. Sloane, Lexicographic codes: error-correcting codes from game theory, IEEE Transactions on Information Theory, 32:337-348, 1986.

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.

Cf. A207063.

def ham(m, n):
    s, t = str(min(m, n))[::-1], str(max(m, n))[::-1]
    return len(t) - len(s) + sum(s[i] != t[i] for i in range(len(s)))
def aupton(terms):
    alst = [10]
    for n in range(2, terms+1):
        an = alst[-1] + 1
        while any(ham(an, aprev) < 2 for aprev in alst[::-1]):  an += 1
        alst.append(an)
    return alst
print(aupton(60)) # Michael S. Branicky, Jul 22 2021

Edited and corrected by N. J. A. Sloane, Jul 20 2021

cp's OEIS Frontend

A075936 Positions of check bits in code in A075934.

Views

Author

Keywords

References

Links

Crossrefs

A075935 Basis for code in A075934.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A075928 List of codewords in binary lexicode with Hamming distance 4 written as decimal numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

A075940 List of codewords in binary lexicode with Hamming distance 8 written as decimal numbers.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A346002 Distance 2 lexicode over the alphabet {0,1,2}, with the codewords written in base 10.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A346003 Distance 3 lexicode over the alphabet {0,1,2}, with the codewords written in base 10.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Python

Extensions

A346261 Lexicographically earliest sequence of decimal words starting with 10 such that each term has Hamming distance at least 2 from all earlier terms.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Extensions