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$
11
  • 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 '19 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$ – user617243 Mar 3 '19 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 '19 at 12:56
  • $\begingroup$ but for example $3> 16/6 > 2$ and 16 is not equal to 2+3 $\endgroup$ – user617243 Mar 3 '19 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 '19 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$
2
  • 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 '19 at 0:35
  • 1
    $\begingroup$ @eyeballfrog, correct. $\endgroup$ – Ennar Mar 4 '19 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$
0
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