Hallway of Square Steps

Problem Statement

Peter moves in a hallway with $N + 1$ doors consecutively numbered from $0$ through $N$. All doors are initially closed. Peter starts in front of door $0$, and repeatedly performs the following steps:

  • First, he walks a positive square number of doors away from his position.
  • Then he walks another, larger square number of doors away from his new position.
  • He toggles the door he faces (opens it if closed, closes it if open).
  • And finally returns to door $0$.

We call an action any sequence of those steps. Peter never performs the exact same action twice, and makes sure to perform all possible actions that don't bring him past the last door.

Let $F(N)$ be the number of doors that are open after Peter has performed all possible actions. You are given that $F(5) = 1$, $F(100) = 27$, $F(1000) = 233$ and $F(10^6) = 112168$.

Find $F(3 \times 2^N)$.

Submit Answers

You need to submit in the format: "N:problem(N)", possibly with multiple values at once, separated by commas, with $N$ between $1$ and $100$.

Top Users

🥇 icy
43.00 (51)
🥈 shs10978
43.00 (43)
🥉 jonnytang
16.00 (16)
4 mmtg
1.00 (1)

Data

Stats

Your submissions will appear here

Recent Submissions

1
mmtg
$g(1)$, $1$ digits 2 weeks, 3 days ago
2
mmtg
$g(1)$, $1$ digits 2 weeks, 3 days ago
3
mmtg
$g(1)$, $1$ digits 2 weeks, 3 days ago
4
mmtg
$g(1)$, $1$ digits 2 weeks, 3 days ago
5
mmtg
$g(1)$, $1$ digits 2 weeks, 3 days ago