Box-Ball System

Consider an infinite row of boxes. Some of the boxes contain a ball. For example, an initial configuration of 2 consecutive occupied boxes followed by 2 empty boxes, 2 occupied boxes, 1 empty box, and 2 occupied boxes can be denoted by the sequence (2, 2, 2, 1, 2), in which the number of consecutive occupied and empty boxes appear alternately.

A turn consists of moving each ball exactly once according to the following rule: Transfer the leftmost ball which has not been moved to the nearest empty box to its right.

After one turn the sequence (2, 2, 2, 1, 2) becomes (2, 2, 1, 2, 3) as can be seen below; note that we begin the new sequence starting at the first occupied box.

A system like this is called a Box-Ball System or BBS for short.

It can be shown that after a sufficient number of turns, the system evolves to a state where the consecutive numbers of occupied boxes is invariant. In the example below, the consecutive numbers of occupied boxes evolves to [1, 2, 3]; we shall call this the final state.

We define the sequence {ti}:s0 = 290797
sk+1 = sk2 mod 50515093
tk = (sk mod 64) + 1

Starting from the initial configuration (t0, t1, …, t10), the final state becomes [1, 3, 10, 24, 51, 75].
Starting from the initial configuration (t0, t1, …, t10 000 000), find the final state.
Give as your answer the sum of the squares of the elements of the final state. For example, if the final state is [1, 2, 3] then 14 ( = 12 + 22 + 32) is your answer.

To solve this problem, we will simulate the Box-Ball System (BBS) starting from the given initial configuration. We will use Python code to implement the simulation and calculate the final state.

Let’s start by defining a function `bbs_simulation` to simulate the BBS for a given configuration. The function takes an array `initial_state` as input and returns the final state.

“`python
def bbs_simulation(initial_state):
final_state = list(initial_state) # Create a copy of the initial state
num_turns = len(initial_state)

for i in range(num_turns):
for j in range(final_state[i]):
# Move the leftmost ball to the nearest empty box
index = final_state.index(j+1)
final_state[index] += 1
final_state[i] -= 1

return final_state
“`

Next, we define another function `calculate_final_state` to calculate the final state starting from `t0` to `t10_000_000` and return the sum of the squares of the elements.

“`python
def calculate_final_state(t0, num_iterations):
t = [t0]

# Generate the sequence {ti} using the given recurrence relation
for _ in range(num_iterations):
t.append((t[-1] * t[-1]) % 50515093)

initial_state = [((t[i] % 64) + 1) for i in range(num_iterations+1)]
final_state = bbs_simulation(initial_state)
sum_squares = sum([x**2 for x in final_state])

return sum_squares
“`

Now, we can call the `calculate_final_state` function with the given initial configuration `(t0, t1, …, t10_000_000)` to get the final state and calculate the sum of the squares of its elements.

“`python
t0 = 290797
num_iterations = 10_000_000
result = calculate_final_state(t0, num_iterations)

print(result)
“`

The output will be the sum of the squares of the elements in the final state.

Note: Calculating the final state for `num_iterations = 10_000_000` may take a while to run since there are a large number of iterations involved. You can try running the code on a powerful machine or reduce the number of iterations if the execution time is a concern.

More Answers: