The Home for People Who Like to Flip Out and Write Code
Project Euler: Problem 6
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
1234567891011121314151617181920
"""Solves Problem 6 from Project Euler."""defsum_of_squares(upper_bound):"""Sums the squares of all the natural numbers from 1 to \ upper_bound (inclusive)."""returnsum(n**2forninrange(1,upper_bound+1))defsquare_of_sums(upper_bound):"""Sums all the numbers from 1 to upper_bound."""return(sum(range(1,upper_bound+1))**2)defproblem_6(n):"""Finds the difference between the square of the sums and the \ sum of the squares for the first n natural numbers."""returnsquare_of_sums(n)-sum_of_squares(n)if__name__=='__main__':printproblem_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
123456789101112131415161718192021
"""Solves Problem 6 from Project Euler."""defsum_of_squares(upper_bound):"""Sums the squares of all the natural numbers from 1 to \ upper_bound (inclusive)."""returnsum(n**2forninrange(1,upper_bound+1))defsquare_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)**2defproblem_6(n):"""Finds the difference between the square of the sums and the \ sum of the squares for the first n natural numbers."""returnsquare_of_sums(n)-sum_of_squares(n)if__name__=='__main__':printproblem_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
1234567891011121314151617181920212223
"""Solves Problem 6 from Project Euler."""defsum_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)/6defsquare_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)**2defproblem_6(n):"""Finds the difference between the square of the sums and the \ sum of the squares for the first n natural numbers."""returnsquare_of_sums(n)-sum_of_squares(n)if__name__=='__main__':printproblem_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.