PHP загадка - интересный результат

Question

У меня есть следующий код:

<?php

$cups = array();
for($i=0; $i<500; $i++){
    $cups[$i] = 0;
}

for($x=1; $x<500; $x++){
    for($y=$x; $y<500; $y+=$x){
        $cups[$y] = !$cups[$y];
    }
}

foreach($cups as $key => $value){
    if($value == 1){
        echo "{$key}, ";
    }
}

?>

Как видите, я заполняю массив 500 нулями, перебираю его дважды, а затем распечатываю числа кубков, в которых есть «1»:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484,

Как видите - выводит квадраты. Я думаю, что это явление впечатляет, но меня интересует математическое объяснение -

Почему происходит эта картина?

Спасибо!

Answer 1

Это работает так, потому что это классическая проблема с блокировщиком ... и в задаче с блокировщиком возвращаются только числа с нечетным числом факторов ... все это квадраты.

Answer 2

Хорошо, вы переключаете состояние один раз для каждого уникального фактора.

Квадраты имеют нечетное количество уникальных факторов.

Answer 3

Я поставил своего рода игру по пьесе в комментариях:

<?php

$cups = array();
for($i=0; $i<500; $i++){
    $cups[$i] = 0;
}
// fill up indices 1-500

// at this step you set up the loop, and increment x
for($x=1; $x<500; $x++){
// since $x is now 2, you are actually looping from 2 to 500, and
// adding 2 to every iteration of $y
    for($y=$x; $y<500; $y+=$x){
 // now you're only showing a value if theyre not the same
    $cups[$y] = !$cups[$y];
    }
}

foreach($cups as $key => $value){
    // here you only loop through those with a value (which is every value + 2) 
    // you are basically counting by 2s (2, 4, 
    if($value == 1){
        echo "{$key}, ";
    }


}

По сути, вы создаете список чисел с нечетными коэффициентами, которые являются квадратами.

Обратите внимание, как каждое значение увеличивается в последовательности значений + 2:

1  + 3 = 4
4  + 5 = 9
9  + 7 = 16
16 + 9 = 25

и так далее.

Я уверен, что кто-то объяснит это гораздо точнее и лаконичнее, чем я, но это дает вам некоторое представление о том, что здесь происходит.