10
$\begingroup$

Consecutive Numbers Sum (or $CNS$) is the number of different consecutive positive integers' summation resulting to a specific number. For example;

$CNS(45)=5$

  1. $22+23=45$
  2. $14+15+16=45$
  3. $7+8+9+10+11=45$
  4. $5+6+7+8+9+10=45$
  5. $1+2+3+4+5+6+7+8+9=45$

$CNS (945)=?$ and $CNS (947)=?$

Hint: You do not have to find every single of them to get the result!

$\endgroup$
  • 1
    $\begingroup$ I am not sure why someone voted to close but this is a puzzle question which requires logic deduction to find the result without finding every single consective numbers to sum. $\endgroup$ – Oray Dec 24 '16 at 19:35
  • 2
    $\begingroup$ Why 45 = 45 does not count as a 6th possibility? $\endgroup$ – Oriol Dec 24 '16 at 20:03
  • $\begingroup$ @Oriol this is how it is defined :) there is no consecutiveness for a single number. $\endgroup$ – Oray Dec 24 '16 at 20:30
  • 2
    $\begingroup$ It's a close call TBF. The question (along with many others from the same poster) wouldn't look out of place in the math sub one bit, and I personally wouldn't ask such a question here, but it doesn't completely go against the point of puzzling. $\endgroup$ – Nautilus Dec 24 '16 at 20:41
  • $\begingroup$ @Nautilus you never asked a question anyway :) just kidding though. $\endgroup$ – Oray Dec 24 '16 at 21:06
8
$\begingroup$

Here's some math; thanks to Gauss we know that 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 an odd 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 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$. By some kind of magic everything falls into place:

  • Because $k$ is odd $2$ divides precisely one of $a$ and $b$, so $m$ and $n$ are integers.
  • Because $b\geq1$ we have $m\leq n$.
  • Because $k$ is odd $2k$ is not a square, so $a\neq b$. Swapping $a$ and $b$ if necessary we get $m\geq 1$.

This shows that half of all factorizations of $2k$ give natural numbers $m$ and $n$ such that $\sum_{i=m}^ni=k$. The number of factorizations is the same as the number of divisors, and the number of divisors of $2k$ is twice the number of divisors of $k$, because $k$ is odd. So the number of ways to write $k=\sum_{i=m}^ni$ equals the number of divisors of $k$, often denoted $\sigma_0(k)$. We don't want the trivial sum $k=\sum_{i=k}^ki$, so we find that $$CNS(k)=\sigma_0(k)-1,$$ where $\sigma_0$ is the divisor counting function. Using the linked formula for $\sigma_0$, the prime factorizations $$945=3^3\times5\times7\qquad\text{ and }\qquad947=947,$$ show without any aid from a machine that \begin{align} 945&=\sigma_0(3^3\times5\times7)-1=(3+1)(1+1)(1+1)-1=15\\ 947&=\sigma_0(947)-1=(1+1)-1=1. \end{align}

$\endgroup$
6
$\begingroup$

I got

$CNS(945)=15$ and $CNS(947)=1$.

Short way:

From playing around with other numbers, I noticed that $CNS(n)=o(n)-1$, where $o(n)$ is the number of odd divisors of $n$. I'm not sure how to prove this, but this does give us $CNS(945)=15$ and $CNS(947)=1$ as shown below, since there are sixteen odd divisors of $945$ and only two for $947$ ($1$ and $947$, since it's prime).


Long way:

For $CNS(945)$:

For there to be an odd number of consecutive integers, the average of them (i.e. the number in the middle) must be odd. Thus, we can find all the odd factors of $945$, and what they multiply with to get $945$:

$945 = 3\times315 = 314+315+316$
$945 = 5\times189=187+188+189+190+191$
$945 = 7\times135=132+133+134+135+136+137+138$
$945 = 9\times105=101+102+\cdots+109$
$945 = 15 \times 63=56+57+\cdots+70$
$945 = 21\times 45=35+36+\cdots+55$
$945 = 27\times 35=22+23+\cdots+48$
$945 = 35\times 27=10+11+\cdots+44$

All products after $35\times27$ (i.e. $45\times21$, $63\times15$, etc.) do not work, since there aren't enough positive numbers available on either side of the average number to reach $945$.

For an even number of integers, the average will be $\textrm{something}.5$. Thus, we need to find integer solutions for $m$ and $n$ such that $\frac{945}{m}=n+0.5$. Solving for $m$ and $n$ here, we get the following sums:

$945 = 2\times 472.5=472+473$
$945 = 6\times 157.5=155+156+157+158+159+160$
$945 = 10\times 94.5=90+91+\cdots+99$
$945 = 14\times 67.5=61+62+\cdots+74$
$945 = 18\times 52.5=44+45+\cdots+61$
$945 = 30\times 31.5=17+18+\cdots+46$
$945 = 42\times 22.5=2+3+\cdots+43$

Similar to above, all products after $42\times22.5$ (i.e. $54\times17.5$, $70\times17.5$, etc.) do not work, since there again aren't enough positive numbers available on either side of the average number to reach $945$.

We have eight sums with an odd middle and seven with an even middle, thus $CNS(945)=15$.

For $CNS(947)$:

We can use a similar method to above. First we have to find all the odd factors of $947$, but since $947$ is prime, the only factors are $1$ and $947$. Therefore there are no strings of an odd number of consecutive integers that sum to $947$.
For an even number of integers, we can again use our formula, $\frac{947}{m}=n+0.5$, to find all solutions. Solving this, we find that the only solution that works is $947=2\times473.5=473+474$. This is thus the only way to sum consecutive integers to $947$, and so $CNS(947)=1$.

$\endgroup$
  • $\begingroup$ @Servaes Ay, good work! :) $\endgroup$ – DooplissForce Dec 24 '16 at 22:43
5
$\begingroup$

Formulas

The sum of consecutive integers from n to m is

$\frac{ (n + m) (m - n + 1) }{ 2 } = \frac{ m^2 - n^2 + m + n }{ 2 }$

So we want to count

$\# \{ (n,m) \in \mathbb{N}^2: m^2 - n^2 + m + n = 2k \} = \text{CNS}(k)$

Isolating n,

$n^2 - n - m^2 -m + 2k = 0$

$n = \frac{ 1 + \sqrt{4m^2 + 4m - 8k + 1} }{2}$

Since $n$ must be integer, this means $4m^2 + 4m - 8k + 1$ must be a perfect square not divisible by 4.

$4m^2 + 4m - 8k + 1 = (2m + 1)^2 - 8k$

$4m^2 + 4m - 8k + 1 = s^2$, with $s$ odd.

$m = \frac{ -1 + \sqrt{8k + s^2} }{2}$

Again, $8k + s^2$ must be a perfect square: $8k + s^2 = (s+r)^2$.

Also, $8k + s^2$ must not be divisible by 4, granted because $s$ odd.

We can consider $s$ to be positive because $-s$ and $s$ give the same solution, and $0$ is divisible by 4. We can also consider $r$ to be positive.

$8k + s^2 = s^2 + 2sr + r^2$

$8k = 2sr + r^2$

$s = \frac{ 4k }{r} - \frac{r}{2}$

We will have a solution for every $r$ such that

  • $r$ is even.
  • $r$ must divide $4*k$.
  • $\frac{ 4k }{r} \geq \frac{r}{2} \iff r^2 \leq 8k \iff r \leq 2 \sqrt{2k}$
  • For $s$ to be odd, either $r$ not divisible by 4 or $\frac{ 4k }{r}$ odd (e.g. $k$ odd).
  • Case $r = 2$ gives a summation of a single term and is not counted.

Case $k = 45$

