Friday, May 20, 2011

Polygonal numbers and multiplication tables (Project Euler #6)

I just recently started in on the problems at Project Euler - a set of math & programming problems for students and others who might like to solve them using short computer programs or pencil and paper.

I haven't tried many problems, but I liked #6 because there is a nice way to state the problem using polygonal numbers, and a nice way to visualize it using the multiplication table.

The problem statement (slightly re-ordered) is:
Find the difference between the square of the sum of the first one hundred natural numbers and the sum of the squares of the first one hundred natural numbers.
Gauss famously (or apocryphally) came up with ways of tackling problems like this at a tender age - see everything about how he may have done it here. Using formulas based on Gauss's approach is the recommended way of solving this problem, but what I first noticed and liked about the problem was how it could be stated (generally) in terms of polygonal numbers:
Find the difference between the square of the nth triangular number and the the nth square pyramidal number.
I don't know if there really is a standard for writing polygonal numbers, but I use $p^d_{k,n}$ to represent the nth d-dimensional k-polygonal number (for example $p^2_{3,n}$ is the nth triangular number, $p^3_{4,n}$ is the nth square-pyramidal number), so we could say that we are trying to find:


A general formula for the polygonal numbers is:


Playing around with pascal-like-triangles (like I tried to do here and here) is one way to convince yourself that this formula does make sense, and you could use it to solve the problem directly.

This is nice, but what's nicer is that there is a simple way to visualize "the square of the nth triangular number" and that you can also find "the nth square pyramidal number" within that visualization.

Consider the standard grade-school multiplication table. Say for example, the 10 by 10 variety shown below.


If you sum all of the entries in the n by n table, you get the square of the nth triangular number.


So, the whole n by n table represents the square of the nth triangular number. Inside the table, you also get the nth square-pyramidal number - this is the sum of the entries along the downward sloping diagonal.


We can think of the problem as finding the sum of all entries in the multiplication table, taking away the entries on the diagonal. Since the table is symmetrical along this diagonal, we can cut this down a bit by finding twice the sum of the "upper triangle" of the table.



We can state the answer to the problem using this idea as:


one way to express this in Java using for loops is: 

int number = 100; // the number you stop summing at
int result = 0;
for (int i=1; i<=number; i++){
for(int j=i+1; j<=number; j++){
result += i*j;
}
}
result = 2*result;

There are some other nice connections between polygonal numbers and the multiplication table. For example, the well known "a square number is the sum of two triangular numbers" relationship can be found inside the multiplication table, and so can the triangulo-triangular numbers (4-dimensional triangular numbers).