php riddle - interesting result

Question

I have the following code:

<?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}, ";
    }
}

?>

As you can see, I fill up an array with 500 zeroes, loop through it twice, and then print out the cup numbers that have a '1' in them:

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

As you can see - it outputs squares. I think the phenomenon is impressive, but I am interested in a mathematical explanation -

Why does this pattern occur?

Thanks!

Answer 1

Well you are flipping the state once for each unique factor.

Squares have an odd number of unique factors.

Answer 2

It works this way because this is the classic Locker Problem... and in the locker problem, only the numbers with odd number of factors are returned... which are all the squares.

Answer 3

I put sort of a play by play in the comments:

<?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}, ";
    }


}

Basically what you are creating is a list of numbers with odd factors, which are squares.

Notice how each value is incremented in a sequence of value + 2:

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

and so on.

I'm sure someone will explain it much more accurately and succinct than I did, but this gives you some idea of what's going on here.