Surviving pair

I will first solve the problem if the list contained the numbers 0 to 999,999 instead of 1 to 1,000,000. Then I will show how to modify it to solve the original problem.

(a) Let the numbers 0 to 999,999 correspond to the indices of the positions of the numbers. Let us represent these as 20-bit strings (because $2^{19} <1,000,000, < 2^{20}$ ). Crossing out the numbers in the odd positions (i.e. with odd indices) corresponds to crossing to crossing out all the numbers whose least significant bit is 1.
Those with least significant bit 0 survive. In step ii we cross out all the numbers with even indices in the surviving list. This corresponds to crossing out all the numbers whose second least significant bit is 0. In the next step we cross out the odd indices from the remaining list, i.e. those whose third least significant bit is 1. and so on. Thus, the unique number that survives this process is the number whose index is represented by the 20-bit string 10101010101010101010. Because our list of numbers is 0 to 999,999, and in the initial list the number stored at index $i$ is $i$ , this means that the unique surviving number is the number whose binary representation is 10101010101010101010 In the second process, we do the same thing, only with odd and even switched. It easily follows that the unique surviving number in this process is the number whose binary representation is 01010101010101010101 (a 20 bit string with leading 0). Adding these numbers together gives the number with binary representation 11111111111111111111, or $\boxed{ 2^{20}-1 }$

(b) To go back to solving the original problem , note that when the list is 1 to 1,000,000 (but the indexing still starts at 0) the initial number at index $i$ is $i+1$ . However, the crossing out processes operated only on the indices, not on the contents of the list. Thus both processes result in the same indices surviving, so that the surviving numbers are 1 more than the corresponding surviving numbers in (a). Thus when the two are added up, the sum is 2 more than the answer in (a) or $\boxed{ 2^{20}+1 = 1,048,577 }$

First, observe that in both cases, after the $n$ th elimination step the remaining numbers form an arithmetic sequence with common difference $2^n$ . Also, after each elimination step the first term of the new sequence is alternately the first or second term of the old sequence. Let $a_i^n$ be the $i$ th term in the $n$ th iteration of the first sequence, and similarly for $b_i^n$ for the second sequence. Consider the first two terms in the first few iterations of each sequence:

If we continue the iteration until the first term of each sequence is less than 1 million, and every term after the first is greater than 1 million, then those first terms are $A$ and $B$ . Let $\{A_k\}$ be the sequence of first terms of the first sequence, ignoring repetition, and define $\{B_k\}$ similarly for the second sequence. We can see that $A_k = 2 + 4 + 16 + 64 + \dots + 4^{k - 1} = 1 + \sum_{i = 0}^k 4^i = 1 + \dfrac{4^k - 1}{4 - 1} = \dfrac{4^k + 2}{3}$

and

$B_k = 1 + 2 + 8 + 32 + \dots + 2 \cdot 4^{k - 1} = 1 + 2 \sum_{i = 0}^k 4^i = 1 + 2 \dfrac{4^k - 1}{4 - 1} = \dfrac{2 \cdot 4^k + 1}{3}$ .

Solving both $A_k < 1,000,000$ and $B_k < 1,000,000$ gives $k \le 10$ , so $A + B = A_{10} + B_{10} = 349,526 + 699,051 = 1,048,577$ .

using $Mathematica$

s=Range@1000000; n=1; While[Length@s>1,s=Drop[s,{1+Abs@Sin[n*Pi/2],-1,2}];n++]; s

this code does the thing and you only have to switch n
n=1 returns 699051
n=2 returns 349526

result 1048577

this is not a complete proof, just some good intuition

Imagine instead of writing the numbers from $1$ to $100000$ , you write the numbers from $1$ to $1048576$ , which is $2^{20}$ . By eliminating all the odd numbers, you eliminate $1$ , and you leave $1048576$ , which is the last number, and by eliminating the evens, you eliminate the last, but leave the first. This means doing the reversed operation is the same as doing the normal operation, but reading the list backwards, we know it will never get to a point where both the first and last numbers get eliminated because we chose a power of $2$ as our list length. This means if by doing the regular operation, the last number remaining is $n$ , by doing reversed operation, the last number remaining is $(1048576+1-n)$ , which is the $n^{th}$ number, if you start reading backwards from the last number. Therefore, the sum is $1048576+1-n+n=1048577$

To make this rigorous, the main thing you'd have to prove that I didnt explain here is that neither the normal operation, neither the reversed leave a number between $1000000$ and $1048577$ as the last non-removed number.

Did the lazy man's approach and coded a program to solve it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

list = [n for n in range(1,1000000)]

def cross_out(list,start_position):
    new_list = list[start_position::2]
    if len(new_list) == 1:
        print(new_list[0])
    else:
        cross_out(new_list,not start_position)

A = cross_out(list,0) #printed 699051
B = cross_out(list,1) #printed 349526
#which sum to 1048577

By using Python3's powerful range object, the result is almost instant.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

>>> a = b = range(1, 1000001)
>>> i = 0
>>> while len(a) + len(b) > 2:
...     if len(a) > 1:
...             a = a[i::2]
...     if len(b) > 1:
...             b = b[1-i::2]
...     i = 1-i
...
>>> a[0] + b[0]
1048577

Edited according to Paul Evans' suggestion.

Write the numbers in binary, and you will see that each step fixes a bit to a value 0 or 1, starting at the least significant bit. In the beginning we get a minor irregularity (which has to do with starting with 1 rather than 0), but after that, the pattern alternates.

For A we get binary ...1010110 where the most significat bit has value $2^{18}$ .

For B we get binary ...0101011 where the most significat bit has value $2^{19}$ .

A and B add up to 2^20+1.

Heres some code, runs in like a second or so and prints the correct answer

 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

<?php  
$arr = range(1,1000000);  
$i = 0;  
do{  
    $arr = unset_arr($arr, $i%2 );  
    $i++;  
} while(count($arr)>1);  
$a = $arr[0];  

$arr = range(1,1000000);  
$i = 1;  
do{  
    $arr = unset_arr($arr, $i%2 );  
    $i++;  
} while(count($arr)>1);  
$b = $arr[0];  

echo $a.'+'.$b.'='.($a+$b);  
//prints 349526+699051=1048577  

function unset_arr($arr,$start){  
    $c = count($arr);  
    for($i=$start;$i<=$c;$i+=2){  
        unset($arr[$i]);  
    }  
    $arr = array_values($arr);  
    return $arr;  
}  
?> 

with javascript (you can run this here in your browser, opening the javascript console), define:

our original list (array) of numbers

const oneToOneMillion = Array(1000000).fill(1).map((_, i) => i + 1)

the functions even and odd , used to get if the index is even or odd

const even = (_, i) => !(i % 2)

const odd = (_, i) => i % 2

the function that will filter the list until only one element remains

const continueFilter = (f1, f2, array) => array.length == 1 ? array[0] : continueFilter(f2, f1, array.filter(f1))

and now you get

continueFilter(even, odd, oneToOneMillion) + continueFilter(odd, even, oneToOneMillion)

=> 1048577

The numbers you cross out in each iteration are given by a sequence with general expression a*n-b, where a=2 in the first iteration, a=4 in the second, a=8 in the third, and a=2^k in the k-th iteration. Then you obtain b by subtracting the first odd or even element ot the sequence from a. Using this fact, I wrote the following code in Maple to obtain the result:

 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

s := seq(n, n = 1 .. 10^6):
S := {s}:
e := numelems(S):

for k from 1 by 1 while e>1 do
if type(k, odd) then c := S[1] else c := S[2] end if:
a := 2^k:
b := a-c:
N := ceil((1/2)*e):
r := seq(a*n-b, n = 1 .. N):
R := {r}:
S := S minus R:
e := numelems(S):
end do:

p := S[1]:


s := seq(n, n = 1 .. 10^6):
S := {s}:
e := numelems(S):

for k from 1 by 1 while e>1 do:
if type(k, even) then c := S[1] else c := S[2] end if:
a := 2^k:
b := a-c:
N := ceil((1/2)*e):
r := seq(a*n-b, n = 1 .. N):
R := {r}:
S := S minus R:
e := numelems(S):
end do:

q := S[1]:
p; q; p+q;
                             349526
                             699051
                            1048577

