为什么这里会出现这种数学模式？
Why does this mathematical pattern occurs here?
实际问题是这样的
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).
可以找到原题here
我试着先写一个强力求解器来解决它，但它会给我一个 "time limit exceeded" 的结论，因为 N 可以大到 10E9，
在测试某些 N 值的解决方案时，我偶然发现了导致最终解决方案的模式
最好用图解释，观察1被0隔开的个数- 2 , 4 , 6 , 8 ...
但我还是想不通为什么会存在这种模式？换句话说，这种模式背后的数学原因是什么？
这是我使用的绘制(N)代码
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)
这是 old puzzle 的一个版本。通常的版本是让第 n 个人翻转数字可被 n 整除的开关，并产生相同的方块图案（方块索引为 1、4、9、16 的开关被切换），无论 N 是偶数还是奇数。在这里，恰好相反的开关被切换，这相当于将所有开关额外切换 N 次，如果 N 是偶数则什么都不做，而当 N 是奇数时反转它们。您只展示了 N 为奇数的情况，这意味着方块是不改变状态的开关。
一个数字的因子成对出现，除了当数字是正方形时，因为我们可以将因子 x 与 n/x 配对，并且除了 x^2=n 时，它们是不同的。
例如，18 有 6 个因数：1 和 18、2 和 9 以及 3 和 6。因此，如果您为每个因数拨动开关 18 一次，它会保持其原始状态。
100 有 9 个因子：1 和 100、2 和 50、4 和 25、5 和 20，以及 sqrt(100)=10。因此，如果您为每个因素切换开关 100 一次，它会改变状态。
您提到了 0 之间 1 的数量。 (n+1)^2-n^2 = 2n+1。因此，对于 N 奇数，您会看到 0 之间的 2、4、6、8 等 1。
Douglas Zare 已经解释了与旧问题的关系，所以我将详细说明旧问题的解决方案，无论如何它的序列都会显示在您的图像中。
我假设开关最初是关闭的 (0)，但不管怎样，推理都是一样的。第一个人离开了他们。第二个人开启2 4 6 ...。 显然 留在其中的那个是 2，因为根据问题的规则，它永远不会再次切换。
然后第三人称切换3 6 9 ...。同样，显然 3 将继续存在。
然后第四个人切换4 8 12 ...。 显然 4 将永远关闭（由第二个人打开）。
现在我们可以看出（如果你走到第 9 个人，可能会更明显）完全正方形将始终关闭，而其余部分将始终打开。这些陈述需要解释：
1.完美的正方形将永远关闭
一个完美的正方形有奇数个因子：
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
通过number of divisors公式。
由于每个数字都由其除数切换，因此完美正方形将始终处于初始状态，因为它们的除数为奇数。
2。不是完全正方形的数字将始终显示
这是因为只有完全平方数的除数是奇数，所以其他数总是与初始状态相反。
假设一个非完全平方有奇数个除数。那么：
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.
然后该问题的有效解决方案涉及找到n下方有多少个完美的正方形：n下方有sqrt(n)个完美的正方形，这些是1, 2, ..., sqrt(n) - 1, sqrt(n) .
实际问题是这样的
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).
可以找到原题here
我试着先写一个强力求解器来解决它，但它会给我一个 "time limit exceeded" 的结论，因为 N 可以大到 10E9，
在测试某些 N 值的解决方案时，我偶然发现了导致最终解决方案的模式
最好用图解释，观察1被0隔开的个数- 2 , 4 , 6 , 8 ...
但我还是想不通为什么会存在这种模式？换句话说，这种模式背后的数学原因是什么？
这是我使用的绘制(N)代码
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)
这是 old puzzle 的一个版本。通常的版本是让第 n 个人翻转数字可被 n 整除的开关，并产生相同的方块图案（方块索引为 1、4、9、16 的开关被切换），无论 N 是偶数还是奇数。在这里，恰好相反的开关被切换，这相当于将所有开关额外切换 N 次，如果 N 是偶数则什么都不做，而当 N 是奇数时反转它们。您只展示了 N 为奇数的情况，这意味着方块是不改变状态的开关。
一个数字的因子成对出现，除了当数字是正方形时，因为我们可以将因子 x 与 n/x 配对，并且除了 x^2=n 时，它们是不同的。
例如，18 有 6 个因数：1 和 18、2 和 9 以及 3 和 6。因此，如果您为每个因数拨动开关 18 一次，它会保持其原始状态。
100 有 9 个因子：1 和 100、2 和 50、4 和 25、5 和 20，以及 sqrt(100)=10。因此，如果您为每个因素切换开关 100 一次，它会改变状态。
您提到了 0 之间 1 的数量。 (n+1)^2-n^2 = 2n+1。因此，对于 N 奇数，您会看到 0 之间的 2、4、6、8 等 1。
Douglas Zare 已经解释了与旧问题的关系，所以我将详细说明旧问题的解决方案，无论如何它的序列都会显示在您的图像中。
我假设开关最初是关闭的 (0)，但不管怎样，推理都是一样的。第一个人离开了他们。第二个人开启2 4 6 ...。 显然 留在其中的那个是 2，因为根据问题的规则，它永远不会再次切换。
然后第三人称切换3 6 9 ...。同样，显然 3 将继续存在。
然后第四个人切换4 8 12 ...。 显然 4 将永远关闭（由第二个人打开）。
现在我们可以看出（如果你走到第 9 个人，可能会更明显）完全正方形将始终关闭，而其余部分将始终打开。这些陈述需要解释：
1.完美的正方形将永远关闭
一个完美的正方形有奇数个因子：
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
通过number of divisors公式。
由于每个数字都由其除数切换，因此完美正方形将始终处于初始状态，因为它们的除数为奇数。
2。不是完全正方形的数字将始终显示
这是因为只有完全平方数的除数是奇数，所以其他数总是与初始状态相反。
假设一个非完全平方有奇数个除数。那么：
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.
然后该问题的有效解决方案涉及找到n下方有多少个完美的正方形：n下方有sqrt(n)个完美的正方形，这些是1, 2, ..., sqrt(n) - 1, sqrt(n) .