mixedmath

After my previous posts (I, II) on perfect partitions of numbers, I continued to play with the relationship between compositions and partitions of different numbers. I ended up stumbling across the following idea: which numbers can be represented as a sum of consecutive positive integers? This seems to be another well-known question, but I haven't come across it before.

First of all, I note that without the restriction to positive integers, this problem is trivial - every integer n is clearly the sum of the integers $ -(n-1), -(n-2), ..., 0, 1, ..., n-1, n$. So we restrict ourselves to sums of consecutive positive integers instead.

Here is the claim:

A number $ n$ can be written as the sum of consecutive positive integers if and only if $ n$ is not a 2-power.

I will present two different proofs of the claim.

First Proof

I think of this as a clever proof. Consider the averages of a consecutive set of positive integers. The average is the sum of the first and last number, divided by 2. Further, the sum of the sequence is the product of the average and the number of elements. We have two possibilities - we either have an even number of elements that we are summing over, or an odd number.

First suppose there are an even number of elements. In this case, either the first element or the last element is odd, and the other is even. Then the sum of the series is the product of an even integer and some number that has a fractional part of 1/2 (as the average of an odd element and an even element has a half-integer fractional part). If we divide the first term by 2 and multiply the second term by 2, and we note that twice a number with a half-integer fractional part is odd, then we see that the overall sum has an odd factor.

Now suppose that there are an odd number of elements. In this case, the average of the first and last integers is just an integer, and so the overall sum contains an odd factor.

So we have that no 2-power is a sum of a consecutive set of positive integers, as they are the numbers that contain no odd factors. We can explicitly construct a consecutive set of positive integers that sum to every other integer. Suppose the integer has an odd factor, and so is of the form $ (2k+1)*(n)$. Then this number is the sum of the integers $ n-k, n-k+1, ... , n+k-1, n + k$.

And so we are done.

Second Proof

This is what I consider a very suggestive proof, and is the source of inspiration for the aforementioned terrible factoring algorithm. In this, we will duplicate the work of Wai Yan Pong, a professor at California State University. We will establish a one to one correspondence between the odd factors of a number and the consecutive sets of positive integers that sum to that number.

Suppose $ k$ is an odd factor of $ n$. Then since the sum of the integers from $ \dfrac{-(k-1)}{2} to \dfrac{(k-1)}{2}$ is 0, we can add $ n/k$ to each of them so that the overall sum is $ n$. If $ \dfrac{-(k-1)}{2} < \dfrac{n}{k}$, then all the terms in the sum are positive and so we have a set of consecutive positive integers of length k. If $ \dfrac{-(k-1)}{2} > \dfrac{n}{k}$, then the set starts with either a zero or a negative number, which means that after dropping the zero and cancelling the negative terms with their positive variants, we are left with the sequence $ {k-1}/2 - n/k + 1, ..., n/k + {k-1}/2$. This has an even number of terms (since we disregarded the 0) and has length $ \dfrac{2n}{k}$.

Now we consider the other direction. Suppose that $ k + 1, k+2, k+3, ..., k+ m$ is a series of consecutive integers that sums to the integer n. Since the sum is n, we have that $ m*(2k + m + 1)/2 = n$. Either $ m$ or $ 2k+m+1$ is an odd factor of n, and it can be verified that the set of consecutive integers is the one associated with this factor, similar to the work above.

So we have a one to one correspondence between the sets of consecutive integers that add up to an odd number n and the odd factors of n. In particular, if one finds such a set of even length l, then the number l divides 2n (and as long as the length is more than 2, this reveals a nontrivial factor of n). And if the length is odd, then l is a factor of n (and as long as it's not the trivial sequence, i.e. n itself, it leads to a nontrivial factor).

The interesting(ly terrible) factoring algorithm

And now we arrive at the promised factoring algorithm (for an odd number - just go ahead and divide all the 2's out). Of course, we can already see that it's one of the least efficient factoring algorithms conceivable. How does one do this as 'efficiently' as possible? One might think that you should start at 1 and add up numbers until one either reaches n or passes n - if one hits n, we've found a factor, and if not, then start at 2 and move on. Conceivably, one might need to do this until one hits about n/2 - far worse than trial division.

But this is not to despair! There are potentially interesting things that can be done modulus the lengths of a particular series. Suppose one notates the sum of the first l terms by $ S_l$, in the style of other partial sums. What one should do is check to see if $ S_l \cong 0 mod(l). If it is not, then it is impossible for any sequence of length l to sum to n, and thus impossible for l (if l is odd) or l/2 (if l is even) to divide n. Further, one only needs to check prime lengths and twice prime lengths. Similarly, one needs only to check up to root n (and twice root n) - so this is actually roughly on par with trial division.

It is more interesting and efficient than it might appear! Of course, this is still slow. Very slow. But it's very interesting.

Leave a comment

Comment via email