I've been thinking about this problem for two days and haven't found any efficient way to solve it.
An experiment carried out with 150 people asked each participant to receive as identification one of the numbers between 1 and 150. Then, they were taken to a room where there were 150 lamps, each numbered from 1 to 150 and with its respective switch. All lamps were initially on. Then, it was requested that, starting from participant number 1, each person should switch the state of all the lamps whose number was a divisor of the number received by the participant before entering the room. How many light bulbs were off in the end of the experiment?
The correct answer is $104$. I see that the $n$-th light bulb were off iff the number of multiples of $n$ is odd. Using brute force, I found that these numbers are $2$, $4$, $6$, $7$, $10$, $11$, $13$, $16$ and those in the ranges $[19, 21]$, $[26, 30]$, $[38, 50]$, $[76, 150]$. Then I added up the amount of these numbers and found the correct answer.
If instead of "divisor" it was "multiple", I'd know how to easily solve it using the property that only perfect squares have an odd number of divisors. But this problem is different.
My question :
Is there a more efficient way to solve this problem?
Best Answer
Some progress.
We are looking for how many $m$ where $m,n \in \mathbb{N}$, $m,n \in [1,150]$, $$\Big\lfloor \dfrac{150}{m} \Big\rfloor=n=\text{odd}$$
An observation is if $(m,n)$ is a valid pair then so is $(n,m)$. Due to this, required number is given by $$\Big\lfloor \dfrac{150}{1} \Big\rfloor - \Big\lfloor \dfrac{150}{2} \Big\rfloor + \Big\lfloor \dfrac{150}{3} \Big\rfloor - \Big\lfloor \dfrac{150}{4} \Big\rfloor + \cdots $$
Although this evaluates to $104$, there is more insight needed.