During one of company meetings, a co-worker raised an interview question that aroused my intense interest. The question goes like this:
Given a positive integer N, how many different ways can one express it as a sum of consecutive integers?
The question¶
For a naive brute force solution, the complexity of the algorithm is obviously O($N^2$). With some optimization, he was able to get to a O(N) performance improvement.
For me, intuitively, this is a math problem. It immediately aroused my interest in looking at this problem in more details. With a little bit mathematical derivation, it appears that I can solve the question with a complexity of $O(\sqrt{N})$.
But before I present my algorithm, let me first clarify a couple of edge cases.
- The number $N$ can be obviously expressed as a $sum$ of the single number $N$ itself. I would like to exclude this trivial case.
- For the set of consecutive integers, we assume the integers will have to be positive.
Thus the original question can be stated more precisely as:
Given a positive integer N, how many different ways can one express it as a sum of more than one consecutive positive integers?
The derivation¶
Let’s denote the consecutive numbers summation expression as:
$$ m\ +\ (m+1)\ +\ …\ +\ (m+n-1) $$
where $$ m > 0\ ,\ n > 1 $$
then we have
$$ N\ = \ m\ +\ (m+1)\ +\ …\ +\ (m+n-1) $$
or $$ N\ =\ mn + (1\ +\ 2\ +\ …\ +\ (n-1))\ =\ mn+\frac{n(n-1)}{2}$$
or $$ N=n(m + \frac{n-1}{2})$$
The question can be now rephrase as:
How many different positive integer pairs we can find for $m$ and $n$ satisfying:
$$N=n(m + \frac{n-1}{2}),\ \ \ \ \ m>0,n>1\ \ \ \ (1)$$
Since $m$ is a positive integer $(m \ge 1)$, we have
$$ N \ge n(n+1)/2$$ or $$ n^2+n-2N \le 0$$
This leads to
$$1\lt n \le \frac{\sqrt{8N+1}-1}{2}\ \ \ \ \ (2)$$
Inequalities (2) effectively limits the possible values of $n$. We still need to find the value of $m$ given a $n$ satisfying inequalities (2). We will then consider two different cases.
If $n$ is an odd number
then $\frac{n-1}{2}$ is an integer. For $n$ to be a solution of equation (1), $n$ MUST be a factor (divisible) of the number $N$. And if $n$ is indeed a factor of $N$, and $n$ satisfy inequalities (2), then a positive integer $m$ is available to satisfy equation (1).
If $n$ is an even number , then we can rewrite equation (1) as equation (3):
$$ 2N=n(2m+n-1)\ \ \ \ \ (3)$$
Because $n$ is assumed to be an even number, $2m+n-1$ would be an odd number. Thus the number $n$ must be a factor of $2N$ and it MUST contain all the exponents of 2 in $2N$ (so that $\frac{2N}{n}$ is odd). Again, inequalities (2) must be satisfied to find a viable $m$ given $n$.
The algorithm¶
Summarizing the above two cases, we get the following algorithms:
- Let $P=\lfloor \frac{\sqrt{8N+1}-1}{2} \rfloor$
- Find the set $O$ of all the odd factors of $N$ between 3 and $P$ inclusive
- Denote the maximum exponents of 2 in $N$ as $e$, and let $q=2^{e+1}$
- Add $q$ into the set $E$ if $q \le P$. For each element $o$ in $O$, if $oq \le P$, then add $oq$ into the set $E$
- The number of elements in $O$ and $E$ determines the number of summation expressions for $N$.
- If we want to further identify the summation expressions: for each element in $O$ and $E$, use $m=\frac{N}{n}-\frac{n-1}{2}$ to find corresponding $m$.
The codes¶
Python code would be the following:
import numpy as np
def get_consecutive_sum_n_values(N):
P=int(np.floor((np.sqrt(8*N+1)-1)/2))
# odd factors of N
n_values = [o for o in range(3, P+1, 2) if (N % o == 0)]
# maximum exponent of 2 in 2N
q = 1
while q <= N and N % q == 0:
q <<= 1
# even factors
if q <= P:
n_values.extend([q * o for o in n_values if (o * q <= P)])
n_values.append(q)
return n_values;
def print_consecutive_sum_expression(N):
n_values = get_consecutive_sum_n_values(N)
print('expressions for:', N)
for n in n_values:
m = int((2*N - n*(n-1))/2/n)
if n == 2:
print(' ', n, 'integers: (',m, '+', m+n-1, ')')
else:
print(' ', n, 'integers: (',m, '+ ... +', m+n-1, ')')
Some testing codes:
print_consecutive_sum_expression(9)
print_consecutive_sum_expression(15)
print_consecutive_sum_expression(100)
print_consecutive_sum_expression(1000000)
Further discussions¶
Simplificatio of the algorithm¶
The algorithm above is simple enough, and it has less than 10 lines of codes. However, with further mathematical analysis, it is possible to further simplify the above algorithm.
Let’s first relax the requirement of $m$ being positive. Let’s allow $m$ to take value of negative integers or zero. We then have the following observations:
- Note: $$ (-p)\ +\ (-p + 1)\ +\ …\ +\ 0\ +\ …\ +\ (p-1)\ +\ p\ +\ (p + 1)\ +\ …\ +\ (p + n – 1)\ ==$$ $$(p + 1)\ +\ …\ +\ (p + n – 1)$$ $$where\ p \ge 0 $$ We can state that we can convert the summation of a consecutive sequence of integers that starts with a non-positive integer into a summation of the mapping consecutive sequence of integers that starts with a positive integer.
- Note: $$(p + 1)\ +\ …\ +\ (p + n – 1)\ ==$$ $$ (-p)\ +\ (-p + 1)\ +\ …\ +\ 0\ +\ …\ +\ (p-1)\ +\ p\ +\ (p + 1)\ +\ …\ +\ (p + n – 1)\ ==$$ $$where\ p \ge 0 $$ We can state that we can convert the summation of a consecutive sequence of integers that starts with a positive integer into a summation of the mapping consecutive sequence of integers that starts with a non-positive integer.
- Summarizing the above two observations, we come to the conclusion that summation sequences have a one-to-one mapping relationship between those start with positive integers and those start with non-positive integers. Or we can say:
Relaxing the requirement of $m \gt 0$, the number of viable sequences that starts with positive integers is the same as the number of viable sequences with non-positive integers. Both are half of the total number of viable sequences.
Please note that in the above conversions, we added or removed $2p+1$ number of integers. So if the number of elements of the sequence before conversion (think $n$) is odd or even, the number of elements of the sequence after conversion will be even or odd respectively. Thus we have:
With the requirement of $m \gt 0$ relaxed, the number of viable sequences with odd number of elements is the same as the number of viable sequences with even number of elements. Both are half of the total number of viable sequences.
Combining the above two bold observations, we get:
The number of viable sequences starting with positive integers is the same as the number of viable sequences containing odd number of elements.
So the original questions becomes: Without requiring $m$ to be positive, how many pairs of $m$ and $n$ we can find for the following equation: $$N=n(m + \frac{n-1}{2}),\ \ \ \ \ n>1\ and\ n\ is\ odd\ \ \ \ (4)$$
It should be easy to see that the answer is exactly: the number of odd factors of the given $N$.
Please note once you get a negative $m$ out of the $m=\frac{N}{n}-\frac{n-1}{2}$, you need to follow the conversion procedure to get the sequence that starts with a positive integer.
Simplified algorithm¶
import numpy as np
def get_consecutive_sum_n_values_simplified(N):
# odd factors of N
return [o for o in range(3, N+1, 2) if (N % o == 0)]
def print_consecutive_sum_expression_simplified(N):
n_values = get_consecutive_sum_n_values_simplified(N)
print('expressions for:', N)
for n in n_values:
m = int((2*N - n*(n-1))/2/n)
if m <= 0:
n -= (-m*2+1)
m = (-m + 1)
if n == 2:
print(' ', n, 'integers: (',m, '+', m+n-1, ')')
else:
print(' ', n, 'integers: (',m, '+ ... +', m+n-1, ')')
The same testing codes:
print_consecutive_sum_expression_simplified(9)
print_consecutive_sum_expression_simplified(15)
print_consecutive_sum_expression_simplified(100)
print_consecutive_sum_expression_simplified(1000000)
Comparing the two algorithms¶
The simplified algorithm in Python only takes one line of codes. However in terms of the computational complexity, the simplified algorithm is actually worse with a performance of $O(N)$.
However, if we are smart in finding the odd factors instead of using the brute force method, the simplified algorithm will be at the same complexity with the algorithm given prior.