I just finished up Problem 6. This one was really straightforward. The interesting part was learning a new math trick: Square Pyramidal Numbers. Here's the most brute-force way (I thought of) to solve it:
"Naïve" Solution
"""Solves Problem 6 from Project Euler."""
def sum_of_squares(upper_bound):
"""Sums the squares of all the natural numbers from 1 to \
upper_bound (inclusive)."""
return sum(n ** 2 for n in range(1, upper_bound + 1))
def square_of_sums(upper_bound):
"""Sums all the numbers from 1 to upper_bound."""
return (sum(range(1, upper_bound + 1)) ** 2)
def problem_6(n):
"""Finds the difference between the square of the sums and the \
sum of the squares for the first n natural numbers."""
return square_of_sums(n) - sum_of_squares(n)
if __name__ == '__main__':
print problem_6(100)
Even though this solution has the worst Big O, it wasn't noticeably slower than any of the others for numbers the size of the ones here.
I used a slightly more sophisticated approach because I remembered an insight for summing the first N natural numbers, discovered by none other than Gauss himself (especially entertaining to use Gauss to solve problems on Project Euler, I know): n * (n + 1)) / 2. I fell back on brute force for the sum of squares part, though.
Solution I Used
"""Solves Problem 6 from Project Euler."""
def sum_of_squares(upper_bound):
"""Sums the squares of all the natural numbers from 1 to \
upper_bound (inclusive)."""
return sum(n ** 2 for n in range(1, upper_bound + 1))
def square_of_sums(upper_bound):
"""Sums all the numbers from 1 to upper_bound."""
# Use Gauss' insight about n/2 * (n + 1).
return (upper_bound * (upper_bound + 1) / 2) ** 2
def problem_6(n):
"""Finds the difference between the square of the sums and the \
sum of the squares for the first n natural numbers."""
return square_of_sums(n) - sum_of_squares(n)
if __name__ == '__main__':
print problem_6(100)
Since there was a math trick for solving the summing problem, I suspected there was one for the sum of squares problem, as well. A quick Google revealed: Square Pyramidal Numbers. I wish I had known about this when I was doing stupid brain teasers; I always knew I was wasting too much time counting squares.
Least Brutish Solution
"""Solves Problem 6 from Project Euler."""
def sum_of_squares(upper_bound):
"""Sums the squares of all the natural numbers from 1 to \
upper_bound (inclusive)."""
# Use the rule for square pyramidal numbers
# (http://en.wikipedia.org/wiki/Square_pyramidal_number).
return ((2 * upper_bound ** 3) + (3 * upper_bound ** 2) + upper_bound) / 6
def square_of_sums(upper_bound):
"""Sums all the numbers from 1 to upper_bound."""
# Use Gauss' insight about n/2 * (n + 1).
return (upper_bound * (upper_bound + 1) / 2) ** 2
def problem_6(n):
"""Finds the difference between the square of the sums and the \
sum of the squares for the first n natural numbers."""
return square_of_sums(n) - sum_of_squares(n)
if __name__ == '__main__':
print problem_6(100)
All in all, I'm really glad I started working these problems. I've usually learned/remembered at least one interesting math trick or Python trick during each one I solved, or at least had good programming practice (KISS) driven home.
Back to flipping out...
