Solution for May 2009
The Problem: 

MP87 May 2009
Our goal this month is to correct a flaw in the usual ordering of the positive integers: when n is odd then it divides but when n is even then it does not divide 1 + 2 + ... + n; so it is only half the time that the nth integer divides the sum of all the integers up to it. Our problem is to find a better ordering of the positive integers; specifically,
find a sequence a_{1}, a_{2}, a_{3}, ... of positive integers such that
(i) every positive integer appears exactly once in the sequence, and
(ii) for every n, a_{n} divides a_{1} + a_{2} + ... + a_{n}.

Correct responses: 

Correct solutions were sent in this month by
Philippe Fondanaiche (France)

John T. Robinson (USA) 
Patrick J. LoPresti (USA) 
Albert Stadler (Switzerland) 

The solution:
Our solution includes ideas from all
correspondents. Obviously we cannot start with a_{1 }=
1, because there is no suitable choice for a_{2}. So
we start with a_{1 }= 2, and follow the following
strategy:
Strategy 1: If a_{1},
a_{2}, ..., a_{n} are
already selected, we put s_{n}
= a_{1} + a_{2} + ... + a_{n},
and select a_{n+1} as the smallest divisor of s_{n} not yet chosen.
n: 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
a_{n}: 
2 
1 
3 
6 
4 
8 
12 
9 
5 
10 
15 
25 
20 
24 
16 
s_{n}: 
2 
3 
6 
12 
16 
24 
36 
45 
50 
60 
75 
100 
120 
144 
160 
The first few values of a_{n} are
shown in the table above. For n
> 1 we have s_{n} >
a_{1}, a_{2}, ..., a_{n}, hence it is always possible to select a next value a_{n+1},
which will be at most s_{n}.
It is clear that this infinite sequence satisfies property (ii), but
not so clear that it also satisfies property (i). In fact our
correspondents looked up this sequence in the Online Encyclopedia of
Integer Sequences http://www.research.att.com/~njas/sequences/,
where it is conjectured that this sequence contains all the positive
integers. Since we cannot prove the conjecture, after a while we
abandon Strategy 1 and switch to:
Strategy 2:
Suppose a_{1}, a_{2}, ..., a_{n}
are already chosen and we start to worry because some integer N has not yet appeared. If s_{n} is a power of 2, we
use Strategy 1 for one more step to get a sum which is not a power of
2. Then we start appending terms a_{k+1}
= s_{k} until we are sure to reach a multiple of N by appending suitable powers of 2.
The first step is to dispose of the undesirable
situation when s_{n} = 2^{k}.
In this case we cannot have all the previous powers of 2 already used,
for otherwise we would have
s_{n}  1 = 1 + 2 + ... + 2^{k1}
< a_{1} + ... + a_{n} = s_{n},
and the only way to complete the sequence would be to
have n = k+1 and a second term equal to 1.
Hence Strategy 1 yields a new term 2^{i}
with i < k, and the next sum 2^{k} + 2^{i} is not a power of two.
Therefore without loss of generality we may assume that
we start worrying about N at
a point when s_{n }is
not a power of 2. We can also assume that N is odd because of the following argument. We put a_{n+1}
= s_{n}
whence s_{n+1} = 2s_{n},
then a_{n+2}
= 2s_{n} whence s_{n+2} = 4s_{n},
and we keep appending terms of the form a_{n+j} = 2^{j1}s_{n}
to get s_{n+j} = 2^{j}s_{n}, until 2^{j} is large
enough. To understand what we mean by ``large enough'', we will examine
the sequence of powers of 2 modulo N.
For every integer i,
let b_{i} be the
remainder of division of 2^{i}
by N. Since there are only
finitely many remainders to chose from, there exist integers i, k such that b_{i+k} = b_{i}. We then have b_{i+k+1} = b_{i+1}, b_{i+k+2} = b_{i+2}, and the
sequence keeps cycling through the terms b_{i}, b_{i+1}, ...,b_{i+k1}. Note that b_{i} +
b_{i+1} + ... + b_{i+k1}
≡ 0 (mod N). Indeed for t = b_{i} +
b_{i+1} + ... + b_{i+k1}, we get
2 t = 2 b_{i} +
2b_{i+1} + ... + 2b_{i+k1}
≡ b_{i+1} +
b_{i+2} + ... + b_{i} ≡ t (mod N)
whence t
≡ 0 (mod N).
Now s_{n} admits a
representation as a sum of distinct powers of 2, whence for any j > i, 2 ^{j}s_{n} is
congruent modulo N to a sum
of terms in b_{i}, b_{i+1}, ..., b_{i+k1}. With the
identity 2 b_{m}
≡ b_{m+1}
(mod N), we can simplify the
sum until we get a sum of distinct terms in b_{i}, b_{i+1}, ..., b_{i+k1} which is
congruent modulo N to 2 ^{j}s_{n}. Let b_{m(1)}, ..., b_{m(r)} be the terms in b_{i}, b_{i+1}, ..., b_{i+k1} which are not
used in this sum. If we picked j
large enough, we can pick a decreasing sequence 2 ^{j}
> 2 ^{e(1)}
> ... > 2 ^{e(r)}
such that 2 ^{e(p)}
≡ b_{m(p)} (mod N), 2 ^{e(1)},
..., 2 ^{e(r)} do not
appear in the sequence a_{1}, a_{2}, ..., a_{n}.
Since s_{n }is
not a power of 2, 2 ^{e(1)},
..., 2 ^{e(r)} do not
appear either in the remaining terms a_{n+1}
= s_{n},
..., a_{n+j} = 2 ^{j1}s_{n}.
Therefore we can pick a_{n+j+1}
= 2 ^{e(1)} , s_{n+j+1} = 2 ^{e(2)}q_{1}, a_{n+j+2} = 2 ^{e(2)} , s_{n+j+1} = 2 ^{e(3)}q_{2}, ...,
up to a_{n+j+}_{r} = 2 ^{e(r)}. We then have
s_{n+j+r} = 2^{j}s_{n} + 2^{e(1)} + ... + 2^{e(r)} ≡
0_{} (mod N).
Thus we can select a_{n+j+r+1} = N.
Here is how the process works up to n = 12. We begin with Strategy 1,
n 
1 
2 
3 
4 
5 






