 |
Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.4 |
|
|
Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.4 |
Michael Kleber
Dept. of Mathematics
Massachusetts Institute of Technology
Supported by an NSF Postdoctoral Fellowship
Email address:
kleber@math.mit.edu
The numbers from 1 to 2001 are written on a sheet of paper. Choose two of these numbers, say a and b, remove them from the list, and add |a2 - b2| (the nonnegative difference between their squares) to the list. Repeat this procedure over and over again. Each time, you take away two numbers from the list, square them, and adjoin to the list the nonnegative difference (it might be 0) of their squares. After a number (how many?) of such operations, you will have only one number left on the paper. Can you choose the numbers so that this last remaining number is zero?(We wish to thank Loren Larson, who is preparing an English version of [V], for this translation.)
The answer is "no", since the number of odd numbers in the set is initially 1001, and its parity never changes. But this led Richard K. Guy [personal communication] to ask the more general question:
Start with a multiset S of integers. Repeatedly replace two members a and b by |a2 - b2|, until a single integer remains. How small can the remaining value be?In this paper we answer this question whenever S has the form {1, 2, ..., n} for a positive integer n. We also give some partial results for other intervals.
First, some notation and terminology:
We let f(a,b) = |a2 - b2|.
If a multiset T can be obtained from a multiset S by repeatedly replacing elements a and b by f(a,b), we will say that T is a reduction of S, or that S can be reduced to T. If T is a singleton, {t}, we will also say that S can be reduced to t.
If S is a nonempty multiset of integers then we let r(S) be the smallest number such that S can be reduced to r(S).
If n is a positive integer, we write r(n) for r({1, 2, ..., n}).
It is easy to find by hand that
r(1) = 1,
r(2) = f(1,2) = 3,
r(3) = f(f(1,2), 3) = 0,
r(4) = f(f(f(1,2), 3), 4) = 16,
r(5) = f(f(0,1), 4) = 15, where 0 = f(f(2,3), 5), and
r(8) = f(f(f(2,4), f(6,7)), f(0,5)) = 0, where 0 = f(f(1,3), 8).
By exhaustive computer search, we also obtain
r(6) = f(f(f(1,4), f(3,5)), f(2,6)) = 63 and
r(7) = f(f(0,1), 3) = 8, where 0 = f(f(f(4,5), 7), f(2,6)).
(Unfortunately, we know of no succinct proof of these two values.)
As we will prove, the sequence continues as shown here:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
r(n) 1 3 0 16 15 63 8 0 3 1 0 0 1 3 0 4 3 3 4 0
This is sequence
A038122 in [EIS]. Our main result states that, for n greater than or equal to 8, the sequence is periodic with period 12.
Theorem: For n>0, let s(n) be defined by the table below:
n mod 12 0 1 2 3 4 5 6 7 8 9 10 11
s(n) 0 1 3 0 4 3 3 4 0 3 1 0
Then, for n not equal to 4, 5, 6, or 7, we have r(n) =
s(n). Furthermore, r(4) = 16,
r(5) = 15, r(6) = 63, and
r(7) = 8. Our proof consists of three parts: First, we prove congruences for r(S) for an arbitrary multiset S, which will imply that r(n) >= s(n). Next, we will show that r(n+24) <= r(n) for all n. Finally, we will compute the values of r(n) for n from 1 to 23 and from 28 to 31. From this information, our result will follow by induction.
Note: The first part of this is not true if |S| = 1; e.g. r({2}) = 2 is not divisible by 4.
Proof: As noted earlier, the parity of the number of odd elements doesn't change when we replace a and b by f(a,b). So in the first case, r(S) is even. But a difference of squares can't be congruent to 2 (mod 4), so r(S) must be divisible by 4. In the second case, r(S) must be odd. QED
Lemma 1: If the number of elements of S which are not divisible by 3 is even, then r(S) is divisible by 3. Otherwise, r(S) is not divisible by 3.
Proof: If a and b are either both divisible by 3 or both not divisible by 3, then f(a,b) is divisible by 3. Otherwise it is not. In either case, replacing a and b by f(a,b) does not change the parity of the number of elements which are not divisible by 3. So if that number is even, then r(S) is divisible by 3; otherwise it is not. QED
Applying Lemmas 0 and 1 to the case S = {1, 2, ..., n}, we find the following information about r(n) modulo 6 or 12:
n mod 12 r(n) mod 2 or 4 r(n) mod 3 r(n) mod 6 or 12
-------- --------------- ---------- ----------------
0 0 (mod 4) 0 0 (mod 12)
1 1 (mod 2) 1 or 2 1 or 5 (mod 6)
2 1 (mod 2) 0 3 (mod 6)
3 0 (mod 4) 0 0 (mod 12)
4 0 (mod 4) 1 or 2 4 or 8 (mod 12)
5 1 (mod 2) 0 3 (mod 6)
6 1 (mod 2) 0 3 (mod 6)
7 0 (mod 4) 1 or 2 4 or 8 (mod 12)
8 0 (mod 4) 0 0 (mod 12)
9 1 (mod 2) 0 3 (mod 6)
10 1 (mod 2) 1 or 2 1 or 5 (mod 6)
11 0 (mod 4) 0 0 (mod 12)
From this table we obtain: Lemma 2: r(n) >= s(n) for all n >= 1.
Lemma 3: If r(T) = 0 and either 0 or 1 is an element of S, then r(S union T) <= r(S).
Proof: Since T can be reduced to 0, S union T can be reduced to S union {0}. If 0 is in S then S union {0} contains two 0's; replacing them by f(0,0) = 0 reduces S union {0} to S. Similarly, if 1 is in S then replacing 0 and 1 by f(0,1) = 1 reduces S union {0} to S. Finally, S can be reduced to r(S), so we conclude that S union T can be reduced to r(S). Hence r(S union T) <= r(S). QED
Lemma 4: For any integer n, r([n,n+23]) = 0.
Here [x,y] denotes the set of integers >= x and <= y.
Proof: First we replace each pair n+i and n+23-i (0 <= i <= 11) by the difference of their squares, namely f(n+i, n+23-i) = (23-2i) |2n+23|. Letting m = |2n+23|, we have reduced [n,n+23] to {m, 3m, 5m, ..., 23m}.
Next, we reduce this set to {0,0} via
f(f(3m,7m), f(9m,11m)) = 0
and
f(f(f(m,5m), f(13m,15m)), f(f(17m,19m), f(21m,23m))) = 0.
Finally, reducing {0,0} to f(0,0)=0 completes the proof. QED
Combining Lemmas 3 and 4 yields:
Lemma 5: For n >= 25, r(n) <= r(n-24).
Proof: Apply Lemma 3 with S = [1,n-24] and T = [n-23,n]: By Lemma 4 with n changed to n-23, r(T) = 0. Hence
r(n) = r(S union T) <= r(S) = r(n-24). QED
Now suppose that n >= 25 and that r(n-24) = s(n-24). Then
r(n) <= r(n-24) = s(n-24) = s(n).
But, by Lemma 2, r(n) >= s(n), so r(n) = s(n). So if the Theorem is true for a value of n other than 4, 5, 6, or 7, then it is also true for n+24. So to complete the proof, we need only show that it is true for n <= 24 and for 28 <= n <= 31. We've already discussed the values of r(n) for n <= 8; in the next section we prove the remaining values.
In each reduction, we explicitly show the zeros that occur as intermediate values. For example, for r(10), we first reduce {4,5,9} to 0, then reduce {0,6,8,10} to 0, then reduce {0,2,3,7} to 0, and finally reduce {0,1} to 1.
Verifying these reductions is easy, although in some cases finding them was not, since the size of the problem grows rapidly with the size of the set. Specifically, the number of possible reductions for a set of n elements is (2n-3)!! = 1 * 3 * 5 * ... * (2n-3). To see this by induction on n, suppose that we have a reduction on a set S of n elements. Then we can add another element a to it by changing some X to f(X,a), where X is either one of the original n elements, or one of the n-1 expressions of the form f(Y,Z) that occur in the original reduction. So there are 2n-1 ways to add the new element for each reduction of S. (This is not a new result; it is essentially Problem 1.36 of [L].)
With the computer resources that we have available, we can do an exhaustive search of the roughly 14 billion reductions of a set of 12 elements in about 3.5 hours. For larger sets, we made reasonable guesses about initial steps which reduced certain subsets to 0, and then used computer searches on the reduced sets. Sometimes we had to try several different combinations of initial steps before finding one that worked.
r(9) = 3, because
f(f(f(f(3,4), 6), f(7,8)), f(5,9)) = 0 and
f(f(0,1), 2) = 3.
r(10) = 1, because
f(f(4,5), 9) = 0,
f(f(0,6), f(8,10)) = 0,
f(f(f(0,2), 3), 7) = 0, and
f(0,1) = 1.
r(11) = 0, because
f(f(3,7), f(9,11)) = 0,
f(f(0,6), f(8,10)) = 0, and
f(f(f(1,2), 0), f(4,5)) = 0.
r(12) = 0, because
f(f(f(3,4), 1), f(f(6,7), 11)) = 0 and
f(f(f(2,5), f(9,10)), f(8,12)) = 0.
r(13) = 1, because
f(f(3,7), f(9,11)) = 0,
f(f(0,6), f(8,10)) = 0,
f(f(0,5), f(12,13)) = 0,
f(f(0,2), 4) = 0, and
f(0,1) = 1.
r(14) = 3, because
f(f(5,10), f(11,14)) = 0,
f(f(6,7), 13) = 0,
f(f(f(f(3,4), 8), 12), f(0,9)) = 0, and
f(f(0,1), 2) = 3.
r(15) = 0, because
f(f(1,4), f(7,8)) = 0,
f(f(2,5), f(10,11)) = 0,
f(f(3,6), f(13,14)) = 0, and
f(f(0,9), f(12,15)) = 0.
r(16) = 4, because
f(f(5,10), f(11,14)) = 0,
f(f(6,7), 13) = 0,
f(f(1,3), 8) = 0,
f(f(0,9), f(12,15)) = 0,
f(f(0,4), 16) = 0, and
f(0,2) = 4.
r(17) = 3, because
f(f(4,7), f(16,17)) = 0,
f(f(f(11,12), f(13,14)), f(5,15)) = 0,
f(f(0,3), 9) = 0,
f(f(0,6), f(8,10)) = 0, and
f(f(0,1), 2) = 3.
r(18) = 3, because
f(f(4,12), f(14,18)) = 0,
f(f(5,9), f(13,15)) = 0,
f(f(f(f(6,7), 11), f(8,10)), f(f(0,3), f(16,17))) = 0, and
f(f(0,1), 2) = 3.
r(19) = 4, because
f(f(f(11,12), f(14,15)), f(f(9,10), 7)) = 0,
f(f(8,13), f(16,19)) = 0,
f(f(1,6), f(17,18)) = 0,
f(f(0,3), f(4,5)) = 0, and
f(0,2) = 4.
r(20) = 0, because
f(f(f(11,14), f(17,18)), f(f(10,13), 19)) = 0,
f(f(9,15), f(16,20)) = 0,
f(f(1,4), f(7,8)) = 0, and
f(f(f(f(f(0,2), 3), 6), 5), f(0,12)) = 0.
r(21) = 3, because
f(f(f(10,11), 6), f(f(13,14), 18)) = 0,
f(f(f(3,5), 17), f(4,7)) = 0,
f(f(9,15), f(16,20)) = 0,
f(f(8,12), f(19,21)) = 0, and
f(f(0,1), 2) = 3.
r(22) = 1, because
f(f(f(f(2,4), 13), 20), f(f(f(3,5), 16), 15)) = 0,
f(f(7,11), f(f(9,10), 17)) = 0,
f(f(8,12), f(19,21)) = 0,
f(f(6,14), f(18,22)) = 0, and
f(0,1) = 1.
r(23) = 0, because
f(f(f(10,11), f(13,14)), f(6,18)) = 0,
f(f(f(1,3), f(4,5)), 17) = 0,
f(f(9,15), f(16,20)) = 0,
f(f(8,12), f(19,21)) = 0, and
f(f(2,7), f(22,23)) = 0.
r(24) = 0, by Lemma 4 with n=1.
r(28) = 4, because
f(f(7,14), f(23,26)) = 0,
f(f(f(18,19), f(21,24)), f(f(22,25), f(27,28))) = 0,
f(f(f(f(3,4), 6), 1), f(f(9,10), f(11,12))) = 0,
f(f(5,13), f(16,20)) = 0,
f(f(0,8), f(15,17)) = 0, and
f(0,2) = 4.
r(29) = 3, because
f(f(f(19,20), f(22,25)), f(f(23,26), f(28,29))) = 0,
f(f(f(3,6), 12), f(f(10,14), f(15,18))) = 0,
f(f(f(5,7), 21), f(11,16)) = 0,
f(f(4,13), f(24,27)) = 0,
f(f(8,9), 17) = 0, and
f(f(0,1), 2) = 3.
The values of r(30) and r(31) are obtained from those of
r(18) and r(19) with the help of Lemma 3:
r([19,30]) = 0, because
f(f(f(19,20), 21), f(f(24,25), f(29,30))) = 0 and
f(f(0,28), f(f(22,23), f(26,27))) = 0;
therefore r(30) = r(18) = 3.
r([20,31]) = 0, because
f(f(f(20,24), 29), f(f(21,25), f(30,31))) = 0 and
f(f(0,28), f(f(22,23), f(26,27))) = 0;
therefore r(31) = r(19) = 4.
This completes the proof of the Theorem.
r({n-6, n-2, n-1, n+1, n+2, n+6}) =
(4.0)
f(f(f(n-1,n-2), n-6), f(f(n+1,n+2), n+6)) = 0;
r({n-5, n-4, n-2, n-1, n+1, n+2, n+4, n+5}) =
(4.1)
f(f(f(n-5,n-4), f(n-2,n+1)), f(f(n-1,n+2), f(n+4,n+5))) = 0.
(Equation (4.1) with n=23 and 24 was used in proving the values of
r(28) and r(29).) Each of these examples is symmetric: There is some integer k such that the reduction is unchanged if we change n+i to n+k-i for each i. But there are also asymmetric examples, such as
r({n, n+1, n+3, n+5, n+12, n+13, n+18, n+20}) =
(4.2)
f(f(f(n,n+5), f(n+1,n+12)), f(f(n+3,n+13), f(n+18,n+20))) = 0.
Open Problem 0: Find necessary and sufficient conditions on a
multiset of integers {a1, ..., ak} so that
r({n+a1, ..., n+ak})
= 0 for all n. An obvious necessary condition is that both the number of even elements and the number of odd elements be even; otherwise we could pick n so that Lemma 0 would rule out a reduction to 0. Similarly, the number of elements in each congruence class mod 3 must be even.
If the equation r({n+a1, ..., n+ak}) = 0 is not true for all n, then there are only finitely many values of n for which it is true. To see this, note that the result of any particular reduction of the set has the form |p(n)| for some polynomial p. If one of these polynomials is identically zero, then r({n+a1, ..., n+ak}) = 0 for all n. Otherwise, the equation is true only if n is one of finitely many roots of finitely many polynomials.
Beyond that, we have little information about this problem. Even for intervals, we haven't completely solved it. The mod 2 and mod 3 restrictions imply that if every interval of length k can be reduced to 0, then k must be a multiple of 12. We hoped for a while that every interval of length 12 could be reduced to 0; that would have simplified the proof of the Theorem. We found such reductions for the intervals [n,n+11] with n = -5 to 14, 16, 17, 19, 20, and 26. However, an exhaustive computer search showed that this is not true in general; in particular the interval cannot be reduced to 0 for n = 15, 18, or 21 to 25.
For larger multiples of 12, we know from Lemma 4 that every interval of length 24 can be reduced to 0. We now show that the same is true for intervals of length 60: Starting with [n,n+59], we first use (4.0) with n replaced by n+6 and n+53, reducing both
{n, n+4, n+5, n+7, n+8, n+12} and
{n+47, n+51, n+52, n+54, n+55, n+59}
to 0. Next, for i = 1 to 3, 6, 9 to 11, and 13 to 29, we reduce {n+i,n+59-i} to (59-2i)m, where m = |2n+59|. This gives us the set
{m, 3m, 5m, 7m, 9m, 11m, 13m, 15m, 17m, 19m, 21m, 23m, 25m, 27m,
29m, 31m, 33m, 37m, 39m, 41m, 47m, 53m, 55m, 57m}.
Finally, we use
f(f(5m,29m), f(47m,55m)) = 0,
f(f(7m,19m), f(37m,41m)) = 0,
f(f(17m,27m), f(53m,57m)) = 0,
f(f(23m,31m), f(33m,39m)) = 0,
and
f(f(f(m,13m), f(3m,9m)), f(f(11m,15m), f(21m,25m))) = 0
to complete the reduction to 0.
In conjunction with the result for intervals of length 24, this implies that every interval whose length is a multiple of 12, except for 12 itself, and with the possible exception of 36, can be reduced to 0. This leaves us with:
Open Problem 1: Can every interval of length 36 be reduced to 0?
Received February 21, 1999. Published in Journal of Integer Sequences March 15, 1999.