Papierstreifenspiel

Das folgende Spiel ist ein klassisches Beispiel der kombinatorischen Spieltheorie:

Zwei Spieler starten mit einem Streifen aus $n$ weißen Quadraten und spielen abwechselnd je einen Zug.
Bei jedem Zug wählt ein Spieler zwei benachbarte weiße Quadrate und färbt sie schwarz.
Der erste Spieler, der keinen Zug mehr spielen kann, verliert.

• $n = 1$: Keine gültigen Züge. Der erste Spieler verliert daher automatisch.
• $n = 2$: Nur ein gültiger Zug, nach welchem der zweite Spieler verliert.
• $n = 3$: Zwei gültige Züge, aber beide führen zu einer Spielsituation, bei der der zweite Spieler verliert.
• $n = 4$: Drei gültige Züge für den ersten Spieler, der gewinnen kann, indem er die beiden mittleren Quadrate färbt.
• $n = 5$: Vier gültige Züge für den ersten Spieler (s. unten in rot). Aber der zweite Spieler gewinnt, egal welchen Zug der erste Spieler wählt.

Für $1 \le n \le 5$, gibt es also 3 mögliche Werte für $n$, bei denen der erste Spieler einen Sieg erzwingen kann.
Für $1 \le n \le 50$ gibt es 40 mögliche Werte für $n$, bei denen der erste Spieler einen Sieg erzwingen kann.

Wie viele mögliche Werte für $n$ mit $1 \le n \le 1 000 000$ gibt es, bei denen der erste Spieler einen Sieg erzwingen kann?