4

Codegolf the hamming code (with distance equals 3)!

The sequence looks like this: 0, 7, 25, 30, 42, 45, 51, 52, 75, 76, 82, 85, 97, 102, 120, 127, 385, 390, 408, 415, 427, 428, 434, 437, 458, 461, 467, 468, 480, 487, 505, 510, 642, 645, 667, 668, 680...

## Task

Given `n`

output the first `n`

items in OEIS sequence A075926. Your program should work for any integer `n`

where `0 <= n < 2^15`

. This sequence is known as the sequence of hamming codewords with distance being 3.

**Rules:**

- Post both an ungolfed version of your code (or an explatation), and the golfed version, so that other people can understand how it works
- If your program is written in a language with a compiler, specify which compiler and the compiler settings you used. Non-standard language features are allowed as long as it compiles with the compiler you specified, and the compiler was created prior to this question

**Sequence Definition:**
Given a distance 3 hamming codeword `k`

, the variants of `k`

are `k`

itself, and any nonnegative integer that can be produced by flipping one of `k`

's bits. The `n`

th hamming codeword is the smallest nonnegative integer that doesn't share a variant with any preceeding distance 3 hamming codeword. Here are the first twenty d-3 hamming codewords in binary:

0, 111, 11001, 11110, 101010, 101101, 110011, 110100, 1001011, 1001100, 1010010, 1010101, 1100001, 1100110, 1111000, 1111111, 110000001, 110000110, 110011000, 110011111, 110101011

**Ungolfed C++ code to produce sequence:**

```
//Flips the nth bit
size_t flipN(size_t val, int bit) {
return val ^ (1ull << bit);
}
void Hamming(size_t n) {
int bits_to_use = 20;
//This vector keeps track of which numbers are crossed off
//As either hamming codewords or their variants.
std::vector<bool> vect(1ull << bits_to_use, false);
size_t pos = 0;
size_t val = 0;
while(val <= n) {
//Checks to see that pos hasn't been crossed off
if(vect[pos]) goto loopend;
for(int i=0; i < bits_to_use; ++i)
{
if(vect[flipN(pos, i)]) goto loopend;
//Checks to see that none of the variants
//of pos have been crossed off
}
//If both those conditions are satisfied, output pos
//As the next hamming codeword
cout << pos << endl;
//Here we cross off all the variants
vect[pos] = true;
for(int i=0; i < bits_to_use; ++i)
{
vect[flipN(pos, i)] = true;
}
++val;
loopend:
++pos;
}
}
```

Related – Stephen – 2017-08-18T17:23:49.250

5

No; they're very different sequences. The Hamming Numbers question is for https://oeis.org/A051037

– J. Antonio Perez – 2017-08-18T17:24:10.483I edited your post to clarify the task and I removed some rules that are already defaults (see meta). Rollback if you would like to. – Stephen – 2017-08-18T17:30:07.433

5Am I the only on that doesn't understand the task? :P – Mr. Xcoder – 2017-08-18T17:32:35.337

Given a number n, output the first n numbers of integer sequence A051037. It's a pretty standard problem to output an integer sequence; this particular integer sequence just requires an interesting algorithm. – J. Antonio Perez – 2017-08-18T17:34:47.830

Some Test cases would be helpful (although we have OEIS) – Mr. Xcoder – 2017-08-18T17:35:12.743

3@JorgePerez You should be able to explain this algorithm and give examples – J42161217 – 2017-08-18T17:36:33.837

4The sequence is defined neither here nor on the OEIS page. – Leaky Nun – 2017-08-18T17:43:26.443

2

"Post both an ungolfed version of your code, and the golfed version, so that other people can understand how it works"What does ungolfed Pyth or Jelly look like? I suggest you ask for an explanation instead. :) – Stewie Griffin – 2017-08-18T17:50:23.850