Skip to content

Prime-indexed door togglers on 100 doors

Question

A hallway has 100100 doors, numbered 11 through 100100, and every one of them starts the day open. A sequence of workers then passes through. Worker number kk is assigned the kk-th prime (2,3,5,7,…2, 3, 5, 7, \dots) 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 100100 has had its worker, how many doors remain open?

Short answer

57. Door nn is flipped once for each distinct prime dividing it, so it ends open exactly when nn has an even number of distinct prime factors. The doors that end shut are the 2525 primes, the 1010 higher prime powers (4,8,9,16,25,27,32,49,64,814,8,9,16,25,27,32,49,64,81) and the 88 numbers with three distinct primes (30,42,60,66,70,78,84,9030,42,60,66,70,78,84,90): 4343 in all, leaving 100−43=57100-43=57 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