$150$ switches question

Question

There are $150$ switches. First, You turn on all $150$ switches.Next, you turn off the even indexes.Then you toggles every third index and turn it off if it is on or turn it on if it is off. After $150$th pass. in which you toggle only switch number $150$, how many switches are on?

I solved it "brut force" and I found that the answer is $75$ (correct me if I'm wrong)

But I'm looking for explanation "number theory" style.

Attempt:

$1.$ turn on all $150$ switches

$2.$ turn off all index $i=0\pmod 2$

$3.$ something $\pmod 3$

Answer 1

Hint:

Go through $16$ or $17$ switches as a trial run and see what you notice about which switches are still on.

Answer:

Switches in $n^2, \, n\in\mathbb{Z}$ (square numbers) will still be on. The number of squares less than or equal to $n$ is $\lfloor\sqrt{n}\rfloor$. So for $n=150$ the answer is $12$.

Answer 2

Hint -

3. Turn on (mod 6)

Turn off (mod 3).

Hope it helps you.

Answer 3

THink of it this way:

Take switch $n$. How many times is $n$ toggled? Well, that depends. Depends on what? On how many factors $n$ has. Okay, let me put it this way, when is switch $n$ toggled? Whenever we are doing a number that is a factor of $n$. Okay, so how many times is $n$ toggled? As many times as $n$ has factors.

Does $n$ end up in the on or off position? Well, that depends. On what? How many factors $n$ have. How so; under what condition will it end up in on and under what conditions will it end up in off? Well, it will be on if it has an odd number of factors and off if it has an even number of factors.

Okay, which numbers have an odd number of factors and which numbers have an even number of factors? I have no idea.

Think about it more and get back to me. But consider:

How many factors does a prime number have? (Two, 1 and itself).

How many factors does a composite number like 24 have? (1,2,3,4,um,6,8,12,24, um 8 right?)

$n$ will always have $1$ and $n$ has factors. If it also has $k$ as a factor, can you name any other factor? (Um, $n/k$ will be a whole number, right? So $k*n/k =n$, so $n/k$ is also a factor, right?)

Is $n/k$ and new factor or one you already listed. (Well, it must be a new one as we have only listed $1,n,k$ and $n/k$ is different.)

What if $n/k = k$? (??????)

So, again, which numbers have an odd number of factors and which have an even number of factors? You can try some examples.

=====

"I solved it "brut force" and I found that the answer is 75 (correct me if I'm wrong)"

You are wrong.