39
$\begingroup$

All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example $9$ can be expressed in three such ways, $2+3+4$, $4+5$ or simply $9$. In how many ways can a number be expressed as a sum of consecutive numbers?

In how many ways can this work for $65$?

Here, for $9$ answer is $3$, for $10$ answer is $3$, for $11$ answer is $2$.

$\endgroup$
9
  • $\begingroup$ @BhavikAmbani, this question is like asking if n is a fibonacci number. The solution can be calculated, but it can't be represented by a simple formula, unless you're saying something trivial like $f(n) \Leftrightarrow f(n - 1) + f(n - 2)$ $\endgroup$ – Neil May 2 '12 at 10:37
  • $\begingroup$ @BhavikAmbani: Many things are counted without explicit formulas, like the prime counting function. However, this question is equivalent to the Diophantine(ish?) problem of counting the integer solutions $(a,b)$ with $a<b$ to $$(b+a)(b-a+1)=2n$$ for $n$ given but unknown. $\endgroup$ – anon May 2 '12 at 10:49
  • 1
    $\begingroup$ Please do not engage in excessive discussions in the comments. If you wish to discuss, please use our chatroom instead. I'll be cleaning up the comments here which are wandering a bit off-topic in a minute or so. $\endgroup$ – Willie Wong May 2 '12 at 10:59
  • $\begingroup$ It doesn't come as too hard to prove that there exist a countable infinity of numbers which can get thus expressed in at least two ways. $\endgroup$ – Doug Spoonwood May 2 '12 at 12:12
  • 2
    $\begingroup$ @BhavikAmbani: (fixed bad typo, earlier now deleted comment) The following is a formula quoted from the post I referred to. For the proof please see the post. If $$w=2^{a_0}p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},$$ where the $p_1,p_2,\dots,p_k$ are distinct odd primes, then the number of non-trivial representations of $w$ is $$(a_1+1)(a_2+1)\cdots(a_k+1).$$ $\endgroup$ – André Nicolas May 2 '12 at 17:31
18
$\begingroup$

Here's one more way to calculate this, from my answer to this question on codegolf.SE:*

An integer $n$ is expressible as the sum of $m$ consecutive positive integers if and only if either:

  • $m$ is odd and $\frac nm$ is an integer, or
  • $m$ is even and $\frac nm + \frac12$ is an integer,

and $\frac nm \ge \frac m2$ (or else some of the integers in the sum would be zero or negative).

These conditions follow from the fact that the sum of an arithmetically increasing sequence of $m$ numbers equals $m$ times the mean of the numbers.

The last condition can be rewritten as $m \le \sqrt{2n}$. Thus, it's sufficient to iterate over all integers $m$ from $1$ to $\lfloor \sqrt{2n} \rfloor$ and check whether $\frac nm + \frac m2 + \frac12$ is an integer.


*) The entire Q&A thread has since been deleted; here's an archive.org copy for anyone curious.

$\endgroup$
1
  • 1
    $\begingroup$ Very Good Answer.. +1 for this $\endgroup$ – Bhavik Ambani May 3 '12 at 5:06
14
$\begingroup$

A sum of consecutive numbers is a difference of triangular numbers. The paper below gives a solution for the case of nonconsecutive triangular numbers.

Nyblom, M. A. On the representation of the integers as a difference of nonconsecutive triangular numbers. Fibonacci Quart. 39 (2001), no. 3, 256ā€“263.

The main result is that the number of distinct representations of a nonzero integer $m$ as a difference of nonconsecutive triangular numbers is given by $dāˆ’1$, where $d$ is the number of odd divisors of $m$.

$\endgroup$
2
  • 2
    $\begingroup$ An equivalent statement to that main result is given in the comments on A001227, although without reference. $\endgroup$ – Peter Taylor May 2 '12 at 13:59
  • $\begingroup$ Also explained in an answer by André Nicolas. $\endgroup$ – lhf May 2 '12 at 14:14
6
$\begingroup$

Fix $k$. Is there a way that a number $N$ can be written in more than one way as a sum of $k$ consecutive number? Certainly not because $$ a+(a+1)+\cdots+(a+k-1)\neq b+(b+1)+\cdots+(b+k-1) $$ if $a\neq b$. On the other hand $N$ is the sum of $k$ consecutive number if and only if $N$ is the form $$ N=\frac12\left[(n+k)(n+k+1)-n(n+1)\right] $$ for some $n$. Does that help?

$\endgroup$
3
  • $\begingroup$ Thanks a lot for your efforts, but this does not make any solution for me $\endgroup$ – Bhavik Ambani May 2 '12 at 11:05
  • 1
    $\begingroup$ It was not intended as a solution, but as a hint/help. $\endgroup$ – Andrea Mori May 2 '12 at 12:30
  • $\begingroup$ But sorry I couldn't get your hint till now. $\endgroup$ – Bhavik Ambani May 2 '12 at 12:31
2
$\begingroup$

Factorise the number and find the number of odd factors . Total number of odd factors (except 1) is the answer.

