Doors toggled by primes

HardCombinatorics Brainteasers~9m

$100$ doors, labelled $1$ – $100$ , all start open. Janitors act in turn: the $k$ -th janitor toggles (opens if closed, closes if open) every door whose number is a multiple of the $k$ -th prime ( $2, 3, 5, 7, \dots$ ). After all janitors have acted, how many doors are open?

Show hints (2)+

Door $d$ is toggled once per distinct prime factor - that's $\omega(d)$ times. It starts open.
Open at the end iff $\omega(d)$ is even (including $d=1$ with $\omega=0$ ). Count those in $1..100$ .

Answer

Reveal answer →

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Practise free Unlock solutions

Asked at: Jane Street, Two Sigma

Doors toggled by primes

Answer

Related questions