-1
$\begingroup$

I have a challenge about a cat in a trip where he can walk in the way of $d, d+1, d+2...$ and the sum of that should give $N$, given an $N$, how many ways of chosing $d$ are posible?

Example:

$N=30$ -> $Ans=3$

$d_1=4; d_2=6; d_3=8$

For $d_1: 4 + 5 + 6 + 7 + 8 = 30$

Edit:

Another way to see it is: How many subsets in the sumation up to N are posible in the way $(\sum (d+n) - \sum(d-1))$=N

1 Answers 1

1

You are basically asking the number of solutions of:

$$\sum_{i=x}^{y} i=N$$ $$\frac{y^2+y-x^2-x}{2}=N$$ $$(y-x)(y+x)+(y-x)=2N$$ $$(y-x)(y+x+1)=2N$$

Since $y+x+1>y-x$ , $y+x+1$ must be a divisor bigger than $\sqrt{2N}$, and the other one a divisor smaller than $\sqrt{2N}$.

$$y-x=d_1 \ \ \ y+x+1=d_2$$

Summing:

$$2y+1=d_1+d_2$$ $$y=\frac{d_1+d_2-1}{2}\Rightarrow x=\frac{-d_1+d_2-1}{2}$$

At least one(and only one can be) among $d_1$ and $d_2$ is even, so the number of solutions is equal to the number of odd divisors of $2N$ that are smaller than its root plus the number of divisors that contains all of the factors $2$ in $2N$(or bigger it's symmetric). In general if you have:

$$N=2^{\alpha}\prod_{i=1}^{k} p_i^{a_i}$$ $$2N=2^{\alpha+1}\prod_{i=1}^{k} p_i^{a_i}$$

Since there is always an odd divisor the answer is simply:

$$\sigma_0(\prod_\limits{i=1}^{k} p_i^{a_i})=\prod_{i=1}^{k} (1+a_i)$$

:/