So, for $\text{CNS}(45)$, since $4 * 45 = 2^2 * 3^2 * 5$ and $\lfloor 2 \sqrt{2*45} \rfloor = 18$

  • $r = 2 \implies s = 89 \implies m = 45 \implies n = 45$, ignored.
  • $r = 2^2 = 4 \implies s = 43 \implies m = 23 \implies n = 22$
  • $r = 2*3 = 6 \implies s = 27 \implies m = 16 \implies n = 14$
  • $r = 2*5 = 10 \implies s = 13 \implies m = 11 \implies n = 7$
  • $r = 2^2*3 = 12 \implies s = 9 \implies m = 10 \implies n = 5$
  • $r = 2*3^2 = 18 \implies s = 1 \implies m = 9 \implies n = 1$
  • The following would be $r = 2^2*5 = 20 > 18$. End.

That's why $\text{CNS}(45) = 5$.

Case $k = 945$

Since $4 * 945 = 2^2 * 3^3 * 5 * 7$ and $\lfloor 2 \sqrt{2*945} \rfloor = 86$,

  • $r = 2 \implies s = 1889 \implies m = 945 \implies n = 945$, ignored.
  • $r = 2^2 = 4 \implies s = 943 \implies m = 473 \implies n = 472$
  • $r = 2*3 = 6 \implies s = 627 \implies m = 316 \implies n = 314$
  • $r = 2*5 = 10 \implies s = 373 \implies m = 191 \implies n = 187$
  • $r = 2^2*3 = 12 \implies s = 309 \implies m = 160 \implies n = 155$
  • $r = 2*7 = 14 \implies s = 263 \implies m = 138 \implies n = 132$
  • $r = 2*3^2 = 18 \implies s = 201 \implies m = 109 \implies n = 101$
  • $r = 2^2*5 = 20 \implies s = 179 \implies m = 99 \implies n = 90$
  • $r = 2^2*7 = 28 \implies s = 121 \implies m = 74 \implies n = 61$
  • $r = 2*3*5 = 30 \implies s = 111 \implies m = 70 \implies n = 56$
  • $r = 2^2*3^2 = 36 \implies s = 87 \implies m = 61 \implies n = 44$
  • $r = 2*3*7 = 42 \implies s = 69 \implies m = 55 \implies n = 35$
  • $r = 2*3^2*5 = 42 \implies s = 69 \implies m = 55 \implies n = 35$
  • $r = 2^2*3*5 = 60 \implies s = 33 \implies m = 46 \implies n = 17$
  • $r = 2*5*7 = 70 \implies s = 19 \implies m = 44 \implies n = 10$
  • $r = 2^2*3*7 = 84 \implies s = 3 \implies m = 43 \implies n = 2$
  • The following would be $r = 2*3^2*5 = 90 > 87$. End.

Therefore,

$\text{CNS}(945) = 15$.

Case $k = 947$

Since $4 * 947 = 2^2 * 947$ and $\lfloor 2 \sqrt{2*945} \rfloor = 87$,

  • $r = 2 \implies s = 1893 \implies m = 947 \implies n = 947$, ignored.
  • $r = 2^2 = 4 \implies s = 945 \implies m = 474 \implies n = 473$
  • The following would be $r = 2*947 = 1894 > 87$. End.

Therefore,

$\text{CNS}(947) = 1$.

In general

Let $k = 2^{a_0} {p_1}^{a_1} {p_2}^{a_2} \dots {p_l}^{a_l}$, where $2, p_1, p_2, \dots, p_l$ are $l+1$ different prime numbers.

$\text{CNS}(k) = \# \left\{ 2^{b_0} {p_1}^{b_1} \dots {p_l}^{b_l} : \begin{array}{c} b_0 \in \{ 1, a_0+2\} \\ 0 \leq b_i \leq a_i \quad \forall i=1,\dots,l \\ 2^{b_0-1} {p_1}^{b_1} \dots {p_l}^{a_l} \leq \sqrt{2*k} \end{array} \right\}$

