11
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – postmortes Mar 3 at 12:49
  • $\begingroup$ @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? $\endgroup$ – VirtualUser Mar 3 at 12:54
  • $\begingroup$ 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 $\endgroup$ – postmortes Mar 3 at 12:56
  • $\begingroup$ but for example $3> 16/6 > 2$ and 16 is not equal to 2+3 $\endgroup$ – VirtualUser Mar 3 at 12:59
  • $\begingroup$ 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$). $\endgroup$ – postmortes Mar 3 at 13:01
15
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – eyeballfrog Mar 4 at 0:35
  • 1
    $\begingroup$ @eyeballfrog, correct. $\endgroup$ – Ennar Mar 4 at 1:05
4
$\begingroup$

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<n$ 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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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)"];
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$;

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.