A question about squares

Question

The numbers from 1 to $ 2013^2 $ are written row by row into a table consisting of $ 2013 \times 2013 $ cells. Afterwards, all columns and all rows containing at least one of the perfect squares $ 1, 4, 9, \cdots, 2013^2 $ are simultaneously deleted. How many cells remain? I checked this operation replacing $2013$ by smaller numbers, and if my arithmetic is not wrong it came out to be the number of quadratic non-residues $\mod n$. Is it true? Anyways what would be the number of remaining cells?

Answer 1

I don't have the reputation to comment yet, so I have to post it as an answer, although it is not really an answer.

Did you check for n=3 ? Unless I have mistaken you in some way I get 0 remaining cells:

1 2 3

4 5 6

7 8 9

All rows are removed and no cells are remaining. But 3 has the quadratic non-redesidue 2.

I also checked n=11 and got 10 remaining cells. But we only have 5 non-residues mod 11.

While writing this text I noticed something that is certainly true: The number of remaining columns is in fact the number of non-residues. This is easy to prove, since every column has integers in it that are congruent modulo n.

So the number of remaining cells is certainly a multiple of the number of non-residues.

Edit: With a computer search I got 503 remaining rows and 1641 remaining columns which gives a whooping 825423 remaining cells.

Edit2: I think I answered what you asked:

1. For arbitary n, are the number of remaining cells the number of quad. non-res.? No, but a multiple thereof. (Short proof: Every column represents a equivalentclass mod n and is removed iif there is a square in it.)
2. How many cells are left if n=2013? Computer search says 825423. You get the columns by calculating the quad. non-residues. You get the rows by finding all rows that don't contain a square (Loop through i=1..2013 and "delete" the row which has the number $\frac{i^2-1}{2013}$ (Integer division)). I don't see how it would be possible to calculate the rows in another way but bruteforce. Althoug you can make some small improvements on the algorithm, I can't think of a way to find a closed form.

Edit3:Ok, I somehow skipped your last sentence. But barto said, the number of remaining columns are the non residues and the number of rows is the formula Ivan Loh provided. So your question is answered.