npm package: @luncheon/parity-step-code
Description: A Universal Coding of Integers (UCI) inspired by Collatz conjecture.
Latest version: 1.0.0

# Parity-Step Code

**Parity-Step Code** is a Universal Coding of Integers (UCI) inspired by [Collatz conjecture](https://en.wikipedia.org/wiki/Collatz_conjecture).

Encoding positive integer `n` is dead simple:

```js
function* encodeParityStep(n) {
  while (n !== 1) {
    if (n % 2 === 0) {
      n = n / 2
      yield 0
    } else {
      n = n - 1 // differs from Collatz function `n = 3 * n + 1`
      yield 1
    }
  }
  yield 1
  yield 1
}
```

- **Each codeword ends with `11`.** As with Fibonacci code, `11` does not appear anywhere else in the codeword.
- **The codeword length is not monotonically increasing.** It is shorter for $2^{n}$ and longer for $2^{n}-1$.

|         n |             Parity-Step Code | [Fibonacci Code](https://en.wikipedia.org/wiki/Fibonacci_coding) ([npm](https://www.npmjs.com/package/@luncheon/fibonacci-code)) | [Exponential-Golomb Code](https://en.wikipedia.org/wiki/Exponential-Golomb_coding) (k=0) ([npm](https://www.npmjs.com/package/@luncheon/exponential-golomb-code)) | [Varint](https://en.wikipedia.org/wiki/Variable-length_quantity) ([npm](https://www.npmjs.com/package/@luncheon/varint)) |
| ---------:| ----------------------------:| ------------------------------:| ---------------------------------------:| ------------------------:|
|         0 |                            - |                              - |                                       1 |                 00000000 |
|         1 |                           11 |                             11 |                                     010 |                 00000001 |
|         2 |                          011 |                            011 |                                     011 |                 00000010 |
|         3 |                         1011 |                           0011 |                                   00100 |                 00000011 |
|         4 |                         0011 |                           1011 |                                   00101 |                 00000100 |
|         5 |                        10011 |                          00011 |                                   00110 |                 00000101 |
|         6 |                        01011 |                          10011 |                                   00111 |                 00000110 |
|         7 |                       101011 |                          01011 |                                 0001000 |                 00000111 |
|         8 |                        00011 |                         000011 |                                 0001001 |                 00001000 |
|         9 |                       100011 |                         100011 |                                 0001010 |                 00001001 |
|        10 |                       010011 |                         010011 |                                 0001011 |                 00001010 |
|        11 |                      1010011 |                         001011 |                                 0001100 |                 00001011 |
|        12 |                       001011 |                         101011 |                                 0001101 |                 00001100 |
|        13 |                      1001011 |                        0000011 |                                 0001110 |                 00001101 |
|        14 |                      0101011 |                        1000011 |                                 0001111 |                 00001110 |
|        15 |                     10101011 |                        0100011 |                               000010000 |                 00001111 |
|        16 |                       000011 |                        0010011 |                               000010001 |                 00010000 |
|       100 |                   0010001011 |                    00101000011 |                           0000001100101 |                 01100100 |
|     1,000 |             0001001010101011 |               0000010000000011 |                     0000000001111101001 |         1110100000000111 |
|     1,023 |         10101010101010101011 |               0100000100000011 |                   000000000010000000000 |         1111111100000111 |
|     1,024 |                 000000000011 |               0010000100000011 |                   000000000010000000001 |         1000000000001000 |
|    10,000 |          0000100001010100011 |           01010001000001001011 |             000000000000010011100010001 |         1001000001001110 |
|    16,383 | 1010101010101010101010101011 |          010000010001001001011 |           00000000000000100000000000000 |         1111111101111111 |
|    16,384 |             0000000000000011 |          001000010001001001011 |           00000000000000100000000000001 | 100000001000000000000001 |
|   100,000 |      00000100100101000001011 |      1010101001001000001010011 |       000000000000000011000011010100001 | 101000001000110100000110 |
| 1,000,000 |  000000100010000010010101011 | 000000001010000000000010100011 | 000000000000000000011110100001001000001 | 110000001000010000111101 |

## Usage

```bash
$ npm i @luncheon/parity-step-code
```

### API

```js
import { encodeParityStep, decodeParityStep } from "@luncheon/parity-step-code";

encodeParityStep(3)
// => Generator<0 | 1>

encodeParityStep(3).toArray()
// => [1, 0, 1, 1]

encodeParityStep(3).reduce((x, y) => x + y, "")
// => "1011"
// can't wait https://github.com/tc39/proposal-iterator-join

decodeParityStep([1, 0, 1, 1])
// => 3

decodeParityStep(encodeParityStep(3))
// => 3
```

### CLI

```bash
$ npx @luncheon/parity-step-code 3 4 5 10-20 0x80
   3 1011
   4 0011
   5 10011
  10 010011
  11 1010011
  12 001011
  13 1001011
  14 0101011
  15 10101011
  16 000011
  17 1000011
  18 0100011
  19 10100011
  20 0010011
 128 000000011
```

## License

[WTFPL](http://www.wtfpl.net)