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 a1, a2, a3, ... of positive integers such that             (i)  every positive integer appears exactly once in the sequence, and             (ii) for every n, an divides a1 + a2 + ... + an.

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, because there is no suitable choice for a₂. So we start with a₁ = 2, and follow the following strategy:

Strategy 1: If a₁, a₂, ..., a_n are already selected, we put s_n = a₁ + a₂ + ... + a_n, and select a_n+1 as the smallest divisor of s_n not yet chosen.

The first few values of a_n are shown in the table above. For n > 1 we have s_n > a₁, a₂, ..., 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₁, a₂, ..., 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

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ⁱ with i < k, and the next sum 2^k + 2ⁱ 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^j-1s_n to get s_n+j = 2^js_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ⁱ 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+k-1. Note that b_i + b_i+1 + ... + b_i+k-1 ≡ 0 (mod N). Indeed for t = b_i + b_i+1 + ... + b_i+k-1, we get

We use a_n = s_n–1 up to s_n–1 = 192 = 64·3: at s₆= 24 ≡ 4 (mod 5) we need a₇ ≡ 1 (mod 5) for the next term, but we cannot use a₇= 16 because it does not divide 24; similarly with s₇= 48 ≡ 3 (mod 5) we need a₈ ≡ 2 (mod 5), but 32 does not divide 48, and with s₈= 96 ≡ 1 (mod 5) we need a₉ ≡ 4 (mod 5), but 64 does not divide 24.  Finally, with s₉= 192 ≡ 2 (mod 5) we need a₁₀ ≡ 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₁₀= 32 and a₁₁= 16, which allows us to set a₁₂ = 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₁ + ... + 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, 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.