[ProjectEuler] 0. Sum of Odd Squares
A perfect square (or square number) is a number that is the square of a positive integer.
For example, 9 is a perfect square because
9 = 3 ^ 2; it is also an odd square.
The first five square numbers are:
1, 4, 9, 16, 25.
Among the first N square numbers, what is the sum of all the odd squares?
Solution
The first N square numbers are 1², 2², 3², …, N². Among these, the odd squares are 1², 3², 5², … — i.e., squares of odd integers.
Let m = ⌈N/2⌉ be the number of odd integers from 1 to N. Then the odd squares we sum are:
1² + 3² + 5² + … + (2m - 1)²
Closed-form formula
For i = 1, 2, …, m:
(2i - 1)² = 4i² - 4i + 1
Summing over i:
Σ(i = 1 to m) (2i - 1)² = 4·Σi² - 4·Σi + m
Using Σi² = m(m + 1)(2m + 1) / 6 and Σi = m(m + 1) / 2:
= 4·m(m + 1)(2m + 1) / 6 - 4·m(m + 1) / 2 + m
= 2m(m + 1)(2m + 1) / 3 - 2m(m + 1) + m (simplify the fraction)
= m·[2(m + 1)(2m + 1) / 3 - 2(m + 1) + 1] (factor out m)
= m·[2(m + 1)(2m + 1) - 6(m + 1) + 3] / 3 (rewrite each term over 3)
= m·[4m² + 6m + 2 - 6m - 6 + 3] / 3 (expand the terms)
= m·(4m² - 1) / 3
Answer
m(4m² - 1) / 3 where m = ⌈N/2⌉
Example: For N = 5, the first 5 squares are 1, 4, 9, 16, 25. Odd squares: 1, 9, 25. Sum = 35.
With m = ⌈5 / 2⌉ = 3: 3(4·9 - 1) / 3 = 3·35 / 3 = 35 ✓