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 →

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Systematic & Data-Driven Trading

Doors toggled by primes

Answer

Related questions