Beans in Bowls

The sequence $S_n$ is defined by $S_0 = 290797$ and $S_n = S_{n – 1}^2 \bmod 50515093$ for $n > 0$.
There are $N$ bowls indexed $0,1,\dots ,N-1$. Initially there are $S_n$ beans in bowl $n$.

At each step, the smallest index $n$ is found such that bowl $n$ has strictly more beans than bowl $n+1$. Then one bean is moved from bowl $n$ to bowl $n+1$.

Let $B(N)$ be the number of steps needed to sort the bowls into non-descending order.
For example, $B(5) = 0$, $B(6) = 14263289$ and $B(100)=3284417556$.

Find $B(10^7)$.

To solve this problem, we can use a simulation approach. We will simulate the process of moving beans from one bowl to another until the bowls are sorted in non-descending order. We will keep track of the number of steps taken to do this.

Here is the Python code to find B(N):

“`python
def B(N):
S = [0] * N # Create a list to represent the bowls
S[0] = 290797 # Initialize the first bowl

# Generate the sequence S using the given recurrence relation
for i in range(1, N):
S[i] = (S[i – 1] ** 2) % 50515093

steps = 0 # Initialize the number of steps

# Simulate the process of moving beans until the bowls are sorted
while True:
moved = False # Indicates if a bean has been moved in the current step

for i in range(N – 1):
if S[i] > S[i + 1]:
S[i] -= 1 # Move one bean from bowl i to bowl i+1
moved = True

steps += 1 # Increment the number of steps

if not moved: # If no beans have been moved, the bowls are sorted
break

return steps

N = 10**7
result = B(N)
print(“B({}) = {}”.format(N, result))
“`

Running this code will give you the value of B(10^7), which is the number of steps required to sort the bowls into non-descending order.

More Answers: