4k reputation special: "I hate square numbers!"

Question

There is a large prison, with exactly 4000 prisoners. The warden noticed that there were too many prisoners, so they lined up all the prisoners, and repeated the following procedure until less than 1000 prisoners were left.

For every prisoner standing, they gave a number to the prisoner, starting from the number 1 to the first prisoner. Every prisoner holding a square number will be executed, then the remaining prisoners are lined up again.

So, how many prisoners were not executed?

This 4k rep special problem is not that hard. Please give it your best to solve this puzzle!

Answer 1

For each cycle, the number of prisoners executed is exactly

$\lfloor \sqrt{N} \rfloor$, where $N$ is the number of prisoners.
Repeating $f(x) = x - \lfloor \sqrt{x} \rfloor$ until the result is less than $1000$ gives $992$ prisoners remaining.

A more mathematical approach:

We have that $4000 = 63^2+31$. Let's see what happens to a number of this form:
$x^2+31 \rightarrow x^2+31-x = (x-1)^2+30+x \rightarrow (x-1)^2+30+x-(x-1) = (x-1)^2+31$
Clearly, as long as $x$ is strictly greater than $31$ - so that we subtract $x-1$ at the next iteration - we will continue having numbers of the desired form, and in particular after some number of cycles we will see $32^2+31$.
This number is $1055$, and the next two cycles give us $1024$ and $992$, the latter of which is the first such number less than 1000.

Answer 2

A general [no-computers] solution:

First of all:

We are starting with 4000 and repeatedly replacing $n$ with $n-\lfloor\sqrt n\rfloor$. That is, if $n=m^2+k$ where $0\leq k\leq2m$ then we are subtracting $m$. Two cases: if $k<m$ then write our new number as $m^2-m+k=(m-1)^2+m-1+k$; if we repeat the procedure then we will have $(m-1)^2+k$ -- that is, doing our operation twice reduces $m$ by 1 and leaves $k$ unaltered. Alternatively, if $k\geq m$ then our new number is $m^2+k-m$ and repeating the procedure gives us $m^2-2m+k=(m-1)^2+k-1$ -- that is, doing our operation twice reduces $m$ by 1 and also reduces $k$ by 1. Note that in both cases we still have $k\leq2m$ after our two reduction steps except maybe in the latter case if $k=2m$ exactly. In that case, what happens is that we go $m^2+2m\rightarrow m^2+m\rightarrow m$ and instead of $(m-1,k-1)$ we have $(m,0)$.

To summarize:

If $0\leq k<m$ ("small $k$") then two iterations replace $(m,k)$ with $(m-1,k)$.
If $m\leq k<2m$ ("large $k$") then two iterations replace $(m,k)$ with $(m-1,k-1)$.
And if $k=2m$ ("maximal $k$") then two iterations replace $(m,k)$ with $(m,0)$.

Let's now consider iterating this.

If we start with "small $k$" then we can do $m-k$ small-$k$ steps, after which we have $(k,k)$ and we move to "large $k$" (or "maximal $k$" if $k=0$ but then we also have $n=0$ and are finished). The remaining large-$k$ iterations will take us cleanly down to $(0,0)$.
If we start with "large $k$" then we can do $2m-k$ large-$k$ steps, after which we have $(k-m,2(k-m))$, do one "maximal $k$ step, and are at $(k-m,0)$ and move to "small $k$". The remaining small-$k$ iterations will take us cleanly down to $(0,0)$.

The following diagram may help to illustrate what happens:

Here, two of the original iterations take one step along a red or green arrow, or jump all the way from tail to head of a blue one. So, if we start in red territory then we walk north until we cross the region boundary, then we walk northwest until we reach (0,0); if we start in green territory then we walk northwest until we reach the diagonal, then hop to the left edge and walk north to (0,0).

Let's now apply this to the present case.

We start at $4000=63^2+31$; that is, at $(63,31)$. This is a small-$k$ case. We take 32 small-$k$ steps down to $(31,31)=992$. The question asked about what happens up to when there are $<1000$ prisoners. Obviously the round of executions leading to 992 (half of one of our "steps") started above 1000, since at this point each round is killing 30ish prisoners. So we stop at 992, and the number of people executed is $4000-992=3008$.

Answer 3

A quick and dirty approach, slightly different to the ones given. Again, [no-computers].

We are interested in the difference between consecutive squares. Note that: $$ a^2 \: \to \: \text{add }2a+1 \: \to \: (a+1)^2$$ Roughly, any number's square root is half as large as the distance to the next square (above or below). This is accurate enough that we need no further observation about square roots for the rest of the problem.

This means that each integer square root will occur twice. Checking the first two manually, the number of people shot in each round is: $$63,62,62,61,61,60,60,...$$ It is not difficult to check that the roots will be roughly size $31$ when we reach 1000 prisoners, which turns out to be a lucky guess: $$\text{prisoners left} = 4000 - 63 - 2\sum_{n=32}^{62} n - 31 =992$$