We let the operator $\hat E$ cross out all the numbers in odd positions of an arbitrary given sequence $\{a_n\}, (n>0)$ , selecting only the numbers at even positions to remain. What this really means is that we're applying a change of variables $n \rightarrow 2n$ . Similarly, we let the operator $\hat O$ cross out all the numbers in even positions of a given sequence, selecting only the numbers at odd positions to remain. Again, this just means applying a change of variables $n \rightarrow 2n-1$ .

Having defined these operators, we select the original sequence $\{c_n\}$ to be the list of consecutive positive numbers from 1 to 1,000,000. First, we take a look at the sequence $\{e_n\}$ that remains in the list during the $k^{th}$ iteration $I_k$ if we start out by using the operator $\hat E$ .

$I_0 : \{c_n\} = \{n\}\\ I_1 : \{e_n\} = \hat E \{(c_n)\} = \{(2n)\}\\ I_2 : \{e_n\} = \hat O \hat E \{(c_n)\} = \{2(2n-1)\} = \{4n - 2\}\\ I_3 : \{e_n\} = \hat E \hat O \hat E \{(c_n)\} = \{4(2n) - 2\} = \{8n - 2\}\\ I_4 : \{e_n\} = \hat O \hat E \hat O \hat E \{(c_n)\} = \{16n - 10\}\\ I_5 : \{e_n\} = \hat E \hat O \hat E \hat O \hat E \{(c_n)\} = \{32n - 10\}\\$

Generally, $\\ I_k : \{e_n\} = \enspace ...\hat O \hat E \{(c_n)\} = 2^kn - \frac{2}{3} (4^{\lfloor \frac{k}{2} \rfloor} - 1)$

(Although the range of $n$ shrinks over each iteration, we won't pay meticulous attention to its range, because we have nothing to lose.) $\\$

Now for there to be only one item in the sequence $\{e_n\}$ , we must set the hypothetical second term to be greater than 1,000,000, that is: $e_2 = 2^{k+1} - \frac{2}{3} (4^{\lfloor \frac{k}{2} \rfloor} - 1) > 1,000,000$

and choose the smallest $k$ that satisfies this equation. This is found to be $k=20$ . This means that it is during the $20^{th}$ iteration of crossing out numbers that only one number will remain. This number is of course the first term in the sequence:

$A = e_1 = 2^{20} - \frac{2}{3} (4^{10} - 1) \\$

Similarly, if we start out with the $\hat O$ operator, the sequence $\{o_n\}$ that remains in the list during the $k^{th}$ iteration $I_k$ will be given by:

$I_0 : \{c_n\} = \{n\}\\ I_1 : \{o_n\} = \hat O \{(c_n)\} = \{(2n-1)\}\\ I_2 : \{o_n\} = \hat E \hat O \{(c_n)\} = \{2(2n)-1\} = \{4n - 1\}\\ I_3 : \{o_n\} = \hat O \hat E \hat O \{(c_n)\} = \{8n-5\}\\ I_4 : \{o_n\} = \hat E \hat O \hat E \hat O \{(c_n)\} = \{16n - 5\}\\ I_5 : \{o_n\} = \hat O \hat E \hat O \hat E \hat O \{(c_n)\} = \{32n - 21\}\\$

Generally, $\\ I_k : \{o_n\} = \enspace ...\hat E \hat O \{(c_n)\} = 2^kn - \frac{1}{3} (4^{\lceil \frac{k}{2} \rceil} - 1)$

Again, for there to be only one item in the sequence $\{o_n\}$ , we must set the hypothetical second term to be greater than 1,000,000, that is: $o_2 = 2^{k+1} - \frac{1}{3} (4^{\lceil \frac{k}{2} \rceil} - 1) > 1000000$ .

The smallest $k$ that can satisfy this is once again $k=20$ . Then, on the 20th iteration, only one number will remain:

$B = o_1 = 2^{20} - \frac{1}{3} (4^{10} - 1) \\$

Then, $A+B = 2^{20} - \frac{2}{3} (4^{10} - 1) + 2^{20} - \frac{1}{3} (4^{10} - 1)\\ A+B = 2^{20} + 2^{20} - \frac{3}{3} (4^{10} - 1)\\ A+B = 2^{20} + 2^{20} - (4^{10} - 1)\\ A+B = 2^{20} + 2^{20} - (2^{20} - 1)\\ A+B = 2^{20} + 1 = \boxed{1,048,577}$