Find the number of ways to express 1050 as sum of consecutive integers

I have to solve this task:

Find the number of ways to present $$1050$$ as sum of consecutive positive integers.

I was thinking if factorization can help there: $$1050 = 2 \cdot 3 \cdot 5^2 \cdot 7$$ but I am not sure how to use that information (if there is a sense)

example

I can solve something similar but on smaller scale:

\begin{align} 15 &= 15 \\ &= 7+8 \\ &=4+5+6 \\ &= 1+2+3+4+5 \end{align}

($$4$$ ways)

• so the next step is to work out what you're doing in general. To get $15=7+8$ you are dividing by $2$ and hoping not to get an integer so that you can take the integers either side. If that doesn't work you'd look to divide by $3$ to get three integers, etc. Can you take it from there? – postmortes Mar 3 at 12:49
• @postmortes chmmm I think that if I divide by odd number ($m$) and I get integers, then I should take $(m-1)/2$ integers from right and the same number integers from left site. But if I divide by even number ($m$) and get non-int then I should get two numbers? – VirtualUser Mar 3 at 12:54
• Yes, and then you can repeat that with each of the smaller numbers and look for a formula to work out how many times you can do it – postmortes Mar 3 at 12:56
• but for example $3> 16/6 > 2$ and 16 is not equal to 2+3 – VirtualUser Mar 3 at 12:59
• if you're dividing by $6$ you're looking to represent 16 as the sum of 6 consecutive integers (which you can't do since $1+2+3+4+5=15$). – postmortes Mar 3 at 13:01

We want to find the number of solutions of $$n+(n+1)+\ldots + (n+k) = 1050,\ n\in\mathbb Z_{>0},\ k\in\mathbb Z_{\geq 0}.\tag{1}$$

Rewrite the sum as $$n(k+1) + 0 + 1 +\ldots + k = n(k+1) + \frac{k(k+1)}{2}= \frac 12(2n+k)(k+1).$$

Thus, the number of solutions to $$(1)$$ is the same as the number of solutions of $$(2n+k)(k+1) = 2100,\ n\in\mathbb Z_{>0},\ k\in\mathbb Z_{\geq 0}.\tag{2}$$

Let $$a$$ and $$b$$ be divisors of $$2100$$ such that \begin{align} 2n+k &= a,\\ k+1 &= b.\tag{3} \end{align} Solving it we get \begin{align} n &= \frac{a-b+1}2,\\ k &= b -1.\tag{4} \end{align}

From here we see that not every choice of integers $$a$$ and $$b$$ such that $$ab = 2100$$ will give us a solution to $$(2)$$. Since $$a-b+1$$ must be even, $$a$$ and $$b$$ are of opposite parities. Also, $$a\geq b > 0$$ since $$n> 0$$ and $$k \geq 0$$.

First determine the number of ways to factor $$2100 = 2^2\cdot 3\cdot 5^2 \cdot 7$$ such that one of the factors is odd. For this to be fulfilled, we shouldn't allow $$4 = 2^2$$ to be factored, so consider $$2100 = 4\cdot 3 \cdot 5^2 \cdot 7$$ instead. Thus, there are $$2\cdot 2\cdot 3\cdot 2 = 24$$ positive integral solutions to $$2100 = a'b'$$ such that one factor is odd. Because of commutativity, it means there are $$12$$ distinct ways to factor $$2100$$ into product of two factors, one of which is odd, and for every such factorization there is a unique choice for $$a$$ and $$b$$ such that $$a\geq b$$.

Thus, there are $$12$$ positive integral solutions to $$(2)$$.

• I believe this argument generalizes to show that the number of ways to write any number $n$ as consecutive positive integers is $\prod (e_i+1)$, where the $e_i$ are the exponents of all odd primes in $n$'s prime factorization. – eyeballfrog Mar 4 at 0:35
• @eyeballfrog, correct. – Ennar Mar 4 at 1:05

The sum of the first $$n$$ natural numbers is $$\sum_{i=0}^ni=\frac12n(n+1).$$ So by subtracting the first $$m-1$$ terms we get the sum of all consecutive integers from $$m$$ to $$n$$; $$\sum_{i=m}^ni=\frac12n(n+1)-\frac12(m-1)m=\frac12(n+m)(n-m+1).$$ To count the number of ways to write a number $$k$$ as a sum of consecutive integers, we want to find natural numbers $$m$$ and $$n$$ with $$m such that $$(n+m)(n-m+1)=2k.$$ In particular this gives a factorization of $$2k$$. Conversely, if $$2k=a\times b$$ is a factorization where $$a\not\equiv b\pmod{2}$$ then setting $$m:=\frac{a-b+1}{2}\qquad\text{ and }\qquad n:=\frac{a+b-1}{2},$$ gives $$(n+m)(n-m+1)=2k$$. This shows that if $$k=2^lk'$$ with $$l\in\Bbb{N}$$ and $$k'$$ odd, then the expressions of $$k$$ as a sum of consecutive integers correspond $$2$$-to-$$1$$ to the divisors of $$k'$$; for each divisor $$d$$ of $$k'$$ we have the two factorizations $$2k=d\times\left(2^l\frac{k'}{d}\right)=\left(2^ld\right)\times\frac{k'}{d},$$ of $$2k$$ into an even and an odd number. The corresponding sums include the trivial sum $$k=\sum_{i=k}^ki$$, as well as sums with negative integers. This shows that the total number of ways to represent a number $$k$$ as a sum of consecutive integers, is twice the number of divisors of $$k'$$.

The number of expressions of $$k$$ as a sum of positive integers is the number of factorizations for which $$m\geq0$$, or equivalently $$a+1\geq b$$. Of course for every factorization $$2k=a\times b$$ with $$a\neq b$$ we have either $$a+1\geq b$$ or $$b+1\geq a$$ exclusively, so if $$2k$$ is not a square then precisely half of all expressions involve only positive integers.

In this particular case $$k=1050=2\cdot3\cdot5^2\cdot7$$ and so $$k'=525=3\cdot5^2\cdot7$$, and the number of divisors of $$k'$$ equals $$2\times3\times2=12$$, so there are $$12$$ expressions of $$k$$ as a sum of positive integers. The factors of $$k'$$ and corresponding sums are $$\begin{eqnarray*} \text{factor}&&\qquad&&\text{sums}\\ \hline 1&&\qquad&&k=\sum_{i=1050}^{1050}i &&\qquad&&k=\sum_{i=261}^{264}i\\ 3&&\qquad&&k=\sum_{i=349}^{352}i &&\qquad&&k=\sum_{i=82}^{93}i\\ 5&&\qquad&&k=\sum_{i=208}^{212}i &&\qquad&&k=\sum_{i=43}^{62}i\\ 7&&\qquad&&k=\sum_{i=147}^{153}i &&\qquad&&k=\sum_{i=24}^{51}i\\ 15&&\qquad&&k=\sum_{i=63}^{77}i &&\qquad&&k=\sum_{i=-12}^{47}i\\ 21&&\qquad&&k=\sum_{i=40}^{60}i &&\qquad&&k=\sum_{i=-29}^{54}i\\ 25&&\qquad&&k=\sum_{i=30}^{54}i &&\qquad&&k=\sum_{i=-39}^{60}i\\ 35&&\qquad&&k=\sum_{i=13}^{47}i &&\qquad&&k=\sum_{i=-62}^{77}i\\ 75&&\qquad&&k=\sum_{i=-23}^{51}i &&\qquad&&k=\sum_{i=-146}^{153}i\\ 105&&\qquad&&k=\sum_{i=-42}^{62}i &&\qquad&&k=\sum_{i=-207}^{212}i\\ 175&&\qquad&&k=\sum_{i=-81}^{93}i &&\qquad&&k=\sum_{i=-348}^{351}i\\ 525&&\qquad&&k=\sum_{i=-260}^{264}i &&\qquad&&k=\sum_{i=-1049}^{1050}i\\ \end{eqnarray*}$$ We see that indeed $$12$$ out of these $$24$$ expressions involve only positive integers.

For the sum of next integer we may use formula for the sum of arithmetic sequence

$$\sum_{k=1}^na_k=\frac n2(a_1+a_n)$$

So

\begin{aligned} 1050 &= \frac n2(a_1+a_n) \\ 2100 &= n(a_1+a_n) \\ 2100&= n(a_1+a_n) \\ 2100&= n(a_1+a1+(n-1)) \\ 2^2\cdot3\cdot5^2\cdot7&= n(2a_1+n-1) \end{aligned}

Now:

1. If $$n$$ is even, then $$(2a_1+n-1)$$ is odd, so $$n=2^2\cdot3^x\cdot5^y\cdot7^z$$ where $$x \in \{0,1\},\; y \in \{0,1,2\}, \;z \in \{0,1\}$$,
so there are $$2 \times 3 \times 2 = 12$$ possibilities for $$n$$.

2. If $$n$$ is odd, then similarly $$n=3^x\cdot5^y\cdot7^z$$

and we obtain other $$12$$ possibilities for $$n$$.

So there are $$24$$ solutions altogether, a half o them, i. e. $$\color{red}{12}$$, for only positive integers, because for positive integers must be $$a_1 \ge 1$$, and consequently $$(2a_1+n-1) >n$$, so in the product $$n(2a_1+n-1)$$ the first multiplier have be smaller than the second one.

Using the MiniZinc solver with Gecode, I got the following $$12$$ solutions:

13 .. 47
24 .. 51
30 .. 54
40 .. 60
43 .. 62
63 .. 77
82 .. 93
147 .. 153
208 .. 212
261 .. 264
349 .. 351
1050 .. 1050


The model:

var 1..1050: k0;
var 0..1050: k1;

constraint
(1050 == sum([k0 + k | k in 0..k1]));

solve satisfy;

output ["\n\(k0) .. \(k0+k1)"];


Here's how you use that information:

1050 has divisors:

$$1,2,3,5,6,7,10,14,15,21,25,30,35,42,50,70,75,105,150,175,210,350,525,1050$$ You can use the prime factorization to check this. You then say 1050 divided by 3 gives 350 so 349+350+351 adds up to 1050. Time to make sums (odd divisors and 4 thrown in, because it lands on a half integer). This gives you: $$\begin{eqnarray}1050=349+350+351\\1050=261+262+263+264\\1050=208+209+210+211+212\\1050=147+148+149+150+151+152+153\\1050=63+64+65+66+67+68+69+70+71+72+73+74+75+76+77\\1050=40+41+42+43+44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60\\1050=30+31+32+33+34+35+36+37+38+39+40+41+42+43+44+45+46+47+48+49+50+51+52+53+54\end{eqnarray}$$

Okay, I may be missing a few. It gets the point across though.

One way is to note that if there are an odd number, $$2n+1$$ of terms with the middle term $$k$$ then the sum of consecutive terms will add to $$(2n+1)k$$.

[Because there are $$2n+1$$ terms and they average $$k$$]

And if there are an even number, $$2n$$ of terms with the middle two terms $$k$$ and $$k+1$$ then the sum of consecutive terms will add to $$2n(k + \frac 12) = n(2k + 1)$$.

[Because there are $$2n$$ terms and they average $$k+\frac 12$$]

But if we can't have negative terms we must have $$k\ge n$$.

And so we can have either:

$$1050 = k(2n+1); k> n$$ can be a sum of $$2n+1$$ consecutive terms centered at $$k$$ (i.e. $$(k-n) + (k-n+1) + ..... +(k+n-1)+ (k+n)$$ ) or

$$1050 = n(2k+1); n\le k$$ can be a sum of $$2n$$ consecutive terms centered at $$k$$ and $$k+1$$ (i.e $$(k-n+1)+ ..... + (k+n)$$.)

And so

$$1050 = 1050*1 = k(2n+1) \implies 1050 = 1050$$; one consecutive term centered at $$1050$$(maybe allowed)

$$1050 = 2*525 = n(2k+1) \implies 1050 = 261+262+263+264$$; four consectutive terms centered at $$262$$ and $$263$$.

$$1050 = 350*3 = k(2n+1) \implies 1050= 349 + 350 + 351$$; three consecutive terms centered at $$350$$.

etc.

And we can partition $$1050 = even*odd$$ in... well....

$$1050 = even*odd = (2*3^a5^b7^c)*(3^{1-a}*5^{b-2}*7^{c-1});a=0,1;b=0,1, 2;c=0, 1$$ ...

That would be in $$2*3*2 = 12$$ ways.

i.e.

$$1050 = 1050*1=k(2n+1) = 1050$$;

$$1050 = 2*525=n(2k+1) = 261+262+263+264$$;

$$1050 = 350*3=k(2n+1) = 349 + 350 + 351$$;

$$1050 = 210*5 =k(2n+1)= 208+209+210+211+212$$;

$$1050 = 6*175=n(2k+1)= 163 + 164+ ..... + 186 + 187$$;

......

$$1050 = 30*35= k(2n+1) = 13 + 14 + ..... + 46 + 47$$;