Tougher Throwing Numbers

Of course there's the boring solution:

1
2
3
4
5
6
7
8

array = list(range(1, 25)) # I'm not sure how large the sequence should be; let's just put 1,2,...,24
moves = 0
while array[0] != 20:
    k = array[1]
    array = array[1:k+1] + [array[0]] + array[k+1:] # Throw array[0] to after the (k+1)-th term
    moves += 1
print(moves)
# Prints 524269

But it's boring. Besides, what if I ask the number of throws required to bring $2016^{2016}$ to the front of the sequence?

Let's solve this without coding at all.

Lemma 1 : Given a sequence with initial terms $1, 2, 3, \ldots, k-1, k, a, t_{k+2}, t_{k+3}, \ldots, t_{a+1}, \ldots$ , after $2^k - 1$ moves, the sequence will look like $1, 2, 3, \ldots, k-1, a, t_{k+2}, t_{k+3}, \ldots, t_{a+1}, k, \ldots$ . In other words, $k$ is moved to the back of the $(a+1)$ -th term.

The proof is by induction on $k$ . (Note that $a$ doesn't matter.) The base case $k = 1$ is trivial: the sequence looks like $1, a, \ldots$ , so a single move throws the 1 to the back of the $(a+1)$ -th element. Suppose we have proven the claim for $k \le k'$ , and we want to prove the claim for $k = k'+1$ .

Consider the sequence $1, 2, 3, \ldots, k'-2, k'-1, k', k'+1, a, t_{k+2}, \ldots$ . By inductive hypothesis with $k \gets k', a \gets k'+1$ , after $2^{k'} - 1$ moves the sequence will look like $1, 2, 3, \ldots, k'-2, k'-1, k'+1, a, k', t_{k+2}, \ldots$ . Invoking it again now with $k \gets k'-1, a \gets k'+1$ , after $2^{k'-1} - 1$ moves the sequence becomes $1, 2, 3, \ldots, k'-2, k'+1, a, k', k'-1, t_{k+2}, \ldots$ . We can keep going, invoking the inductive hypothesis for $k \gets k', k'-1, k'-2, \ldots, 1$ and $a \gets k'+1$ in turn, so that after $(2^{k'} - 1) + (2^{k'-1} - 1) + \ldots + (2^1 - 1) = 2^{k'+1} - k' - 2$ moves, the sequence looks like $k'+1, a, k', k'-1, k'-2, \ldots, 1, t_{k+2}, \ldots$ .

Now, a single move throws $k'+1$ to the back of the $(a+1)$ -th term. But we still have the front of the sequence looking like $a, k', k'-1, k'-2, \ldots, 1, t_{k+2}, \ldots$ . So, we apply $k'$ more moves; the first sets $a$ to be the $(k'+1)$ -th term, the second sets $k'$ to be the $k'$ -th term, the third sets $k'-1$ to be the $(k'-1)$ -th term, and so on, until the last move sets 2 to be the second term; now the 1 is also the first term. The sequence now looks $1, 2, 3, \ldots, k', a, t_{k+2}, \ldots, t_{a+1}, k'+1, \ldots$ . That's a total of $(2^{k'+1} - k' - 2) + 1 + k' = 2^{k'+1} - 1$ moves, proving the claim for $k = k'+1$ . By induction, the claim is proven for all $k$ .

Lemma 2 : Given a sequence with initial terms $1, 2, 3, \ldots, k-1, a, b, t_{k+2}, t_{k+3}, \ldots, t_{a+1}, \ldots$ , it takes $2^{k-1} - (k-1)$ moves to bring $b$ to the $k$ -th position, and the resulting sequence is $a, k-2, k-3, \ldots, 1, b, t_{k+2}, t_{k+3}, \ldots, t_{a+1}, k-1, \ldots$ .

Proving that $2^{k-1} - (k-1)$ moves is enough is easy. We invoke Lemma 1 with $k \gets k-2, k-1, \ldots, 1$ in order and $a \gets k-1$ (this is also part of the proof in Lemma 1). We obtain the sequence $k-1, a, k-2, k-3, \ldots, 1, b, \ldots$ . One additional move throws $k-1$ to after the $(a+1)$ -th element; since $a \ge k$ , this is after $b$ , thus showing that we manage to bring $b$ to the $k$ -th position. It takes $(2^{k-2} - 1) + (2^{k-3} - 1) + \ldots + (2^1 - 1) + 1 = 2^{k-1} - (k-1)$ moves to do so.

Proving it is necessary is harder. We prove this by induction on $k$ . For $k = 2$ , this is trivial; the sequence looks like $1, a, b, t_4, t_5, \ldots, t_{a+1}, \ldots$ , and a single move makes it $a, b, t_4, t_5, \ldots, t_{a+1}, 1, \ldots$ , proving both parts of the claim at once. Suppose we have proven the claim for $k < k'$ , and we want to prove the claim for $k = k'$ .

The only way we can bring $b$ down to $k'$ -th position is if we throw something behind it. This means, we need to make the second element to be $k'$ or greater (since $b$ is in the $k'+1$ -th position). However, this element must also be found in front of $b$ ; if it is behind $b$ , then to bring it down, we also need to bring $b$ down, and thus it is circular logic. The only element in front of $b$ that is at least $k'$ is $a$ . Thus we need to bring $a$ to the second position.

By inductive hypothesis on $k \gets k'-2, a \gets k'-1, b \gets a$ , we obtain the sequence $k'-1, k'-3, k'-4, k'-5, \ldots, 1, a, k'-2, b, \ldots$ after $2^{k'-2} - (k'-2)$ moves. Doing $k'-3$ additional moves, the sequence is "fixed", making $1, 2, 3, \ldots, k'-4, k'-3, k'-1, a, k'-2, b, \ldots$ . This is a total of $2^{k'-2} - 1$ moves required. (Note that Lemma 1 says this is the sequence is the result after $2^{k'-2} - 1$ moves, but doesn't say whether we can reach it earlier.) We repeat this with $k \gets k'-3, a \gets k'-1, b \gets a$ ; this is $2^{k'-3} - 1$ additional moves to make it $1, 2, 3, \ldots, k'-4, k'-1, a, k'-2, k'-3, b, \ldots$ . Once again, we do this for $k \gets k'-2, k'-3, \ldots, 1$ in order, $a \gets k'-1, b \gets a$ ; this leads to the sequence $k'-1, a, k'-2, k'-3, \ldots, 1, b, \ldots$ in $(2^{k'-2} - 1) + (2^{k'-3} - 1) + \ldots + (2^1 - 1) = 2^{k'-1} - k'$ moves, and now we achieved our aim. This is also the smallest necessary, since we invoked the inductive hypothesis which says this is necessary. (Lemma 1 only says this is sufficient.) One final move completes the job, proving the inductive hypothesis for $k = k'$ , and thus by induction, Lemma 2 is proven for all $k$ .

With Lemma 2 proven, we will now prove the main result:

Result : It takes $2^{n-1} - (n-1)$ moves to bring $n$ to the first element of the sequence.

We repeat the proof in Lemma 2.
Invoking Lemma 2 for $k \gets n-2, a \gets n-1, b \gets n$ gives $2^{n-2} - (n-2)$ moves to obtain the sequence $n-1, n-3, n-4, \ldots, 1, n, n-2, \ldots$ . Doing $n-3$ moves moves makes the sequence $1, 2, 3, \ldots, n-3, n-1, n, n-2, \ldots$ in $2^{n-2} - 1$ moves.
We repeat it for $k \gets n-3$ , then for $k \gets n-4$ , and so on until $k \gets 1$ , to obtain the sequence $n-1, n, n-2, n-3, n-4, \ldots, 1$ within $(2^{n-2} - 1) + (2^{n-3} - 1) + \ldots + (2^1 - 1) = 2^{n-1} - n$ moves; one final move throws $n-1$ away and makes $n$ at the front of the sequence, done in $2^{n-1} - (n-1)$ moves.
Due to the result in Lemma 2, we know that there is no faster method to bring $n$ to the $(n-1)$ -th position other than $k \gets n-2, a \gets n-1, b \gets n$ ; there is no faster method to bring $n$ to the $(n-2)$ -th position other than $k \gets n-3, a \gets n-1, b \gets n$ ; and so on, so this is indeed the shortest way to bring $n$ to the front of the sequence. This proves that it takes $2^{n-1} - (n-1)$ moves to do so.

I'm sure this can be simplified, with so many repeated statements, but I can't think of it at the moment.

I have found the relation that the number of throws require to get $n$ to the head of the sequence is:

$2^{n-1}-(n-1) \quad \quad n \neq 1$

I've not been able to prove this yet but it seems to hold for all $n \neq 1$ . This gives the answer as:

$2^{20-1}-(20-1)= \boxed{\boxed{524269}}$

Here's a solution in C:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

void throw(int *sequence, int *length) {
    int first_num = sequence[0];
    int second_num = sequence[1];
    if (second_num >= *length) {
        int old_length = *length;
        *length = second_num + 1;
        sequence = realloc(sequence, *length * sizeof(int));
        for (int i = old_length; i < *length; i++) {
            sequence[i] = i + 1;
        }
    }
    memmove(&sequence[0], &sequence[1], second_num * sizeof(int));
    sequence[second_num] = first_num;
}

void print_sequence(int *sequence, int length) {
    printf("[");
    for (int i = 0; i < length; ++i) {
        if (i > 0) {
            printf(", ");
        }
        printf("%d", sequence[i]);
    }
    printf("]\n");
}

int main(int argc, const char * argv[]) {
    int sequence_length = 3;
    int *sequence = malloc(sequence_length * sizeof(int));
    for (int i = 0; i < sequence_length; ++i) {
        sequence[i] = i + 1;
    }

    uint64_t i = 0;
    while (true) {
        if (sequence[0] == 20) {
            printf("throw %llu: ", i);
            print_sequence(sequence, sequence_length);
            break;
        }
        throw(sequence, &sequence_length);
        i += 1;
    }

    free(sequence);
    return 0;
}

and an arguably easier to read solution in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def throw(sequence):
    first_num = sequence[0]
    second_num = sequence[1]
    if second_num >= len(sequence):
        old_length = len(sequence)
        for i in range(old_length, second_num + 1):
            sequence.append(i + 1)
    sequence.pop(0)
    sequence.insert(second_num, first_num)


def main():
    sequence = []
    for i in range(0, 3):
        sequence.append(i + 1)

    i = 0
    while True:
        if sequence[0] == 20:
            print('throw {}: {}'.format(i, sequence))
            break
        throw(sequence)
        i += 1

main()