Asymptotic behavior in a modular color-cycling problem

Question

Consider the following problem: We have $k$ rooms, each equipped with a light that cycles through three colors – red, green, and blue – in a cyclic order. Initially, all lights are set to red. Each of $k$ guests enters the rooms sequentially, with the $n$-th guest advancing the light in every $n$-th room by $n \bmod 3$ steps. After a guest leaves, if the light is green, a mischievous cat resets it to red. I seek to understand the asymptotic behavior of the number of blue lights as $k$ approaches infinity.

Numerical simulations indicate that the percentage of blue lights decreases as $k$ increases, while the positions of the blue lights across the rooms show a near-linear distribution. For large $k$, the percentage of blue lights appears to stabilize around a certain value, though it continues to decrease slowly. You can see plots of the numerical simulations here (I can't embed images as a new user). The full dataset (up to $k = 10^9$ rooms) and the Python code used to generate these plots can be downloaded here.

Without the cat, the color of the light in room $n$ after all guests have visited can be described by the divisor function $\sigma(n) \bmod 3$, where $\sigma(n)$ is the sum of the divisors of $n$. It can be shown that without the cat's intervention, the natural density of red lights tends to 1 as $n$ approaches infinity ($\lim_{n \to \infty} \frac{ n : \sigma(n) \equiv 0 \bmod 3}{n} = 1$).

The cat introduces a non-trivial modification by resetting any light that turns green (i.e., every time the partial sum $\sum_{d \mid n, d \le i} d \equiv 1 \bmod 3$) back to red (subtracting $1 \bmod 3$ every time this occurs).

I am seeking to understand:

1. Whether the percentage of blue lights converges to a specific value as $k$ approaches infinity, or if it continues to decrease indefinitely.
2. If there is a rigorous explanation for the observed linear distribution of blue lights.
3. How does the cat’s interference alter the asymptotic behavior of the system, and can this be rigorously analyzed using tools from analytic number theory or combinatorial game theory?

UPDATE: I searched for the smallest congruence classes that show properties without overlap and found: $$always\ red = 1 \bmod 3, 3 \bmod 9, 9 \bmod 27, 27 \bmod 81, 81 \bmod 243, 243 \bmod 729, \{77, 231, 539, 693\} \bmod 770, 729 \bmod 2187, 2187 \bmod 6561$$ $$always\ blue = 2 \bmod 6, 5 \bmod 15, 6 \bmod 18, 15 \bmod 45, 18 \bmod 54, 45 \bmod 135, 54 \bmod 162, \{11,143,209\} \bmod 231, 135 \bmod 405, \{341,407\} \bmod 462, 162 \bmod 486, \{33,429,627\} \bmod 693, 737 \bmod 924, 405 \bmod 1215, \{1023,1199,1221\} \bmod 1386, 486 \bmod 1458, \{99,1287,1881\} \bmod 2079, 2123 \bmod 2310, 2211 \bmod 2772, 3047 \bmod 3234, 1215 \bmod 3645, \{3069,3597,3663\} \bmod 4158, 1458 \bmod 4374, \{17, 323, 527, 629, 731, 1037, 1139, 1241, 1343, 1649, 1751, 1853, 2159, 2363, 2567, 2669, 2771, 3077, 3281, 3383, 3587, 3791, 3893, 4097, 4607\} \bmod 4641, 5819 \bmod 6006, \{297, 3861, 5643\}\bmod 6237, 6369 \bmod 6930, 7667 \bmod 7854, 6633 \bmod 8316, 8591 \bmod 8778, \{4709, 4811, 4913, 5219, 5321, 5627, 5729, 5933, 6137, 6239, 6341, 6443, 6647, 6749, 6953, 7157, 7361, 7463, 7769, 7871, 8279, 8381, 8483, 8891, 8993, 9197\}\bmod 9282$$ All of this should be proved rigorously, but it holds for $10^8$ rooms. All of this would give a lower bound of the natural density of blue lights of $\frac{7667142635}{19799007228} \approx 38.72488\%$, as well as an upperbound of $\frac{1250063}{2525985} \approx 49.488\%$

While blue light patterns appear to be quite chaotic, red lights show a nice pattern, that if holds, lets us slightly improve the upperbound: $$1 - (\frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \frac{1}{81} + \frac{1}{243} + \frac{1}{729} + \frac{4}{770} + \frac{1}{2187} + \frac{1}{6561} + \dots) \approx 1 - (\frac{4}{770}+\sum_{i=1}^{\infty}\frac{1}{3^i})=1-(\frac{4}{770}+\frac{1}{2})=\frac{381}{770} \approx 49.4805\%$$

Answer 1

First note that any guest whose number is divisible by $3$ does not contribute to the lighting. Hence the light in room $3^kn$ will be the same as the light in room $n$ for all $k, n \in \mathbb{N}$.

Due to the cat's behaviour,

• $n \equiv 1 \mod 3$ turns any light red
• $n \equiv 2 \mod 3$ switches red and blue

Thus rooms with blue lights will be precisely the rooms where there are an odd number of divisors congruent to $2$ greater than its greatest divisor congruent to $1$.

To answer your first question, consider all numbers $n \equiv 2 \mod 6$. Its largest divisors are $n / 2 \equiv 1 \mod 3$ and $n \equiv 2 \mod 3$. Thus the light always ends up blue. Therefore the fraction of blue lights is bounded below by $1 / 6$.

More results can be found by considering different congruence classes of products of small primes. For example, if $n \equiv 1 \mod 3$ then the light is red; if $n \equiv 5 \mod 30$ then the light is blue. This gives some intuition for the linear behaviour. However more advanced techniques would be necessary to prove convergence.

Note that we can also say that the colour of room $n$ depends only on $n / 3^{e_3(n)} \mod 3$ and all its divisors $d_1,d_2,...,d_i \leq k$ whenever $n / (3^{e_3(n)}d_i) \equiv 1 \mod 3$ for some $i$. You then could try to prove that:

• the fraction of $n$ such that $n / (3^{e_3(n)}d) \equiv 1 \mod 3$ for some $d \leq k$ converges to $1$ as $k \rightarrow \infty$
• for fixed $k$ the fraction of blue light converges on the subset of $n$ with this property

Finally, neither the guests and the cat make their own decisions and rather follow a predetermined strategy. Therefore it is not really a game theory question and number theory is indeed the way to go.

---

Here is some code that should give some bounds. Note that is very inefficient, since it e.g. considers all congruence classes $1 \mod 3$ separately. It's probably more efficient to search the congruence classes in a tree-like fashion: first look at everything modulo 3, then only refine $2 \mod 3$ to $2, 5 \mod 6$ etc.

import math

def bounds(k):
    m = 3
    for i in range (1, k + 1):
        if i % 3:
            m = i * m // math.gcd(i, m)
    print("modulus: " + str(m))
    red, blue, unknown = 0, 0, 0
    total = 0
    for i in range (0, m):
        if i % 3 == 0:
            continue
        total += 1
        if i % 3 == 1:
            red += 1
            continue
        d = []
        for j in range (1, k + 1):
            if i % j == 0:
                if j % 3 == 2:
                    if len(d) % 2 == 0:
                        red += 1
                        break
                    else:
                        blue += 1
                        break
                d.append(j)
        else:
            unknown += 1
    print("red: {}\nblue: {}\nunknown: {}".format(red / total, blue / total, unknown / total))

Result:

>>> bounds(22)
modulus: 77597520
red: 0.5047129341246989
blue: 0.32416407122289476
unknown: 0.1711229946524064