36
$\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$
  • $\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
16
$\begingroup$

Here's one more way to calculate this, from my answer to this question on another site:

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.

$\endgroup$
  • 1
    $\begingroup$ Very Good Answer.. +1 for this $\endgroup$ – Bhavik Ambani May 3 '12 at 5:06
13
$\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
    $\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
5
$\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$
  • $\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
  • $\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
3
$\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$
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$
  • $\begingroup$ Good one, +1 for the nice explaination :) $\endgroup$ – Bhavik Ambani Mar 20 '14 at 9:06
1
$\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$
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$
  • $\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

protected by Zev Chonoles Dec 28 '16 at 21:33

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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