Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.4 |

Dept. of Mathematics

University of California, Davis

Email address: dean@math.ucdavis.edu

Michael Kleber

Dept. of Mathematics

Massachusetts Institute of Technology

Supported by an NSF Postdoctoral Fellowship

Email address:
kleber@math.mit.edu

**Abstract:**We determine, for each positive integer*n*, the smallest number that can be obtained by starting with {1, 2, ...,*n*} and repeatedly replacing two numbers by the difference of their squares.

The numbers from 1 to 2001 are written on a sheet of paper. Choose two of these numbers, say(We wish to thank Loren Larson, who is preparing an English version of [V], for this translation.)aandb, remove them from the list, and add |a^{2}-b^{2}| (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?

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 multisetIn this paper we answer this question wheneverSof integers. Repeatedly replace two membersaandbby |a^{2}-b^{2}|, until a single integer remains. How small can the remaining value be?

First, some notation and terminology:

We let *f*(*a*,*b*) =
|*a*^{2} - *b*^{2}|.

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:

This is sequence A038122 in [EIS].n1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20r(n) 1 3 0 16 15 63 8 0 3 1 0 0 1 3 0 4 3 3 4 0

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:

Then, fornmod 12 0 1 2 3 4 5 6 7 8 9 10 11s(n) 0 1 3 0 4 3 3 4 0 3 1 0

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:

From this table we obtain:nmod 12r(n) mod 2 or 4r(n) mod 3r(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)

**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-2*i*) |2*n*+23|. Letting *m* = |2*n*+23|, we have
reduced [*n*,*n*+23] to {*m*, 3*m*, 5*m*, ...,
23*m*}.

Next, we reduce this set to {0,0} via

*f*(*f*(3*m*,7*m*), *f*(9*m*,11*m*)) = 0

and

*f*(*f*(*f*(*m*,5*m*), *f*(13*m*,15*m*)), *f*(*f*(17*m*,19*m*), *f*(21*m*,23*m*))) = 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 (2*n*-3)!! = 1 * 3 * 5 * ...
* (2*n*-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 2*n*-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.

The values ofr(9) = 3, becausef(f(f(f(3,4), 6),f(7,8)),f(5,9)) = 0 andf(f(0,1), 2) = 3.r(10) = 1, becausef(f(4,5), 9) = 0,f(f(0,6),f(8,10)) = 0,f(f(f(0,2), 3), 7) = 0, andf(0,1) = 1.r(11) = 0, becausef(f(3,7),f(9,11)) = 0,f(f(0,6),f(8,10)) = 0, andf(f(f(1,2), 0),f(4,5)) = 0.r(12) = 0, becausef(f(f(3,4), 1),f(f(6,7), 11)) = 0 andf(f(f(2,5),f(9,10)),f(8,12)) = 0.r(13) = 1, becausef(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, andf(0,1) = 1.r(14) = 3, becausef(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, andf(f(0,1), 2) = 3.r(15) = 0, becausef(f(1,4),f(7,8)) = 0,f(f(2,5),f(10,11)) = 0,f(f(3,6),f(13,14)) = 0, andf(f(0,9),f(12,15)) = 0.r(16) = 4, becausef(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, andf(0,2) = 4.r(17) = 3, becausef(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, andf(f(0,1), 2) = 3.r(18) = 3, becausef(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, andf(f(0,1), 2) = 3.r(19) = 4, becausef(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, andf(0,2) = 4.r(20) = 0, becausef(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, andf(f(f(f(f(0,2), 3), 6), 5),f(0,12)) = 0.r(21) = 3, becausef(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, andf(f(0,1), 2) = 3.r(22) = 1, becausef(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, andf(0,1) = 1.r(23) = 0, becausef(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, andf(f(2,7),f(22,23)) = 0.r(24) = 0, by Lemma 4 withn=1.r(28) = 4, becausef(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, andf(0,2) = 4.r(29) = 3, becausef(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, andf(f(0,1), 2) = 3.

This completes the proof of the Theorem.r([19,30]) = 0, becausef(f(f(19,20), 21),f(f(24,25),f(29,30))) = 0 andf(f(0,28),f(f(22,23),f(26,27))) = 0; thereforer(30) =r(18) = 3.

r([20,31]) = 0, becausef(f(f(20,24), 29),f(f(21,25),f(30,31))) = 0 andf(f(0,28),f(f(22,23),f(26,27))) = 0; thereforer(31) =r(19) = 4.

(Equation (4.1) withr({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.

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.

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*+*a*_{1}, ..., *n*+*a _{k}*})
= 0 is not true for all

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-2*i*)*m*, where
*m* = |2*n*+59|. This gives us the set

{*m*, 3*m*, 5*m*, 7*m*, 9*m*,
11*m*, 13*m*, 15*m*, 17*m*, 19*m*, 21*m*,
23*m*, 25*m*, 27*m*,

29*m*, 31*m*, 33*m*, 37*m*,
39*m*, 41*m*, 47*m*, 53*m*, 55*m*, 57*m*}.

Finally, we use

*f*(*f*(5*m*,29*m*),
*f*(47*m*,55*m*)) = 0,

*f*(*f*(7*m*,19*m*),
*f*(37*m*,41*m*)) = 0,

*f*(*f*(17*m*,27*m*),
*f*(53*m*,57*m*)) = 0,

*f*(*f*(23*m*,31*m*),
*f*(33*m*,39*m*)) = 0,

and

*f*(*f*(*f*(*m*,13*m*),
*f*(3*m*,9*m*)), *f*(*f*(11*m*,15*m*),
*f*(21*m*,25*m*))) = 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?

- [EIS] The On-Line Encyclopedia of Integer Sequences, by Neil Sloane,
http://oeis.org
- [L] "Combinatorial Problems and Exercises", by László
Lovász, 1979, North-Holland Publishing Company
- [V] "Fler Matematiska Tankenötter", [Swedish] by Paul Vaderlind, 1996, Svenska Dagbladets Förlags AB

Received February 21, 1999. Published in Journal of Integer Sequences March 15, 1999.

Return to