Why does this mathematical pattern occurs here?

Question

The actual question goes like this

A room has N (1 to N inclusive) bulbs and N switches. N people go in one by one. 1st person goes in and toggles none of the switches. 2nd person goes in and toggles all switches other than the multiples of 2(2, 4, 6...). 3rd person goes in and toggles all switches other than multiples of 3(3, 6, 9...), and so on (Till Nth person toggles all the switches except Nth switch). Once the process is finished, how many bulbs are in 'on' state. (Assume that all bulbs to be in 'off' state initially).

The original question can be found here

I tried solving it by writing a brute force solver first, but it would have given me a "time limit exceeded" verdict because N can be as large as 10E9 ,

While testing the solutions for some values of N, I hit upon a pattern which led to the final solution

It is best explained with a picture, observe the number of 1's which are separated by 0's - 2 , 4 , 6 , 8 ...

But I am still unable to figure out why this pattern exists? In other words what is the mathematical reason behind this pattern?

Here is the draw(N) code I used

def draw(N):
    arr=[0]*N
    for i in range(2,N+1):
        for j in range(0,N):
            if((j+1)%i!=0):
                arr[j]^=1
    print(N,arr)
    ans=0
    for i in range(0,N):
        if(arr[i]==1):
            ans+=1
    print(ans)

Answer 1

This is a version of an old puzzle. The usual version has the nth person flip the switches whose numbers are divisible by n, and that produces the same pattern of squares (the switches with square indices 1, 4, 9, 16 are toggled) whether N is even or odd. Here, exactly the opposite switches are toggled, which is equivalent to toggling all switches an extra N times, which does nothing if N is even, and reverses them when N is odd. You showed only cases where N is odd, which means the squares are the switches that don't change states.

Factors of a number come in pairs, except when the number is a square, since we can pair the factor x with n/x, and these are distinct except when x^2=n.

For example, 18 has 6 factors: 1 and 18, 2 and 9, and 3 and 6. So, if you toggle switch 18 once for each factor, it stays in its original state.

100 has 9 factors: 1 and 100, 2 and 50, 4 and 25, 5 and 20, and sqrt(100)=10. So, if you toggle switch 100 once for each factor, it changes states.

You mentioned the number of 1s between the 0s. (n+1)^2-n^2 = 2n+1. So, you are seeing 2, 4, 6, 8, etc. 1s between the 0s for N odd.

Answer 2

Douglas Zare already explained the relationship to an older problem, so I'm just going to detail the solution to the older problem, whose sequence shows up in your image anyway.

I assume the switches are initially off (0), but the reasoning is the same regardless. The first person leaves them all off. The second person turns on 2 4 6 .... The one that will obviously stay on out of these is 2, because according to the problem's rules, it will never be toggled again.

Then the third person toggles 3 6 9 .... Again, obviously 3 will stay on.

Then the fourth person toggles 4 8 12 .... Obviously 4 will stay off forever (it was turned on by the second guy).

Now we can tell (it might be more obvious if you go up to the 9th guy) that perfect squares will always be off and the rest will always be on. These statements require an explanation:

1. Perfect squares will always be off

A perfect square has an odd number of factors:

x^2 = (p_1^e_1 * ... * p_k^e_k)^2
    = p_1^2e_1 * ... * p_k^2e_k,  p_i prime
divisors(x^2) = (2e_1 + 1)(2e_2 + 1)...(2ek + 1) = odd

By the number of divisors formula.

Since each number is toggled by its divisors, the perfect squares will always end up in the initial state, because they have an odd number of divisors.

2. Numbers that aren't perfect squares will always be on

This is because only perfect squares have an odd number of divisors, so the other numbers will always be in the opposite of the initial state.

Assume a non-perfect square has an odd number of divisors. Then:

divisors(x) = (e_1 + 1)...(ek + 1) = odd
=> all e_k are even
=> we can write the number as (p_1^(e_1 / 2) * ... * p_k^(e_k / 2))^2
=> x is a perfect square, a contradiction.

Then the efficient solution for the problem involves finding how many perfect squares are below n: there are sqrt(n) perfect squares below n, and these are 1, 2, ..., sqrt(n) - 1, sqrt(n).