a_{n} 
2 
1 
3 
6 
4 






s_{n} 
2 
3 
6 
12 
16 






which gets us a sequence of length 5 with numbers up to 4. We now want N = 5 in our sequence. Because s_{5}= 16 is a power of 2, we take a_{6}= 8 so that s_{6}= 24. We will be working mod 5 (because N = 5), which means that we might need as many as N – 1 = 4 powers of 2 that exceed 8 (the largest power of 2 that has thus far appeared); that is, we might need
b_{4}= 2^{4} = 16 ≡ 1 (mod 5),
b_{5} = 2^{5} = 32 ≡ 2 (mod 5),
b_{6} = 2^{6} = 64 ≡ 4 (mod 5),
b_{7} = 2^{7} = 128 ≡ 3 (mod 5).
n 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 

a_{n} 
2 
1 
3 
6 
4 
8 
24 
48 
96 
32 
16 
5 
... 
s_{n} 
2 
3 
6 
12 
16 
24 
48 
96 
192 
224 
240 
245 

We use a_{n} = s_{n–1} up to s_{n–1} = 192 = 64·3: at s_{6}= 24 ≡ 4 (mod 5) we need a_{7} ≡ 1 (mod 5) for the next term, but we cannot use a_{7}= 16 because it does not divide 24; similarly with s_{7}= 48 ≡ 3 (mod 5) we need a_{8} ≡ 2 (mod 5), but 32 does not divide 48, and with s_{8}= 96 ≡ 1 (mod 5) we need a_{9} ≡ 4 (mod 5), but 64 does not divide 24. Finally, with s_{9}= 192 ≡ 2 (mod 5) we need a_{10} ≡ 3 (mod 5), and although 128 does not divide 192, we can now use 32 + 16 ≡ 3 (mod 5) and save 64 and 128 for a future step. Consequently we set a_{10}= 32 and a_{11}= 16, which allows us to set a_{12} = 5, as promised. The next missing number is N = 7, so we will possibly use the next N – 1 = 6 powers of 2 (starting with 64), and the process continues ad infinitum.
A related problem.
Fondanaiche reported that he came across a problem from the 12th Nordic Mathematical Contest (1998) that is closely related to our problem. It asked for a rearrangement a_{n} of the positive integers in which the partial sums s_{n} = a_{1} + ... + a_{n} are divisible by n (unlike our problem where s_{n} is divisible by a_{n}). Patrick LoPresti, Lou Cairoli, Ruben Victor Cohen, and Bojan Basic also sent in solutions to this variation of the problem. Here is a composite of their similar solutions.
Define the arrangement recursively: Let a_{1} = 1, and set
if this number is not already in the sequence; otherwise set
Note that in the first case
In the second case,
In both cases we see that s_{n} is divisible by n, as desired. Moreover, the difference between successive quotients is either 0 or 1. The sequence of quotients grows monotonically without bound (since the difference cannot be 0 twice in a row). Since a_{n} is defined to be equal to the value of the quotient if that value has not yet appeared, every positive integer must eventually be reached. On the other hand, because the quotients are increasing it is not possible that can equal a previous or for k < n. Here, then, are the first 14 terms of the resulting sequence.
n 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 

a_{n} 
1 
3 
2 
6 
8 
4 
11 
5 
14 
16 
7 
19 
21 
9 

s_{n} 
1 
4 
6 
12 
20 
24 
35 
40 
54 
70 
77 
96 
117 
126 
... 

1 
2 
2 
3 
4 
4 
5 
5 
6 
7 
7 
8 
9 
9 

