Can the Ionians continue counting indefinitely while following their four rules?

[Jehannum]

The society on Jupiter's moon Io has a very odd way of counting. They count in binary using special counters: small discs with 0 printed on one side and 1 on the other. To increase speed when counting they made a rule:

Rule #1: To get the next number in the sequence, only one counter can be turned over.

To ensure all of their numbers are unique they made a second rule:

Rule #2: The next number in the sequence must not have already appeared.

They start counting with a single counter showing 0 and then flip it to get 1. To progress any further a new counter is needed. Again, to ensure speed, they made this third rule:

Rule #3: When no more numbers can be made a single counter can be added on the left.

They can't put the new counter down with the 0 on top to get 01 because 01 equals 1, which has already been used. Instead, the sequence continues like this:

11, 10

Now another counter must be added on the left:

110

Here there appears to be a choice: do they flip the second counter along to get 100 or the third to get 111? To avoid ambiguity they made a fourth rule:

Rule #4: The next number in the sequence must have the lowest possible value.

So the sequence continues like this:

100, 101, 111, 1111, 1011, 1001, 1000, 1010, 1110, 1100, 1101, 11101, 10101, etc.

The question is: can the Ionians continue to count like this indefinitely while adhering strictly to their four rules?

If you solve the puzzle please explain how you did it.

 

[mfb]

With a different rule 4 you get a Gray code.

The question is: can the Ionians continue to count like this indefinitely while adhering strictly to their four rules?

Yes. How could you not? You can always add a 1 to the left to create a new number if there is no other option left, creating a new number (as no previous number had the same number of digits).

 

[phinds]

With a different rule 4 you get a Gray code.Yes. How could you not? You can always add a 1 to the left to create a new number if there is no other option left, creating a new number (as no previous number had the same number of digits).

Yeah. What he said.

 

[Jehannum]

Before I post what I think is the solution I will say there is "still scope for further answers".

 

[Jehannum]

Sorry folks, to make the puzzle work as intended I should have specified a 5th rule:

The Ionians are very concerned about efficient use of materials so:

Rule #5: Leading zero counters must be removed.

i.e. if the most significant bit counter flips to zero, it has to be taken away.

Does this change things at all?

 

[mfb]

Ah, so we can remove digits. Then it gets more interesting. For the first few digits all options are visited before another 1 is added, but this changes once we go to 6-digit numbers, and more 6-digit numbers are visited after a couple of 7-digit numbers, first at 1101100 -> 101100.
Just by continuing the sequence with some computer assistance, we run into a dead end at 111101101->11101101 after 488 steps.

Spoiler: python

import math

def  getsortedoptions(word):
  len=int(math.ceil(math.log(word+1,2)))
  options=[]
  for i in range(0, len+1):
    options = options + [word ^ 2**i]
  options.sort()
  return options

words=[0]
for k in range(0,1000):
  okay=0
  for option in getsortedoptions(words[-1]):
    if option not in words:
      words = words + [option]
      okay=1
      break
  if not okay:
    print "no options left after "+str(k)+" steps"
    break

for word in words:
  print "{0:b}".format(word)

 

[Jehannum]

Correct! Sorry for the delay in confirming. I was just a bit embarrassed by the blunder about omitting Rule #5.

Here's the solution as intended:

Let’s join the sequence at the 486th term:

#486 1 1 1 1 0 1 1 1 1 = 495
#487 1 1 1 1 0 1 1 0 1 = 493
#488 1 1 1 0 1 1 0 1 = 237

For the first time in the sequence, the most significant bit is changed from 1 to 0 to get the next number, 1 1 1 0 1 1 0 1 (237).

Rule #5 says that leading zeros must be removed so now let’s try to get term #489:

#488 1 1 1 0 1 1 0 1 = 237
Try: 0 1 1 0 1 1 0 1 = 109 Already used as the 121st term
1 0 1 0 1 1 0 1 = 173 the 163rd term
1 1 0 0 1 1 0 1 = 205 the 203rd term
1 1 1 0 0 1 0 1 = 229 the 231st term
1 1 1 0 1 0 0 1 = 233 the 237th term
1 1 1 0 1 1 0 0 = 236 the 193rd term
1 1 1 0 1 1 1 1 = 239 the 235th term
1 1 1 1 1 1 0 1 = 253 the 407th term
1 1 1 1 0 1 1 0 1 = 493 the 487th term

So, because of rule #5 we can’t now add a single counter to get the next term.

Thanks for the Python program. I'm just learning the language and this puzzle was actually my first ever program in this language.

BTW, I discovered the sequence generated is OEIS A163252.