# More bits the merrier

The computer department at Puzzled State University devised an inefficient bit-based (zeros and ones) number system, n', for their ever more bit-happy machines.

Here are n' = n for 0 ≤ n ≤ 42, skipping to X' = X where 100000000' = X+1, to be solved for X' and X.

    n' = n             n' = n               n' = n                n' = n

0'   0         10000'   12  b5     100000'   24  b6     1000000'   36  b7
1'   1  b1     10001'   13         100001'   25         1000001'   37
10'   2  b2     10010'   14         100010'   26         1000010'   38
11'   3         10011'   15         100011'   27         1000011'   39
100'   4  b3     10100'   16         100100'   28         1000100'   40
101'   5         10101'   17         100101'   29         1000101'   41
1000'   6  b4     11000'   18         101000'   30        10000000'   42  b8
1001'   7         11001'   19         101001'   31                  .
1010'   8         11010'   20         101010'   32                  .
1011'   9         11011'   21         101011'   33                  .
1100'   10        11100'   22         101100'   34               X'   X
1101'   11        11101'   23         101101'   35       100000000'   X+1  b9
.
.
bit numbers  b1  b2  b3  b4  b5  b6  b7  b8  b9                    .
bit values    1   2   4   6  12  24  36  42  X+1


Each n' = n is unique. Only 1000' = 6 suits n' = 6, for example, even though one could imagine 110' = 100'+10' = 4+2 = 6 as well. Yet 110' does not exist in this system.

What are the values ofX' and X?
What is the formulaic consistency of this number system?

First of all, it seems that

in this system as in ordinary binary notation each bit has a definite value and the value of a given string of bits is the sum of the values associated with its 1-bits. What's different is that (1) the bit-values increase more slowly than for regular binary and (2) we therefore use only some subset of the possible bit-patterns. (Or, equivalently, (2) we only use some subset of the possible bit-patterns and therefore (1) the bit-values increase more slowly.)

Further,

the restriction on the bit-patterns so far always takes the following form: certain pairs of bits are not permitted both to be 1. Specifically, using the numbering scheme in the puzzle starting with bit 1 on the right: bits 2 and 3 must not both be 1; bits 5 and 6 must not both be 1; bits 7 and {6, 5, or 4} must not both be 1. (But bits 6 and 4 can both be 1, so it's not that the bits are divided into cliques and only one bit from each clique can be set.)

A little more specifically,

each bit excludes some (possibly zero) number of other bits to its right.

So in effect we are being asked

to continue the sequence that begins 0, 0, 1, 0, 0, 1, 3. Of course there are many many possible continuations, and so far I don't see anything that makes one vastly more obvious than another, which is why I find this answer less than perfectly satisfactory.

However, we can say that

so far, the bit positions that exclude other "smaller" bit positionsare precisely the ones whose (conventional) binary representation has consecutive 1-bits. Bit positions with just one pair of consecutive 1s exclude just the next-smallest bit. Bit positions with three consecutive 1s exclude the three next-smallest bits.

So

one possible way to continue this upward (we are now attempting to extrapolate the sequence that begins 0, 1, 3, and again this is not a problem with a unique solution) is as follows. If bit n (counting from 1 on the right) is set, look at the conventional binary representation of n and then at the string of 1-bits at its left. Consider just that string, delete its leading 1, and interpret what remains in conventional binary. That many bits after bit n must be zero.

If this is correct, then

bit 8 excludes no other bits, so the valid binary strings beginning with a 1 in position 8 are just what we get by taking the strings for 0..42 and adding a 1 in position 8, so the value of bit 9 is 2x42 = 84, X is 83, and X' is 11000101.

Another closely-related choice leading to the same conclusion for X,X' (but extending to infinity differently) would be

that the number of bits below the nth excluded by bit n is obtained by "planing" the binary expansion of n -- deleting one from each consecutive run of equal bits.

I suspect (especially as I don't really have an answer to the question "what is the formulaic consistency of this number system?") that humn has something more specific in mind. But I don't think the information we have been given so far suffices to pin it down.

• Those are the values alright, wow, @Gareth McCaughan! The formula is surprisingly straightforward though, in a slightly untraditional yet quite fair way, but I tried to keep data to a screenful. The values for 0 ≤ n ≤ 41 do have the unintended red herring of looking like binary-coded base 6, which is why the list goes to n = 42. Should I somehow add clues for the next few bits?
– humn
Mar 6, 2023 at 21:58
• The 3 low-order bits also have an unintended red herring that smells like regular binary and recurs in many other bits.
– humn
Mar 7, 2023 at 14:38