The last constraint is annoying. But if we remove it we will get the double of solutions, so we can just divide by 2.

Therefore, the closed formula is

$\text{CNS}(k) = \frac{ 2 (a_1+1) \dots (a_l+1)}{2} - 1 = (a_1+1) \dots (a_l+1) - 1$

The $-1$ at the end is because we ignore summations of only one term.

$\endgroup$
  • 1
    $\begingroup$ Your last expression for $\operatorname{CNS}(k)$ has a much nicer closed form; see my answer. $\endgroup$ – Inactive - Objecting Extremism Dec 24 '16 at 22:13
  • $\begingroup$ @Servaes You were right. I had some mistakes, now the formula coincides indeed with the number of odd divisors minus 1. $\endgroup$ – Oriol Dec 25 '16 at 1:29
4
$\begingroup$

We have to count the number of integers $k\ge 2$ for which $n$ can be written as a sum of $k$ consecutive numbers. Certainly, this is only possible if $n\ge 1+2+\dots+k=k(k+1)/2$ is large enough. The other rules are this, which are proved by pictures below.

If $k$ is odd, it can be done iff $n$ is large enough and $n\equiv 0$ (mod $k$).
If $k$ is even, it can be done iff $n$ is large enough and $n\equiv k/2$ (mod $k$).

To compute CNS(945),

Factorize it as 3•5•7•9. From this, we can see it is a multiple of the odd numbers 3, 5, 7, 9, 15, 21, 27, 35, and 45, which are all small enough, and all other odd factors are too large. For an even $k$ to work, $n/k$ must be a half integer, which occurs if $k$ is double one of its odd factors. The ones which are small enough are 2, 6, 10, 14, 18, and 30. This is 15 numbers total.

For CNS(947),

This number is prime. It's only odd factors are itself, which is too large, and 1. The only $k$ which works is then 2•1=2, so CNS(947)=1.


If an number $n$ can be written as the consecutive sum of $k$ numbers, then $n$ is the number of dots in a trapezoidal picture with $k$ rows like this:

••••••••      ^
•••••••••     | 
••••••••••  k rows 
•••••••••••   |
••••••••••••  v

Flipping the below triangle makes a rectangle with $k$ rows, showing $n$ is a multiple of $k$. The transformation can be done in reverse provided there are enough columns, which happens when $n\ge k(k+1)/2$.

••••••••           ••••••••**
•••••••••          •••••••••*
••••••••••     =>  ••••••••••
••••••••••*        ••••••••••
••••••••••**       ••••••••••

If $k$ is even, the same triangle flip results in a rectangle plus half a column.

••••••••           ••••••••**
•••••••••          •••••••••*
•••••••••*     =>  •••••••••
•••••••••**        •••••••••
$\endgroup$
  • $\begingroup$ I was hoping that someone would lay it out like this! $\endgroup$ – humn Dec 24 '16 at 23:33
2
$\begingroup$

Trick

Just add a digit to the existing series

Example

$22+923=945$
$14+15+916=945$
$7+8+9+10+911=945$
$5+6+7+8+9+910=945$
$1+2+3+4+5+6+7+8+909=945$

For the next :

May be do the same as above adding +2 to any number :)

$\endgroup$
  • 1
    $\begingroup$ ^vote with a note: Great trick but it's bound to miss some sums $\endgroup$ – humn Dec 24 '16 at 19:51
  • $\begingroup$ @humn- Yeah. I am on phone. So too slow :) $\endgroup$ – Techidiot Dec 24 '16 at 19:53
  • 1
    $\begingroup$ Doesn't it have to be consecutive? $\endgroup$ – bleh Dec 24 '16 at 20:41
  • 1
    $\begingroup$ The question clearly states that the numbers should be consecutive, so this is not a solution. $\endgroup$ – Inactive - Objecting Extremism Dec 24 '16 at 22:26

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.