Hip to be squares

We are looking for the least positive integer $n$ such that $\frac{n(n + 1)(2n + 1)}{6}$ is divisible by $1000$ , i.e., such that $n(n + 1)(2n + 1)$ is divisible by $6000.$

Now $6000 = 2^{4}*3*5^{3}$ . So since $n, (n + 1)$ and $(2n + 1)$ are relatively prime for any positive integer $n$ , we know that one of them is divisible by $125$ . The least possible $n$ for which this can happen is $n = 62$ , which makes $2n + 1 = 125.$ But $62*63$ is not divisible by $2^{4}*3$ , so we will need to advance to the next smallest $n$ , which will be $n = 124$ , which makes $n + 1 = 125$ . But $124*249$ is not divisible by $2^{4}*3$ , so we need to advance to the next smallest $n$ .

Now we need to move through the sequence of increasing possible values of $n$ based on the "divisibility by $125$ " criterion to find a product $n(n + 1)(2n + 1)$ that is also divisible by $2^{4}*3.$ The sequence of such $n$ goes as follows:

$62, 124, 125, 187, 249, 250, 312, 374, 375, 437, 499, 500, 562, 624.$

Only once we reach $624*625*1249 = 2^{4}*3*5^{4}*13*1249$ do we have all the prime divisors in sufficient powers to satisfy the divisibility by $6000$ requirement. Thus the least such value $n$ is $\boxed{624}$ .

I know that there is a less "bashy" substitute for the last stage of my solution, but for now I just wanted to get a solution posted and I'll worry about tightening it up later.

Python:

1
2
3
4
5
6

k = 1
total = 1
while total % 1000 != 0:
    k += 1
    total += k**2
print "Answer:", k

Just for fun i tried to write a c ++ program. And found the out put as 624.

Here is the code if your interested http://pasted.co/b8faefe2