Primary decomposition of a particular sum Is there an easy way to see that the sum
$$
\sum_{k=0}^{728} (1+2k)
$$
has primary decomposition $3^{12}$ ?
 A: The number of terms is $729=3^6$ and the formula for the sum of an arithmetic progression is the number of terms times the average of the first and last term:
$$\sum_{k=0}^{3^6-1}(1+2k)=3^6\cdot\frac{1+(1+2(3^6-1))}2=3^6\cdot3^6=3^{12}$$
A: 
$$(k+1)^2-k^2=(k^2+2k+1)-k^2=2k+1\quad=>\quad\sum_{k=0}^{n-1}2k+1=\sum_{k=0}^{n-1}(k+1)^2-k^2=n^2$$ In this case, $n-1=728$. See telescoping series for more details. Or, alternately, $$\sum_{k=0}^{n-1}2k+1=2\sum_{k=0}^{n-1}k+\sum_{k=0}^{n-1}1=2\frac{n(n-1)}2+n=n^2$$ See Faulhaber's formulas for more details. As to why $\displaystyle\sum_{k=0}^{n-1}k=\frac{n(n-1)}2$ just write the sum in both ascending and descending order, then add the two expressions term by term, as Gauss himself did two centuries ago.
A: It is well known that the sum of the first $j$ odd integers is $j^2$. Indeed, the previously posted answers essentially demonstrate this factoid. But if you know that rule of thumb, then you know directly that the sum of the first $729$ odd integers ($k=0\dots 728$ gives $729$ terms) is $729^2$. Now all that remains is to recognize that $729=3^6$ and you are done.
