# Highly Dependent Lightbulbs

Logic Level 5

For integer $$n\geq2$$, I have $$n$$ lightbulbs arranged on the circumference of a circle, each lightbulb can be either on or off. When I press a button, the lightbulbs will either:

1. once every minute, be turned on if it is in the same state as the one of its left (both off or both on),
2. once every minute, be turned off if it is in the different state as the one of its left (one on and one off).

How many integers $$n < 10^6$$ are there such that after at most $$n$$ minutes, all the lightbulbs will be on simultaneously regardless of their initial states?

×