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

In summary, the society on Jupiter's moon Io counts in binary using special counters and has four rules to ensure unique numbers. However, with the addition of a fifth rule, the sequence eventually reaches a dead end, as shown by the example of term #486. This sequence is known as OEIS A163252 and has been solved using a Python program.
  • #1
Jehannum
102
26
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.
 
Mathematics news on Phys.org
  • #2
With a different rule 4 you get a Gray code.
Jehannum said:
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).
 
  • #3
mfb said:
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.
 
  • #4
Before I post what I think is the solution I will say there is "still scope for further answers".
 
  • #5
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?
 
  • #6
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.
Code:
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)
 
  • #7
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.
 
  • Like
Likes jim mcnamara

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

1. What is a Mathematics binary puzzle?

A Mathematics binary puzzle is a logic puzzle that involves filling in a grid with 0s and 1s according to a set of given clues. The goal is to fill in the entire grid with the correct numbers while following specific rules.

2. How do you solve a Mathematics binary puzzle?

To solve a Mathematics binary puzzle, you need to carefully analyze the given clues and use logic and deduction to determine the correct placement of 0s and 1s in the grid. It may also be helpful to start with the rows or columns that have the most given clues to narrow down the possible solutions.

3. What are the rules of a Mathematics binary puzzle?

The rules of a Mathematics binary puzzle vary depending on the specific puzzle, but they generally include the following: each row and column can only have an equal number of 0s and 1s, no more than two consecutive 0s or 1s can be placed in a row or column, and each row and column must be unique.

4. Are there different levels of difficulty for Mathematics binary puzzles?

Yes, there are different levels of difficulty for Mathematics binary puzzles. Some puzzles may have more given clues and be easier to solve, while others may have fewer given clues and require more advanced logic and deduction skills to solve.

5. Can Mathematics binary puzzles help improve math skills?

Yes, solving Mathematics binary puzzles can help improve math skills such as logic, deduction, and pattern recognition. It can also help develop problem-solving and critical thinking abilities.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • General Math
Replies
7
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
3K
Replies
21
Views
3K
  • Math Proof Training and Practice
2
Replies
67
Views
10K
  • Math Proof Training and Practice
6
Replies
175
Views
20K
Replies
6
Views
13K
  • Set Theory, Logic, Probability, Statistics
3
Replies
93
Views
17K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
6
Views
3K
Replies
11
Views
5K
Back
Top