Throwing Number

Lemma 1 : Given the sequence with initial elements $1, 2, 3, \ldots, k, n, \ldots$ (the numbers 1 to $k$ in order, then some number $n$ , then the rest of the sequence), after $2^k - 1$ moves the sequence becomes $n, 1, 2, 3, \ldots, k, \ldots$ (the number $n$ moves to the front of the sequence).

The proof is by induction on $k$ . With $k = 1$ , this is trivial: the sequence is $1, n, \ldots$ , and a single move brings it to $n, 1, \ldots$ .

Now, suppose that we have proven the claim for $k = k'$ , and we'd like to prove the claim for $k = k' + 1$ .

• The sequence starts $1, 2, 3, \ldots, k', k' + 1, n, \ldots$ .
• By induction hypothesis, after $2^{k'} - 1$ moves, the sequence becomes $k' + 1, 1, 2, 3, \ldots, k', n, \ldots$ .
• After one more move, the sequence becomes $1, 2, 3, \ldots, k', n, k' + 1, \ldots$ .
• By induction hypothesis, after $2^{k'} - 1$ more moves, the sequence becomes $n, 1, 2, 3, \ldots, k', k' + 1, \ldots$ .

Thus in total, that's $2^{k' + 1} - 1$ moves, proving the claim for $k = k' + 1$ . Thus by induction, the lemma is proven.

---

Lemma 2 : A number $n$ will be the first element of the sequence after $2^{n-1} - 1$ moves and not earlier.

Showing that $n$ is the first element after $2^{n-1} - 1$ moves is easy; using Lemma 1 with $k = n-1$ and original sequence $1, 2, 3, \ldots, n-1, n, \ldots$ , after $2^{n-1} - 1$ moves we obtain the sequence $n, 1, 2, 3, \ldots, n-1, \ldots$ . The problem is now to prove that we cannot get $n$ to the first element any time earlier.

To show this, we will prove again by induction on $n$ . For $n = 1, 2$ , this is trivial. ( $n = 1$ is the starting sequence, so that's 0 moves; $n = 2$ needs only one move.) Now, suppose we have proven the claim for $n \le n'$ , and we want to prove the claim for $n = n' + 1$ .

To move $n' + 1$ to the front of the sequence, there are $n'$ phases: moving it to the $n'$ -th element of the sequence, moving it (from the $n'$ -th element of the sequence) to the $(n' - 1)$ -th element of the sequence, and so on, until the last phase being moving it (from the second element of the sequence) to the first element of the sequence. We claim that moving $n'+1$ from the $(k+1)$ -th element to the $k$ -th element of the sequence:

• starts with the sequence $1, 2, 3, \ldots, k-1, k, n'+1, k+1, k+2, \ldots, n', \ldots$ ,
• ends with the sequence $1, 2, 3, \ldots, k-1, n'+1, k, k+1, k+2, \ldots, n', \ldots$ , and
• takes $2^{k-1}$ moves.

We prove this by induction on $k$ , from $k = n'$ down to $k = 1$ .

For the base case $k = n'$ , the sequence clearly starts as $1, 2, 3, \ldots, n', n'+1, \ldots$ , so the first part of the claim is satisfied.

Now, the only way to bring $n'+1$ down is if the front of the sequence is at least $n'$ . (Anything less and its destination is still in front of the $(n'+1)$ -th element, so it will not move $n'+1$ down.) But the only such number in front of $n'+1$ is $n'$ , and we clearly cannot use any number behind $n'+1$ (if $n'+1$ doesn't move, then neither does any number behind it). Thus we need to first bring $n'$ to the front of the sequence, then make a move to bring it behind $n'+1$ . By inductive hypothesis (the one on $n$ ), bringing $n'$ to the front takes at least $2^{n'-1} - 1$ moves. And we know that after $2^{n'-1} - 1$ moves, the sequence will look like $n', 1, 2, \ldots, n'-1, n'+1, \ldots$ . Making one more move makes it $1, 2, \ldots, n'-1, n'+1, n', \ldots$ , which proves both the second and the third parts of the claim.

Now suppose that we have proven the case $k = k'+1$ , and we'd like to prove the case $k = k'$ .

The first part follows immediately from the second part of the inductive hypothesis. By using essentially the same reasoning as above, the only way to bring $n'+1$ down from $(k'+1)$ -th element to $k'$ -th element is to bring $k'$ to the front of the sequence, and then making a move; this takes $2^{k'-1}$ moves and sets up the sequence correctly, proving both the second and the third parts of the claim. This completes the induction (on $k$ ).

Now, using the third part of the claim for $k = n', n'-1, \ldots, 1$ , it takes at least $2^{n'-1} + 2^{n'-2} + \ldots + 2^0 = 2^{n'} - 1$ moves to bring $n'+1$ to the front of the sequence. This proves Lemma 2 for $n = n'+1$ , and by induction, for all $n$ .

---

With Lemma 2, we can now easily compute the answer. We're invoking Lemma 2 for $n = 1000$ , which means it takes $2^{999} - 1$ moves. Since the first sequence is numbered sequence 1, the first sequence where 1000 is at the front of the sequence will be sequence number $2^{999}$ . By simple modular arithmetic, we can compute the answer to be $\boxed{688}$ .

We can actually obtain the answer without using computer. We're looking for $2^{999} \mod 1000$ . By Chinese Remainder Theorem, it suffices to compute $2^{999} \mod 8$ and $2^{999} \mod 125$ . The former is clearly 0 because $8 = 2^3$ divides $2^{999}$ . The latter can be computed using Fermat's Little Theorem; we know $\varphi(125) = 100$ , so $2^{100} \equiv 1 \pmod{125}$ , and so $2^{1000} \equiv (2^{100})^{10} \equiv 1 \pmod{125}$ . And $2^{-1} \equiv 63 \pmod{125}$ (special case of $2^{-1} \equiv k+1 \pmod{2k+1}$ ), so $2^{999} \equiv 2^{1000} \cdot 2^{-1} \equiv 63 \pmod{125}$ . Combining the two together gives $2^{999} \equiv 688 \pmod{1000}$ (by checking numbers in the form $125k+63$ and finding which one is a multiple of 8).