A given natural number $N$ is being decomposed in a sum of some consecutive integers. a.) Find all such decompositions for $N=500.$ b.) How many such decompositions does the number $N=2^{\alpha }3^{\beta }5^{\gamma }$ (where $\alpha ,$ $\beta $ and $\gamma $ are natural numbers) have? Which of these decompositions contain natural summands only? c.) Determine the number of such decompositions (= decompositions in a sum of consecutive integers; these integers are not necessarily natural) for an arbitrary natural $N.$ Note by Darij: The $0$ is not considered as a natural number.
Problem
Source: IMO LongList 1959-1966 Problem 29
Tags: number theory, Summation, equation, IMO Shortlist, IMO Longlist
03.09.2004 14:20
If $N=2^{\alpha}M$, where $M$ is odd and the total number of divisors of $M$ is $d(M)$ then exists $d(M)$ such decompositions in sum of positive integers. If $N=2^{\alpha} $ prod($p_i^{\alpha_i}$) , where each $p_i$ is odd , $N$ is written as sum of $b+1,b+2,...,a$ then we get $a-b$ and $a+b+1$ as divisors with different parity of $2N$ and having the product exactly $2N$. So: $a=2^{\alpha}$prod($p_i^{\gamma_i}$) + 1/2 prod($p_i^{{\alpha_i}-{\gamma_i}}$) , where any ${{0\leq\gamma_i}\leq\alpha_i}$. It is easy to check that each two of these possible values of $a$ are different. The desired answer is: prod(${\alpha_i}+1$).
10.09.2004 02:13
small latex hint: you can use \prod to make a product sign $\prod$, or for example \prod_{i=1}^n a_i for $\prod_{i=1}^n a_i $
13.09.2004 08:28
...did you notice the difference between a bad programmer and a good one? 1st always believes that a 1Kb has 1000 bits, while 2nd thinks that 1Km has 1024 meters
09.11.2023 09:21
Notice the fact that for every decomposition of $N$ which has negative numbers, it is basically an extension of a decomposition having only natural numbers, and vice-versa, that is for every decomposition of $N$ having positive numbers, we can make a decomposition of $N$ having negative numbers. So now we consider only the decompositon of $N$ having positive numbers. Let the decomposition be $$N = x + (x-1) + (x-2) \dots + (y+1) + y \implies N = \frac{x(x+1)}{2} - \frac{y(y+1}{2} \implies 2N = x^2 - y^2 + x - y = (x-y)(x+y+1)$$We want that $N$ has to be factorised into two factors such that one of them is even, one of them is odd. Hence, we can simply find a general answer and we are done!