Unproperty of the Powers of 2

The powers of 2 have several unique properties. For example, the integer iterations on a circle that generate Ducci's sequence always settle to all zeros in a finite number of steps only if the starting sequence counts the number of terms which is a power of 2. Also, only for the sets whose size is a power of two, the multisets formed by the sum of pairs of elements may be equal. There are of course additional properties.

A curious result has been published 2007 that deals with a property common to all natural numbers, except for the powers of 2. The author sets out to answer the following question:

And the answer is: all natural numbers, but the powers of 2. The answer bears some musings. For, it is clear that a set and its complement carry exactly the same amount of information. A number may or may not be the sum of two or more consecutive integers. Those that are form a set and those that are not form its complement. The elements of the former possess the property of being the sum of two or more consecutive integers; the elements in the complement do not possess that property. The absence of this particular property is a characteristic feature of the powers of 2. So the powers of 2 do possess a property which is the absence of the property in question. May we not declare the absence of a property unproperty? Which is of cause a property in its own right. Does not this remind one of the Epimenides' paradox?

To get a taste for the problem, consider a few examples.

	1,	2,	3 = 1 + 2,	4,
	5 = 2 + 3,	7 = 3 + 4,	8,
	9 = 4 + 5,	10 = 1 + 2 + 3 + 4,	11 = 5 + 6,	12 = 3 + 4 + 5,
	13 = 6 + 7,	14 = 2 + 3 + 4 + 5,	15 = 7 + 8,	16.

The 2-term sums for odd numbers are pretty obvious: 2n + 1 = n + (n + 1). The constructs for the even numbers are not so easily classified. Still, clearly the powers of 2 stand out.

Theorem

Proof

For convenience, we shall call a representation of a number into the sum of consecutive integers decomposition. The number of terms in the decomposition is its length. A decomposition that consists of a single term is trivial. A decomposition of an odd (even) length is called odd (even). As an example, number 15 has three odd decompositions (15), (4, 5, 6), and (1, 2, 3, 4, 5), and one even, (7, 8).

For the proof, we shall construct a 1-1 correspondence between the odd factors of number N and its decompositions. Since the powers of 2 (and only them) have no odd factors, this will prove the theorem.

So let k be an odd factor of N. The k integers

-(k - 1)/2, ..., 0, ..., (k - 1)/2

add up to 0. Adding to each N/k produces k numbers

(1)	N/k - (k - 1)/2, ..., N/k, ..., N/k + (k - 1)/2

that add up to N. We have to consider two cases depending on whether the first term in the so obtained decomposition is negative or not.

	1.	N/k - (k - 1)/2 > 0. In this case, we already have a valid decomposition.
	2.	N/k - (k - 1)/2 ≤ 0. In this case, we may drop 0, if one is present, and cancel negative terms on the left of the sum with their positive counterparts across 0. Since the first term in (1) N/k - (k - 1)/2 will have to be canceled with (k - 1)/2 - N/k, the first positive term left over will be (k - 1)/2 - N/k + 1, starting the decomposition

(2)	(k - 1)/2 - N/k + 1, (k - 1)/2 - N/k + 2, ..., N/k + (k - 1)/2,

which is even of length 2N/k. Indeed, the number of terms that have been dropped equals 2[(k - 1)/2 - N/k] + 1 = k - 2N/k, while the length of the decomposition in (1) is k.

We now need to show that every decomposition of N is in one of the forms, (1) or (2). Let (a + 1, a + 2, ..., a + m) be a decomposition of N for some a and m. Since this decomposition adds up to m(2a + m + 1)/2, and the factors m and (2a + m + 1) are of different parities, only one of them is odd. And, since this is a decomposition of N, only of them is an odd factor of N. If m is odd then the decomposition is of kind (1) of length m. If m is even, then m = 2N/k, where k = 2a + m + 1, giving a decomposition of kind (2) of length 2N/(2a + m + 1) = m.

The proof is complete. But let's reformulate what has been proved. Observe that the condition N/k > (k - 1)/2 is equivalent to 2N/k > (k - 1); and, since k is odd while 2N/k is even, it is equivalent to 2N/k > k, i.e., k < √2N. Similarly, the condition N/k ≤ (k - 1)/2 is equivalent to 2N/k ≤ (k - 1), i.e., 2N/k < k, or k > √2N, which leads to the following

Theorem

There is a one-to-one correspondence between the odd factors of a natural number N and its decompositions. More precisely, for each odd factor k of N, if k < √2N, then (1) is an odd decomposition of N of length k. If k > √2N, then (2) is an even decomposition of N of length 2N/k. Moreover, these are all the decompositions of N.

In particualr, the number of decompositions of a number equals the number of its odd factors. For example, 15 = 3·5 has 4 odd factors: 1, 3, 5, 15, of which only the last satisfies 15 > √2·15 which corresponds to the even decomposition of length 2: 7 + 8. The rest correspond to odd decompositions. k = 1 gives a trivial decomposition {15}. k = 3 gives a decomposition of length 3: 4 + 5 + 6. 5 gives a decomposition of length 5: 1 + 2 + 3 + 4 + 5.

Triangular numbers n(n + 1)/2, of course, always have an odd factor and a posteriori can't be a power of two. (Triangular numbers may be square but never a power of 2.) If a natural number is neither triangular nor a power of 2, it is a difference of two triangular numbers.

References

1. Wai Yan Pong, Sums of Consecutive Integers, THE COLLEGE MATHEMATICS JOURNAL, VOL. 38, NO. 2, MARCH 2007

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny