The question is pretty simple, consider 1000 switches and 1000 light bulbs, every time we press a switch it's light bulb changes it's state(ON to OFF and vice versa). We start with all the light bulbs at OFF, We take 1000 frogs, the first frog jumps on all the switches, the second only on even numbers, the third on numbers which are multiples of three etc. The question is which light bulbs will stay ON.
From a number theory point of view, this problem can be simplified to which numbers has odd divisors number, so if we take a number and break it down to its prime divisors, count the multiplicity of each prime, we can see that each divisor can be expressed using those primes.
For instance $360=2^3*3^2*5^1$ so every divisor is written as $2^a*3^b*5^c, 0≤a≤3 , 0≤b≤2, 0≤c≤1$, So all in all we have 24 possibilities which is even.
We want odd possibilities, well this only occurs if we have only even multiplicities, then the numbers will have an integers square root.
This is the solution I thought about, but it seems lengthy, Is there any simpler methods to simplify this problem.
I think this problem is generally thought of as following from the claim: The number of divisors of an integer is odd if and only if the integer is a perfect square. This proposition usually follows from studying the number-of-divisors function, which is multiplicative, and odd when applied to a prime raised to an even power, i.e., a perfect square.
Your reasoning is completely correct, except that you said "square root" instead of "perfect square".