Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Determine in How many ways $N!$ can be expressed as sum of consecutive numbers.For example for $3!$ can be as $1+2+3$ only $1$ ways.

Please suggest an elegant approach.

share|improve this question
2  
Discounting the trivial sum of one number, then? –  Peter Taylor Jan 22 '11 at 21:11
    
@Peter Taylor:Probably I don't understand what you meant. –  Quixotic Jan 22 '11 at 21:12
    
1 + 2 + 3 is a sum of 3 consecutive numbers. 6 is a sum of one consecutive number... –  Peter Taylor Jan 22 '11 at 21:16
    
Do all the numbers need to be integers? Do they need to be positive? –  Yuval Filmus Jan 22 '11 at 21:41

4 Answers 4

up vote 4 down vote accepted

I am assuming that you want it to be written as a sum of consecutive natural numbers.

Let $p \leq N$ be a prime. The highest power of $p$ dividing $N$ is given by $\alpha_p = \displaystyle \sum_{k=1}^{\infty} \lfloor \frac{N}{p^k} \rfloor$.

So $N! = 2^{\alpha_2} 3^{\alpha_3} 5^{\alpha_5} \ldots q^{\alpha_q}$, where $q$ is the last prime $\leq N$.

We want $N! = a + (a+1) + (a+2) + (a+3) + \cdots b = \frac{(b-a+1)(a+b)}{2}$, where $a,b \in \mathbb{N}$

So we need to find $a$ and $b$ such that $(b-a+1)(a+b) = 2^{(\alpha_2 + 1)} 3^{\alpha_3} 5^{\alpha_5} \ldots q^{\alpha_q}$.

Now note that $(a+b)$ and $(b-a+1)$ are of opposite parity.

So one of them has to be odd. Further $(a+b)>(b-a+1)$ since $a \in \mathbb{N}$.

Assume that $(a+b)$ is even. So $(b-a+1)$ is odd.

Hence $$(a+b) = 2^{(\alpha_2 + 1)} 3^{\beta_3} 5^{\beta_5} \ldots q^{\beta_q}$$ $$(b-a+1) = 3^{\alpha_3-\beta_3} 5^{\alpha_5-\beta_5} \ldots q^{\alpha_q-\beta_q}$$ where $0 \leq \beta_p \leq \alpha_p$ and $(a+b) > (b-a+1)$

Now assume that $(a+b)$ is odd. So $(b-a+1)$ is even.

Hence $$(a+b) = 3^{\beta_3} 5^{\beta_5} \ldots q^{\beta_q}$$ $$(b-a+1) = 2^{(\alpha_2 + 1)} 3^{\alpha_3-\beta_3} 5^{\alpha_5-\beta_5} \ldots q^{\alpha_q-\beta_q}$$ where $0 \leq \beta_p \leq \alpha_p$ and $(a+b) > (b-a+1)$

If we relax the fact that it has to be written as a sum of consecutive natural numbers, and assume that the consecutive numbers belong to integers then we get $$2 \times (1+\alpha_3) \times (1+\alpha_5) \times (1+\alpha_7) \cdots \times (1+\alpha_q)$$

Note that the above also acts as a trivial upper bound if it has to be written as a sum of consecutive natural numbers. This upper bound is obtained by violating the constraint $(a+b) > (b-a+1)$

share|improve this answer

Since $n+(n+1)+\cdots+(n+d)=(d+1)n+\frac{d(d+1)}{2}=\frac{(2n+d)(d+1)}{2}$, you can write the number $M$ as sum of $d+1$ consecutive integers starting from $n$ if you can decompose $$ 2M=(2n+d)(d+1). $$ Note that the two factors have opposite parity, so the question is: given $M$, how many ways we have to write $2M$ as a product $2M=ab$ in such a way that $a$ and $b$ have opposite parities and $a>b-1$?

In this way one gets some non-trivial examples: $4!=24=7+8+9$, $5!=120=22+23+24+25+26$, $6!=720=41+42+\cdots+55$, and so on.

(Some answers arrived while I was typing this)

share|improve this answer

Let's deal with odd length and even length sequences separately.

A number $N$ is the sum of an odd number of consecutive integers, centered at $m$, whenever $m|N$ and $N/m$ is odd.

A number $N$ is the sum of an even number of consecutive integers, centered at $m+1/2$, whenever $2m+1|N$.

Now let $N = 2^k M$, where $M$ is odd. For each factor $m|M$ we get one odd-length sequence centered at $2^km$, and one even-length sequence centered at $m+1/2$.

Example: $N = 6 = 2^1 3$, so we get two odd-length sequences (centered at $2$ and $6$) and two even-length sequences (centered at $.5$ and $1.5$): $$6 = 1 + 2 + 3 = 6 = -5 -4 -3 -2 -1 + 0 + 1 + 2 + 3 + 4 + 5 + 6 = 0 + 1 + 2 + 3.$$

In order to obtain a formula for the number of representations of $n!$, all we need to do is to figure out how many odd divisors $n!$ has. I leave that to the reader.

share|improve this answer

Basically you have

$a+(a+1)+(a+2)+\ldots+b=\sum _{k=a}^b k=-(1/2) (-1 + a - b) (a + b)$

So you have to find positive nontrivial solutions for the following diophantine equation:

$-(1/2) (-1 + a - b) (a + b) = n!$

for $n=3$ the only solution is exactly the one you gave with $a=1$ and $b=3$

share|improve this answer
    
There is also the one with a=b=6. Generally you get a solution for each two-item factorization of 2n! –  Ross Millikan Jan 22 '11 at 21:42
    
I know thats why i said nontrivial :-), that solution always exists –  Listing Jan 22 '11 at 22:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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