Real Ultimate Programming

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    """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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    """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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    """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…