A075926 -id:A075926 - cp's OEIS frontend

A075927 Basis for code in A075926.

7, 25, 42, 75, 385, 642, 1155, 2184, 4233, 8330, 16523, 98305, 163842, 294915, 557064, 1081353, 2129930, 4227083, 8421504, 16810113, 33587330, 67141763, 134250632, 268468361, 536903818, 1073774731, 6442450945, 10737418242

Offset: 0

Bob Jenkins (bob_jenkins(AT)burtleburtle.net)

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.
Ari Trachtenberg, Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs

Cf. A075928, A075929, A075930, A075926, A057716, A075933.

a(n) = b(2^n), where b is the Hamming code d=3.

b(n) = XOR(a(i)) where i is a bit 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.

A075931 List of codewords in binary lexicode with Hamming distance 5 written as decimal numbers.

Original entry on oeis.org

0, 31, 227, 252, 805, 826, 966, 985, 1354, 1365, 1449, 1462, 1647, 1648, 1676, 1683, 6182, 6201, 6341, 6362, 6915, 6940, 7136, 7167, 7532, 7539, 7567, 7568, 7753, 7766, 7850, 7861, 10315, 10324, 10408, 10423, 11118, 11121, 11149, 11154

Offset: 0

Bob Jenkins (bob_jenkins(AT)burtleburtle.net)

Rémy Sigrist, Table of n, a(n) for n = 0..8191
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, A075932, A075933, A075924, A075926, A075937.

a=vector(40); n=0; for (k=0, 11154, if (n==0 || vecmin(apply(o -> hammingweight(bitxor(k, o)), a[1..n]))>=5, print1 (a[n++]=k", "))) \\ Rémy Sigrist, Feb 09 2021

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

Original entry on oeis.org

0, 111, 222, 333, 444, 555, 666, 777, 888, 999, 1012, 1103, 1230, 1321, 1456, 1547, 1674, 1765, 2023, 2132, 2201, 2310, 2467, 2576, 2645, 2754, 3031, 3120, 3213, 3302, 3475, 3564, 3657, 3746, 4048, 4159, 4284, 4395, 4806, 4917, 5069, 5178, 5296, 5387, 5814

Offset: 0

Rémy Sigrist, Jun 09 2020

This is the distance 3 lexicode over the decimal alphabet. - N. J. A. Sloane, Jul 20 2021

Rémy Sigrist, Table of n, a(n) for n = 0..9999
J. H. Conway, Integral lexicographic codes, Discrete Mathematics 83.2-3 (1990): 219-235. See paragraph 3.
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émy Sigrist, C program for A333568

Cf. A075926 (binary equivalent)

C
```
See Links section.
```

A261283 a(n) = bitwise XOR of all the bit numbers for the bits that are set in n, using number 1 for the LSB.

Original entry on oeis.org

0, 1, 2, 3, 3, 2, 1, 0, 4, 5, 6, 7, 7, 6, 5, 4, 5, 4, 7, 6, 6, 7, 4, 5, 1, 0, 3, 2, 2, 3, 0, 1, 6, 7, 4, 5, 5, 4, 7, 6, 2, 3, 0, 1, 1, 0, 3, 2, 3, 2, 1, 0, 0, 1, 2, 3, 7, 6, 5, 4, 4, 5, 6, 7, 7, 6, 5, 4, 4, 5, 6, 7, 3, 2, 1, 0, 0, 1, 2, 3, 2, 3, 0, 1, 1, 0

Offset: 0

M. F. Hasler, Aug 14 2015, following the original version A253315 by Philippe Beaudoin, Dec 30 2014

If the least significant bit is numbered 0, then a(2n) = a(2n+1) if one uses the "natural" definition reading "...set in n": see A253315 for that version. To avoid the duplication, we chose here to start numbering the bits with 1 for the LSB; equivalently, we can start numbering the bits with 0 but use the definition "...bits set in 2n". In any case, a(n) = A253315(2n) = A253315(2n+1).

Since the XOR operation is associative, one can define XOR of an arbitrary number of terms in a recursive way, there is no ambiguity about the order in which the operations are performed.

			a(7) = a(4+2+1) = a(2^2+2^1+2^0) = (2+1) XOR (1+1) XOR (0+1) = 3 XOR 3 = 0.
a(12) = a(8+4) = a(2^3+2^2) = (3+1) XOR (2+1) = 4+3 = 7.

Philippe Beaudoin, Table of n, a(n) for n = 0..8190
Oliver Nash, Yet another prisoner puzzle, coins on a chessboard problem.
Tilman Piesk, Illustration of the first 128 terms

Cf. A075926 (indices of 0's), A253315, A327041 (OR equivalent).

A261283[n_] := If[n == 0, 0, BitXor @@ PositionIndex[Reverse[IntegerDigits[n, 2]]][1]]; Array[A261283, 100, 0] (* Paolo Xausa, May 29 2024 *)

A261283(n,b=bittest(n,0))={for(i=1,#binary(n),bittest(n,i)&&b=bitxor(b,i+1));b}

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

A075927 Basis for code in A075926.

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

A075931 List of codewords in binary lexicode with Hamming distance 5 written as decimal numbers.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

A261283 a(n) = bitwise XOR of all the bit numbers for the bits that are set in n, using number 1 for the LSB.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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