Prime-indexed door togglers on 100 doors
Question
A hallway has doors, numbered through , and every one of them starts the day open. A sequence of workers then passes through. Worker number is assigned the -th prime () and flips the state of every door whose number is a multiple of that prime: an open door gets shut and a shut door gets reopened. Once every prime up to has had its worker, how many doors remain open?
Short answer
57. Door is flipped once for each distinct prime dividing it, so it ends open exactly when has an even number of distinct prime factors. The doors that end shut are the primes, the higher prime powers () and the numbers with three distinct primes (): in all, leaving open.
Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.
See the hint and the full worked solution in the question bank (free account).
Open the worked solution