# 4k reputation special: “I hate square numbers!”

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!

• You should add the no-computers tag, because it can be solved with a 3-line program or an excel sheet. – Florian F Jun 29 '20 at 12:41
• @FlorianF I was planning to add this but forgot! – Culver Kwan Jun 29 '20 at 12:47
• Can you dress this abstract puzzle in a happier story, please?Sorry but the joke cruelty is honestly a bit sickening for me – Laska Jun 30 '20 at 2:34

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.

• I don't believe that you repeated $f(x) = x - \lfloor \sqrt{x} \rfloor$ until the result is less than 1000 without computers. – the default. Jun 29 '20 at 13:01

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 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 ("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$$.

• Ah, you've shamed me into fixing it. Hang on a second. [EDITED to add:] Now done. – Gareth McCaughan Jun 29 '20 at 20:36
• I must say, Gareth McCaughan, 1) Your creating the $(m,k)$ landscape by combining pairs of consecutive iterations is like pulling a rabbit out of a hat. What a brilliant 1-D-to-2-D "mapping" in so many senses of the word! 2) Keeping the treasure map spoilered hides too much of a good thing; could you be unshamed into baring it? Your solution would not be given away. I've never seen something so number theoretic evoke such balanced rhythmic intricacy, like some excellent music. – humn Jul 2 '20 at 6:29
• I'm glad you like the diagram, but I fear that unspoilering it might give too much away. Imagine, for instance, a reader who gets a sentence or so in and thinks "oh, I hadn't thought of using the (m,k) representation; let me think about it some more" -- seeing the diagram might short-circuit some of that thinking. – Gareth McCaughan Jul 2 '20 at 9:13
• If you are a fan of number theory, squares, and elegant visual thingies, though, I warmly commend to you the video at youtube.com/watch?v=DjI1NICfjOk which contains an elegant visual thingy at least two orders of magnitude cleverer than mine. [EDITED to add:] It has nothing else to do with the puzzle here; it just seems like a thing you might appreciate. – Gareth McCaughan Jul 2 '20 at 9:14
• Thank you for the windmill squares video link, Gareth McCaughan. The staggered symmetries at 16:46 are indeed astoundingly clever to the point of magical. So squares bring out the most handsome in number theory? Still, your diagram transforms into an entirely non-square landscape and actually makes me feel like dancing with its dynamic combination of rhythm, shimmies and leaps. (And, okay okay, i suppose someone could recognize how its overall shape derives from squares.) – humn Jul 2 '20 at 14:44

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$$