I was trying to write a poker program yesterday, and trying to figure out a way to tell the computer how to detect a straight. I realized that if you add $5$ consecutive numbers and divide by $5$, you'll get no remainder. I tried for $6$ consecutive numbers, but it didn't work. It turns out it only works for odd numbers. Really silly question, but does this 'method' have a name? Has it been proven that for all odd $n$, the sum of any $n$ consecutive numbers divided by $n$ yields a remainder of zero?
[Math] Sum of $n$ consecutive numbers divided by $n$
number theory
Related Solutions
Ah, here we go: this one's the problem of enumerating the number of ways to make change. This problem has been discussed before on this site and in a nice textbook, but let's specialize to your problem.
Consider a country, Lost-soulia, where the currency unit is the Lostie. The existing coins of the realm have the values of 1 Lostie, 2 Losties, and 4 Losties. You're asking how many ways can one have 10 Losties in the coins of the realm.
One way to solving this makes use of the concept of generating functions; specifically, consider the generating function
$$\frac1{(1-a x)(1-b x^2)(1-c x^4)}$$
where $a,b,c$ each correspond to the number of each denomination. To solve your problem of representing 10 Losties in coins, we expand the generating function as a Maclaurin series, and take the coefficient of $x^{10}$. For this case, the required coefficient is
$$a^{10}+a^8 b+a^6 b^2+a^6 c+a^4 b^3+a^4 b c+a^2 b^4+a^2 b^2 c+a^2 c^2+b^5+b^3 c+b c^2$$
We count twelve terms in this result, corresponding to your twelve ways of representing 10 Losties in terms of Lostie coins. Each term can be interpreted as a particular partition of 10; for instance, the term $a^4 bc$ corresponds to having 4 1-Lostie coins, 1 2-Lostie coin, and 1 4-Lostie coin, which totals to 10 Losties. (The exponents of the $a,b,c$ correspond to the counts of each coin.)
We can generalize. If for instance Lost-soulia decides to release a brand spanking new 3 Lostie coin, you just need to change your generating function to
$$\frac1{(1-a x)(1-b x^2)(1-c x^4)(1-d x^3)}$$
where $d$ corresponds to the count of 3-Lostie coins.The coefficient of $x^{10}$ in the series expansion is
$$\begin{split}a^{10}+a^8 b+a^7 d+a^6 b^2+a^6 c+a^5 b d+a^4 b^3+a^4 b c+a^4 d^2+a^3 b^2 d+a^3 c d+a^2 b^4+\\ a^2 b^2 c+a^2 b d^2+a^2 c^2+a b^3 d+a b c d+a d^3+b^5+b^3 c+b^2 d^2+b c^2+c d^2\end{split}$$
which has 23 terms, so you have 23 ways of having 10 Losties in coins. The $abcd$ term for instance corresponds to partitioning 10 as $1+2+4+3$, and $ab^3 d$ corresponds to partitioning 10 as $1+2+2+2+3$.
I gave a short Mathematica routine for the change-making problem in the comments, but that version has a bug (try MakeChange[8, {2, 7}]). Here is a more robust version of that routine:
MakeChange[n_Integer?Positive, v_?VectorQ] := Module[{l = Length[v], x},
Exponent[#, Array[C, l]] & /@
Flatten[{Expand[
SeriesCoefficient[1/Apply[Times, 1 - Array[C, l] x^v],
{x, 0, n}]] /. Plus -> List}]] /;
VectorQ[v, (IntegerQ[#] && Positive[#]) &]
Much later: It turns out that the functionality of MakeChange[] is already done by the intrinsic functions IntegerPartitions[] and FrobeniusSolve[]. Still, I think the routine is a nice illustration of generating functions...
There are more efficient methods for solving the Frobenius problem, using methods from graph theory and integer programming; you can search the web for papers discussing these methods for generating and counting integer partitions.
You want to find the $\gcd$ of the numbers
$$F_1+\cdots+F_n,\quad F_2+\cdots+F_{n+1},\quad F_3+\cdots+F_{n+2},\quad F_4+\cdots+F_{n+3},\quad \cdots\cdots$$
Since $F_1+\cdots+F_n=F_{n+2}-1 \implies F_{1+k}+\cdots+F_{n+k}=F_{n+k+2}-F_{k+2}$, this is
$$F_{n+2}-F_2,\quad F_{n+3}-F_3,\quad F_{n+4}-F_4,\quad F_{n+5}-F_5,\quad \cdots$$
Notice how this is a new Fibonacci(-like) sequence, in which each term is a sum of the two previous terms. Therefore, not only does the $\gcd$ of the whole sequence divide the $\gcd$ of the first two terms (this holds generically for any sequence), but the $\gcd$ of the first two terms divides all of the other terms hence divides the $\gcd$ of the whole sequence. Therefore, the $\gcd$ of the whole sequence is equal to the $\gcd$ of the first two terms! Using the algorithm $(a,b)=(a,b-a)$, we can simplify: $(F_{n+2}-F_2,F_{n+3}-F_3)=(F_{n+2}-F_2,F_{n+1}-F_1)=(F_n-F_0,F_{n+1}-F_1)$.
Therefore, the generalization of $3\mid(F_{k+1}+\cdots+F_{k+8})$ for all $k\ge0$ is
$$\gcd(F_n,F_{n+1}-1)\mid(F_{k+1}+\cdots+F_{k+n}).$$
Note this holds for negative values of $k$ too.
Best Answer
Yes, If $n=2k+1$, write the numbers as
$a - k, a-(k-1), \dots,a-1, a, a + 1, \dots, a+(k-1), a+k$
Adding gives you $na$ which is divisible by $n$.
Try something similar for even $n =2m$ and you see that the sum is $m \mod n$, which is not divisible by $n$.