Express N in terms of prime factors

$N = a^p . b^q . c^r$

If a = 2 . Number of odd factors = (q+1)(r+1) - 1 . Note : 1 is subtracted because 1 cannot be answer as consecutive terms means greater than 1 term.

For eg.

$100 = 2^2 . 5^2 $

So Number of odd factors = (2+1) - 1 = 2 = Number of ways of writing 100 as sum of 2 or more consecutive integers . They are
18, 19, 20, 21, 22

9,10,11,12,13,14,15,16

ANSWER:

Number of ways of writing N as sum of consecutive positive integers is Number of odd factors in that number (except 1).

Also see : http://mathblag.wordpress.com/2011/11/13/sums-of-consecutive-integers/

$\endgroup$
2
$\begingroup$

It is a well known fact that $$1+2+\cdots+a=\tfrac12 a(a+1)$$ Thus, $$b+(b+1)+\cdots+a=(1+2+\cdots +a)-(1+2+\cdots (b-1))=\tfrac12(a(a+1)-(b-1)b)$$ Where $a>b>0$. How many solutions does $$2n=a(a+1)-b(b-1)=(a+b)(a-b+1)$$ have? Well, taking two divisors $i,j$ of $2n$ such that $ij=2n$, we want to solve $$a+b=i$$ $$a-b+1=j$$The solutions of this are easy to obtain: $$a=\frac12(i+j-1)$$ $$b=\frac12(i-j+1)$$ For this to be integer solutions, we need $i+j$ to be odd (which also makes $i-j$ odd) Thus, we want to choose $i$ and $j$ in such a way that one is odd and the other is even (thus, the even one must contain all factors $2$ in $2n$). Let now $2^km=2n$ with $m$ odd, then there are exactly as many solutions as there are divisors for $m$ - that is, if we count the number itself as one consecutive integer. Not counting that one, we arrive at the final answer $$\sigma_0(m)$$ where $\sigma_0$ denotes the Divisor Function. Note that $\sigma_0(p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k})=(e_1+1)(e_2+1)\cdots (e_k+1)$ where all $p_i$ are distict prime factors.

$\endgroup$
1
$\begingroup$

I thought of this same question several months ago during one of my classes and I worked out the solution during my lunch break, the same sort of argument could be used to find the number of representations of $n$ in any arithmetic sequence modulo a positive integer. I got that if $S(n)$ denotes the number of representations of $n$ as a sum of successive natural numbers with $n\ge 1$ then that:

$$S(n)=d(\frac{n}{2^{v_2(n)}})$$

Where $v_2(n)$ is the $2$-adic order of $n$, what I did was used the fact that:

$$\sum_{\substack{a^2+ab=n\\(a,b)\in \mathbb{N^2}}}f(a,b)=\sum_{\substack{b=\frac{n}{a}-a\\(a,b)\in \mathbb{N^2}}}f(a,b)=\sum_{\substack{d\mid n\\d<\sqrt{n}}}f(d,\frac{n}{d}-d)$$

To rewrite: $$S(n)=\sum_{\substack{a+(a+1)+(a+2)+\dots +(b-1)+b=n\\b\ge a\\(a,b)\in \mathbb{N^2}}}1=\sum_{\substack{(a+b)(a-b+1)=2n\\b\ge a\\(a,b)\in \mathbb{N^2}}}1=\sum_{\substack{a^2-b^2+a+b=2n\\b\ge a\\(a,b)\in \mathbb{N^2}}}1$$

And then simplified the resulting sum by swapping the summation indices several times and by setting $b=a-1+k$ with $k\in \mathbb{N}$ since we have that $b\ge a$.

This was the proof I scribbled down, where I used $\chi_2$ to denote the Dirichlet character modulo $2$.

Sorry if it's kind of messy:

enter image description here enter image description here

$\endgroup$
1
  • $\begingroup$ Good one, +1 for the nice explaination :) $\endgroup$ – Bhavik Ambani Mar 20 '14 at 9:06
0
$\begingroup$

The number of ways of representing a number by consecutive integers is equal to the number of divisors of the largest odd divisor of that integer minus 1. (If you count the number itself as a representation, you don't need to subtract 1). The number of divisors of a number $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$, is $d(n)=(a_1+1)(a_2+1)...(a_k+1)$. In other words, just add 1 to each power in the prime factorization and multiply them all together.

So if you want to find the number of ways to write a number $n$ as a sum of consecutive integers, factor $n$ into powers of primes, $n = p_1^{a_1}p_2^{a_2}...p_k^{a_k}$, then, using only the powers of odd primes, compute $(a_1+1)(a_2+1)...(a_k+1)$. (If one of the $p_i^{a_i}$ are a power of 2, delete that term).

$\endgroup$
1
  • $\begingroup$ Welcome to Math.SE. This is a very old question which already has some really good answers. You are not contributing anything new. It would be great if you answer some more recent un-answered questions. $\endgroup$ – Shailesh Apr 20 '16 at 12:59

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