Почему этот математический образец происходит здесь?

Question

Фактический вопрос идет как этот

Комната имеет N (от 1 до N включительно) луковиц и N переключателей. N людей идут один за другим. 1-й человек отправляется в и не переключает ни один из переключателей. 2-й человек входит и переключает все переключателей, кроме кратных 2 (2, 4, 6 ...). 3-й человек отправляется в и переключает все переключатели, отличные от кратных 3 (3, 6, 9 ...), и поэтому (до N-го человека переключает все переключатели, кроме N-го переключателя). Как только процесс завершен, сколько ламп находится в состоянии «включено». (Предположим, что все луковицы сначала находятся в состоянии «выключено»).

оригинальный вопрос можно найти here

Я попытался решить ее, написав грубую силу решателя первым, но это дало бы мне «максимальное время превышены» приговор, потому что 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) 

Answer 1

Это версией 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 один раз для каждого фактора, он меняет состояния.

Вы упомянули число 1s между 0s. (n + 1)^2-n^2 = 2n + 1. Итак, вы видите 2, 4, 6, 8 и т. Д. 1s между 0s для N нечетных.

Answer 2

Douglas Zare уже объяснил отношение к более старой проблеме, поэтому я просто подробно расскажу о решении старой проблемы, последовательность которой в любом случае появляется на вашем изображении.

Я предполагаю, что переключатели изначально выключены (0), но рассуждения одинаковы независимо.Первый человек оставляет их всех. Второй человек включает 2 4 6 .... Тот, который будет , очевидно, остался без них 2, потому что в соответствии с правилами проблемы он никогда не будет переключен снова.

Затем третий человек переключает 3 6 9 .... Опять же, очевидно3 останется на.

Затем четвертый человек переключает 4 8 12 .... Очевидно,4 останется навсегда (он был включен вторым парнем).

Теперь мы можем сказать (это может быть более очевидно, если вы подходите к девятому парню), что идеальные квадраты всегда будут выключены, а остальное всегда будет включено. Эти заявления требуют объяснений:

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: есть sqrt(n) совершенные квадраты ниже n, и это 1, 2, ..., sqrt(n) - 1, sqrt(n).