3

Introduction

Found the following interesting problem and made attempt in solving it. While there are some already existing posts describing quite analogical problem on MathStack Exchange platform (no duplication of already existing post):

however I am fond of constructing rigorous solution in so-called "full glory of details" (i.e. with all intermediate steps shown). The point is that the replies attached to the above mentioned posts provide just outlines of solution. I would like to provide a detailed solution. This is going to differentiate between other posts related to similar, but not exaclty the same problem. This is the main motivation of establishment of new post from my side.

Description

There are $1,000$ light bulbs numbered from $1$ to $1000$. A switching mechanism changes state of some bulbs (from “on” to “off” and vice versa). If the switch is pressed for the $k$-th time, all bulbs, whose indices are divisible by $k$, change their states. At the beginning of experiment, all bulbs are off.

The experiment is initiated:

  • After pressing the switch for the 1st time ($k = 1$), all bulbs are “on.”

  • After pressing the switch for the 2nd time ($k = 2$), all bulbs with even indices are “off” and all bulbs with odd indices remain “on.”

  • After pressing the switch for the 3rd time ($k = 3$), all odd bulbs not divisible by 3, and all even bulbs divisible by 3 are “on”. Other bulbs are “off.”

  • etc.

The switching occured $1000$ times.

Which bulbs were “on” at this stage?

My extended attempt

Let $n \in [0, 1000] \cap \mathbb{N}$. Let $M_{2 \times 1000}(\mathbb{N})$ be a set of matrices having $2$ rows and $1000$ columns in which every entry is a natural number.

Let $A_{n} \in M_{2 \times 1000}(\mathbb{N})$ be a matrix representing encoded states of light bulbs in analysed network after $n$-th switch pressing. Let $A_{n}$ be represented in the following way:

  • $1$st row represents numbers of indices of light bulbs
  • $2$nd row represents states of light bulbs in the form of either $1$ (switched on) or $0$ (switched off).

The analysis of initial states yields the following conclusions:

    1. light bulb with index whose number has odd number of natural factors (including number $1$ and itself) has $1$ (switched on) as final state
    1. light bulb with index whose number has even number of natural factors (including number $1$ and itself) has $0$ (switched off) as final state
    1. Let $k \in \{ 1, \dots, 1000 \}$. Let $m \in \mathbb{N}$. Let $b_{k}^{m} \in \mathbb{Z}_{2}$ be a state of light bulb with index number $k$ after $m$-th switch pressing operation. Then $$ b_{k}^{m} = \big\lvert \{ l \in \mathbb{N} : l \leq m \land l|k \} \big\rvert \; (mod \; 2) $$

In other words, the state of light bulb with index $k$ after $m$-th switch pressing operation is equal to number of all natural divisors of $k$ that do not exceed value of $m$ and to this number is applied modulo $2$ operator.

    1. Let $S_{1000} \in \mathbb{N}$ be a number of light bulbs in analysed network that after $1000$-th switching press operation are switched on. Then $$ S_{1000} = \sum\limits_{k=1}^{1000}b_{k}^{1000} $$

It is required to inspect all natural divisors of every natural number from $1$ to $1000$ individually and apply formula derived in point (3). In this case there is a need of utilisation of computational power to do verifications for each considered natural number. The reason is a lack of explicit pattern of distribution of prime numbers. Hence, it is required to do verification for every natural number from $1$ up to $1000$ individually for each natural number.

For the above mentioned repetitive computations we use some programming stuff. The implementation of the above conclusions generates number 31.

For the above mentioned repetitive computations we use the following code snippet:

def get_number_of_natural_factors(input_number: int) -> int:
                # each natural number is divisible by 1
                # hence counter should start with 1
                number_of_natural_divisors = 1
                exclusive_upper_boundary = input_number + 1

            for potential_divisor in range(2, exclusive_upper_boundary, 1):
                if input_number % potential_divisor == 0:
                    number_of_natural_divisors += 1

            return number_of_natural_divisors

                    def number_of_operating_light_bulbs(input_number_of_light_bulbs: int) -> int:
            list_of_number_of_divisors_modulo_2 
                = [get_number_of_natural_factors(input_number=index) % 2 \
                    for index in range(1, input_number_of_light_bulbs + 1)]

            initial_index = 0
            exclusive_index = 1000

            for index in range(initial_index, exclusive_index):
                if list_of_number_of_divisors_modulo_2[index] == 1:
                    # index + 1 yields value of index of light bulb
                    index_with_odd_number_of_divisors = index + 1

                    print(index_with_odd_number_of_divisors)        

            return sum(list_of_number_of_divisors_modulo_2)

The inclusion of the following code snippet

print(get_number_of_operating_light_bulbs(input_number_of_light_bulbs=1000))

prints number 31 and the following numbers:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961.

Hence, after $1000$-th switch pressing operation there are $31$ light bulbs that are switched on.

Question

Do you think that my solution is fully explicit?

Hope this content will enrich MathStack Exchange platform further!

some_user
  • 43
  • 1
    The natural numbers with an odd number of divisors are precisely the perfect squares. – lulu Jun 18 '23 at 09:13
  • @lulu thanks for stating this post that I found before making this post. However, after analysis of its content I concluded that this was not exactly what I was looking for. I stated explicitly that my research done on the platform implied no posts related to the submitted problem. – some_user Jun 18 '23 at 10:01
  • How is it not what you are looking for? For any $N$ you just need to count the squares up to $N$ and that's just $\lfloor \sqrt N \rfloor$. Minimal computation needed. – lulu Jun 18 '23 at 10:07
  • $lulu there is a subtle difference in terms of initial configuration of light bulbs in the post stated by You. In terms of more constructive analytical suggestion, the user @barak manos provided in this post https://math.stackexchange.com/questions/2017047/the-locker-problem-why-squares It is worth to mention it for a completenss of a content of this post. – some_user Jun 18 '23 at 10:18

1 Answers1

3

This is a classic problem that can be solved by hand. If a number $n$ is not a square, you can pair up each divisor $d$ that is less than $\sqrt n$ with the corresponding divisor $\frac nd$ that is (necessarily) greater than $\sqrt n$. Thus, if $n$ is not a square, it has an even number of divisors, exactly half of which are less than $\sqrt n$.

If $n$ is a square, you can repeat the same process with every divisor except for $\sqrt n$, which corresponds to itself. Thus, if $n$ is a square, it has an odd number of divisors.

Your algorithm toggles light bulb $n$ at every step $d$ where $d \mid n$. Thus, light bulb $n$ is on at the end of the process exactly when $n$ has an odd number of divisors, which occurs exactly when $n$ is a square. Since $\lfloor \sqrt {1000} \rfloor=31$, when you're done, $31$ of the light bulbs are on.

Robert Shore
  • 23,332