Wonders Electrical Engineers Do With Bulbs!

Behold the power of a pure functional programming language!

1
2

Prelude> let x = takeWhile (<=10000) [i^2 | i <- [1..]] in length x + sum x
338450

The time complexity of this solution is $\Theta (\sqrt n)$

Proof of how only squares work:

Let $\tau (n)$ denote the number of positive divisors of $n$ (including both 1 and $n$ ).

Before the first pulse, all the bulbs are off (call this the 0 state and call the on state as the 1 state). After the all of the 10000 pulses, say the $i^{th}$ bulb is in state $r$ . Then we claim that $r \equiv \tau (n) \pmod 2$ . The proof of this easy to see if the toggling function (T) is seen as follows : $T : \{0,1\} \to \{0,1\} \\ T(i) \equiv i+1 \pmod 2$

Hence the $i^{th}$ bulb is on if and only if $\tau (i)$ is odd.

We show now that $\tau (i)$ is odd if and only if $n$ is a perfect square.

Let $n = \displaystyle \prod_{i} p_i^{\alpha_i}$ where $p_i$ is a prime for all $i$ .

Then it follows that if $d|n$ then $d = \displaystyle \prod_{i} p_i^{\beta_i} \quad 0 \leq \beta_i \leq \alpha_i$

Hence, $\tau (n) = \prod_{i} (1+\alpha_i)$ The desired conclusion now follows.

The solutions are perfect squares. Other non-programming solutions are also accepted.