Problems & Puzzles: Puzzles

Puzzle 156.  One million doors

The following is the prime version of the puzzle "Doors" published in the always interesting pages of the site of my friend Frank Rubin: Contest Center.

According to Frank: "Bhattacharyya is certainly not the author of that puzzle.  He is actually the 3rd person to submit it to me.  (I'm told it was on the 1999 entrance exam for the Indian Statistical Institute in Calcutta.)  I just figured if 3 people sent it, then it must be popular"

This our prime version of it:

Suppose there are one million doors namely d1, d2, d3, ... , all closed at the beginning, and there are one million persons p1, p2, p3, ...

First p1 opens all even numbered doors.
Then p2 changes the state every third door (opens d3, closes d6, etcetera)
Then p3 changes the state to every fifth door
And so on.

Question: at the end, how many and which  doors remain closed/open? 

Solution:

To the question of which doors will be open at the end of the process, this was correctly responded by Jean Brette, Leadhyena Inrandomtan & Santi Spadaro:

"An open doors d_i is such that its index i has an odd number of distinct prime factors."

To the question of how many doors will be open at the end of the process, responded correctly Leadhyena Inrandomtan and Paul Jobling.

"Open Doors = 500954"

Both proceeded to count one by one all the indexes with the property stated above.

***

According to their quantitative results it seems that we may conjecture that:

CR-Conjecture: Open doors -> (n/2), as n goes to infinite

Can you say something about this conjecture?

***

Leadhyena Inrandomtan devised a parallelism between the questions asked and the already existing functions: Moebius and Mertens. His approach goes like this:

Let's define:

1) m(n) = Moebius-Like function of n, such that:

• m(n) is +1 if n has an odd quantity of prime factors ("an open door")

• m(n) is -1 if n has an even quantity of prime factors ("a closed door")

• m(1) = -1

2) M(n) = Mertens-Like function = Sum(m(i)) for i=1 to n

Then he calculated "by brute force" M(1000000) - using a code made by him - obtaining the following result:

M(1000000) = - 1908

But as open + closed = 1000000 and as closed - open = -1908, then closed = 499046 and then open = 500954

For the purposes of our current problem the Inrandomtan approach does not provide any kind of benefit in order to the calculation of the number of open doors. This approach only shows some similar concepts that can be introduced 'to talk about' this problem.

But the temptation to look out for more questions - rather than answers - is impossible to avoid.

Inrandomtan made his code to print out the values for M(n) at periodical values of n and observed that this function , M(n), oscillates between negative and positive values a kind of erratically, and obviously constructed the following conjecture:

LI-Conjecture: M(n) is zero infinitely often

Can you say something about this conjecture?

***

Jean Brette also reminds a slight link of this puzzle and conjectures with the now beaten Pólya Conjecture.

***