How Many Cars Are On This Circular Train?

Riddler Express

What is the next number in this series? $$1111211121212211212221212121\ldots$$

The Riddler, FiveThirtyEight, August 2, 2019(original post)

Solution

Read the digits against the counting numbers starting at $2$. The first digit goes with $2$, the second with $3$, and so on. Each digit is the number of distinct primes dividing that number. The numbers $2, 3, 4, 5$ are each a power of a single prime, so they contribute $1, 1, 1, 1$; then $6 = 2 \cdot 3$ has two distinct primes, giving $2$; $7$ gives $1$; and so on. Lining the digits up with $2, 3, 4, \ldots$ reproduces the string exactly.

The string has $28$ digits, so it ends at the number $29$. The next digit belongs to $30 = 2 \cdot 3 \cdot 5$, which has three distinct prime factors. The next number is $$\boxed{3}.$$

The computation

Encode the rule directly: count the distinct prime factors of $2, 3, 4, \ldots$, build the string, and check it matches the given one; the next term is the count for the following number.

from sympy import primefactors
s = "1111211121212211212221212121"
gen = "".join(str(len(primefactors(n))) for n in range(2, 2 + len(s)))
print("matches:", gen == s)
print("next term:", len(primefactors(2 + len(s))))   # distinct primes of 30
# matches: True
# next term: 3

Riddler Classic

You are on a train whose cars are connected in a circle, of some unknown number $N$. You can walk between adjacent cars (and walking far enough returns you to where you started), and each car has one light you can switch on or off; the lights start in a random pattern. You cannot mark a car, and a car’s light is only visible from inside it. Using only walking and switching, what is the most efficient way to determine how many cars there are?

The Riddler, FiveThirtyEight, August 2, 2019(original post)

Solution

The lights are the only memory you have, and the random start is the only obstacle. The key building block is a test, call it $\textsf{check}(n)$, that decides whether the train has $n$ cars or fewer.

The test. Turn the light in your current car on, then walk forward $n$ cars, switching each car you enter off. Finally walk the $n$ cars back to your start. If the train has $N \le n$ cars, your forward walk goes all the way around (at least once), so at step $N$ you re-enter your start car and switch its light off; it stays off, and when you return you find it off. If $N > n$, you never circle back, your start light is untouched, and you find it still on. So the start light, read on return, tells you whether $N \le n$.

A clean side effect. When $N \le n$, the forward walk enters every car at least once and leaves it off, so the whole train ends up dark. That gives you a clean slate with no marking: now turn your start light on (the only lit car), walk forward counting until you re-enter a lit car. That can only be your start, reached after exactly $N$ steps, so you read off $N$.

Efficiency. Testing $n = 1, 2, 3, \ldots$ in turn would take on the order of $N^2$ steps. Instead double: test $n = 1, 2, 4, 8, \ldots$ until a test succeeds. The successful test costs about $2N$ steps, the failed ones sum to less than that, and the final exact count costs $N$, so the whole job is $$\boxed{\text{linear in } N \text{ (about } 5N \text{ to } 9N \text{ steps)}},$$ not quadratic. Doubling is what turns a workable method into an efficient one.

The computation

Simulate the train as a circle of lights set at random, with a step counter, and run the doubling-plus-exact-count method. It must return the true $N$ for every train, and the step count must grow linearly.

1. $\textsf{check\_le}(n)$: light the start, walk forward $n$ switching off, walk back $n$; return whether the start ended dark (and, when true, the train is all dark).

2. Double $n$ until $\textsf{check\_le}$ succeeds; the train is now dark at the start.

3. Light the start and walk forward until re-entering a lit car; the step count is $N$.

import random
class Train:
    def __init__(self, N, seed):
        r = random.Random(seed)
        self.N = N; self.L = [r.randint(0, 1) for _ in range(N)]
        self.pos = 0; self.steps = 0
    def move(self, d): self.pos = (self.pos + d) % self.N; self.steps += 1
    def on(self): self.L[self.pos] = 1
    def off(self): self.L[self.pos] = 0
    def lit(self): return self.L[self.pos] == 1

def check_le(t, n):
    t.on()
    for _ in range(n): t.move(+1); t.off()
    for _ in range(n): t.move(-1)
    return not t.lit()                      # start dark <=> N <= n (then all dark)

def count_cars(N, seed):
    t = Train(N, seed); n = 1
    while not check_le(t, n): n *= 2        # doubling
    t.on(); c = 0                            # clean slate: only start is lit
    while True:
        t.move(+1); c += 1
        if t.lit(): return c, t.steps        # re-entered the start after N steps

print("all N in 1..60 correct:",
      all(count_cars(N, s)[0] == N for N in range(1, 61) for s in range(4)))
for N in (20, 40):
    avg = sum(count_cars(N, s)[1] for s in range(20)) / 20
    print(f"N={N}: avg steps {avg:.0f}")
# all N in 1..60 correct: True
# N=20: avg steps 146    N=40: avg steps 294   (linear)

The method recovers the exact car count for every train, and the step count roughly doubles when $N$ does, confirming the linear efficiency.