## Monday, August 31, 2009

### Solutions to Two More Java Puzzlers

In my last post, Two More Java Puzzlers, I gave two puzzling snippets of Java code that don't act exactly as expected.

The first puzzle asked why the following code prints null instead of either "even" or "odd" as expected.
    public static void main(String[] args)    {        String a = null;        int n = "number".hashCode();        switch( n % 2 ) {            case 0:                a = "even";                break;            case 1:                a = "odd";                break;        }                System.out.println( a );    }

This code uses n % 2 as the condition on a switch with cases for 0 and 1. Strangely, neither of the cases is executed. What other return values could the modulo operator produce when the divisor is 2? Surely 0 and 1 are the only two possible remainders when dividing by 2, aren't they?

Usually that's the case. "Usually" meaning, "for positive dividends." The Java % operator doesn't return the modulus in a strict mathematical sense. What it returns is the remainder.

What's the difference? In this particular case "number".hashCode() returns a negative value. When n is negative in the operation n % 2, the result will be negative too.

This isn't just a problem in Java. Some languages specify that the % operator is a strict modulus function, and some specify that it returns the remainder. You should know how the operator reacts to negative inputs in whatever language you're using.

To fix the code above, just use the absolute value of the result of the remainder operation.

The second puzzle asked why the following code crashes where it does, and why doesn't it crash sooner?
    public static void main(String[] args)    {        Vector<Integer> numbers = new Vector<Integer>();        int min = 128;        int max = 255;        for( int i = min; i <= max; ++i )        {            numbers.add(i);        }        int element = 100;        numbers.remove(element);        element = 255;        if( numbers.contains(element) )        {            numbers.remove(element);        }    }

The code above creates a Vector of Integer objects, then adds the values from 128 to 255 to the Vector. It then removes element 100, checks to see if the Vector contains and element with the value 255, and attempts to remove it if it does. (At least this is what it appears to be doing.)

If you run the code above you will see it crash on line 21, when the second remove operation is attempted. Why does it crash there and not the first time it attempts to removes an element? The second element removed has a value of 255, which was added to the Vector. If that value wasn't found in the Vector, the remove operation wouldn't even execute. It should crash earlier, when the attempt to remove the element with the value of 100 is executed, if it's going to crash at all, shouldn't it? There is no element with that value to remove.

The problem with the above code is related to auto-boxing. More precisely, it's a lack of auto-boxing at the critical point that's causing the code to fail. Note that on line 10 when the int values are added to the Vector, they're automatically wrapped and added as Integer objects. This might lead you to believe that the same thing will happen when you try to remove elements from a Vector, as well. This isn't the case when the elements are Integers, though.

The problem is that Vector has a remove(int index) method that interferes with the auto-boxing that would normally occur when you try to remove an int. The statement on line 21 above is attempting to remove the element at index 255, which doesn't exist, instead of the element with the value 255, which does. The contains method isn't overloaded, so the condition on line 19 evaluates to true, allowing the fatal line of code to execute.

And what about the other remove operation? It has the same problem, only reversed. It appeared to be attempting to remove the element with the value of 100, which doesn't exist, but it was really removing the element at index 100, which does exist. This could be a particularly insidious bug if the values never go out of range. Instead of crashing quickly and alerting you to a problem, it could just quietly remove the wrong values.

To fix the bugs in this puzzler, just wrap the variable element in an Integer object before using it as an argument to remove, to make sure the expected method is called. And what lessons can we learn? Never assume. Always check to make sure you know exactly which operations will use auto-boxing, and which operations won't, with whatever libraries you use.

## Saturday, August 29, 2009

### Two More Java Puzzlers

Oh, Java! Will you ever run out of corner cases to confuse and bewilder me? I doubt it. On the bright side, you are an unquenchable fountain of fun programming puzzles for my blog. Thanks, Java!

Odd or Even?

Today's first puzzler comes to us courtesy of @royvanrijn. Take a look at the following code:
    public static void main(String[] args)    {        String a = null;        int n = "number".hashCode();        switch( n % 2 ) {            case 0:                a = "even";                break;            case 1:                a = "odd";                break;        }                System.out.println( a );    }

At first glance it looks like this program should print either "even" or "odd", but looks can be deceiving. The program prints null. The question is, why?

Who uses Vector anyway?

Our second puzzler comes from my boss, Chris. It's a very contrived variation of a problem that he encountered in a very real project. The following code crashes at a point you might not expect. Can you tell why it crashes there, and why it didn't crash before that point?
    public static void main(String[] args)    {        Vector<Integer> numbers = new Vector<Integer>();        int min = 128;        int max = 255;        for( int i = min; i <= max; ++i )        {            numbers.add(i);        }        int element = 100;        numbers.remove(element);        element = 255;        if( numbers.contains(element) )        {            numbers.remove(element);        }    }

A co-worker figured this one out in under a minute after he was told that it wasn't a threading issue (which should be obvious from this contrived example, but wasn't in the original context). See if you can beat his very impressive time.

I'll have the answers to both puzzlers in an upcoming post.

As always, I can't bring up the subject of Java puzzlers without mentioning the book Java Puzzlers: Traps, Pitfalls, and Corner Cases by Josh Bloch and Neal Gafter. It's a collection of 95 Java puzzles plumbed from the depths of the language and its core libraries.

## Tuesday, August 25, 2009

### The Broken Stick Revisited

In my earlier post The Broken Stick Experiment, I introduced a problem I had seen in a BLOSSOMS video lecture of the same name. The problem asks
If you break a stick randomly in two places, what is the probability that you can form a triangle from the three pieces?
If you watched the video or ran the simulation code I provided, you found out that the probability of forming a triangle by chance is 25%.

Reader Tom Raywood asks, "Do obtuse triangles count here, or is the solution limited to acute?" The answer to that question is that the solution accounts for triangles of all types, acute, obtuse, and even right triangles. When you break the stick randomly, any of the three are possible (although, as we'll see, right triangles are so unlikely that the probability of getting one randomly is effectively 0).

This question piqued my curiosity enough to investigate another related question.

What proportion of the resulting triangles from the broken stick experiment will be obtuse?

I decided to modify the simulation program to find out the answer.

The first question I had to answer was "How do you tell if a triangle is acute or obtuse?" The easy way is look at it and see if it contains one angle greater than 90° (the definition of an obtuse triangle). However, in the original experiment we only know the lengths of the three sides of the triangles, and none of the angles. It seemed unnecessary to compute all three angles just to see if the triangle was acute or obtuse, although this approach is not totally infeasible. Fortunately, there's an easier way.

We all know from the Pythagorean Theorem that for a right triangle

a2 + b2 = c2

That is, if one angle is exactly right (90°), the sum of the squares of the two sides adjacent to that angle will be exactly the same as the side opposite that angle.

But if the angle changes (while the two sides a and b stay the same length) then the relationship changes as well. If you open the angle up, side c (and its square) gets larger. If you close the angle, side c (and its square) gets smaller. Meanwhile, the sum of the squares of sides a and b stays the same. This leads to the following relationships for acute and obtuse triangles:

If the triangle is acute:
a2 + b2 > c2

If the triangle is obtuse:
a2 + b2 < c2

Using those relationships, I modified the simulation to count how many of the resulting triangles were acute, obtuse, and right triangles.
import java.util.Arrays;import java.util.Random;public class BrokenStickRevisited{ public static void main(String[] args) {     Random random = new Random();     int trials = 1000000;     int triangles = 0;     int acute = 0;     int obtuse = 0;     int right = 0;     double[] breaks = new double[2];     double[] sides = new double[3];     for( int i=0; i < trials; ++i )     {         breaks[0] = random.nextDouble();         breaks[1] = random.nextDouble();         Arrays.sort(breaks);         sides[0] = breaks[0];         sides[1] = breaks[1] - breaks[0];         sides[2] = 1.0 - breaks[1];         Arrays.sort(sides);         if( sides[2] < (sides[0] + sides[1]) )         {             triangles++;             double aSquared = sides[0] * sides[0];             double bSquared = sides[1] * sides[1];             double cSquared = sides[2] * sides[2];             if( aSquared + bSquared > cSquared )             {                 acute++;             }             else if( aSquared + bSquared < cSquared )             {                 obtuse++;             }             else // highly unlikely, but still...             {                 right++;             }         }     }     System.out.println("Triangles: " + triangles);     System.out.println("Acute: " + acute);     System.out.println("Obtuse: " + obtuse);     System.out.println("Right: " + right);     System.out.println("Trials: " + trials);     double p = (double)triangles / trials;     System.out.println("Proportion: " + p);     double pAcute = (double)acute / triangles;     double pObtuse = (double)obtuse / triangles;     System.out.println("Acute Proportion: " + pAcute);    System.out.println("Obtuse Proportion: " + pObtuse); }}
I let the simulation run for 1,000,000 trials to be sure I get a result accurate to three decimal digits. I ran the simulation several times, and never got a single right triangle. That's not surprising, since we knew the odds were quite against it from the beginning.

The proportion of triangles that were obtuse was 0.682, or about 68.2%. The rest (about 31.8%) were acute triangles. This seemed like a strange result. I was hoping for a nice even proportion like the 1/4 probability we got for generating a triangle from the first broken stick problem. It took a bit of exploration for me to explain the result. Read on if you're still curious.

In order to explain the odd proportion we got from the simulation, I need to start with the solution to the original problem. If we break the stick at two random points, x and y, the three resulting pieces will have lengths x, (y - x), and (1 - y) if x is to the left of y

and y, (x - y), and (1 - x) if x is to the right of y

The three pieces form a triangle if none of the pieces is greater than half the length of the stick. In other words, if

(y > 1/2) and (x < 1/2) and (y - x) < 1/2

when point x is to the left of point y (first image above), and

(x > 1/2) and (y < 1/2) and (x - y) < 1/2

when x is to the right of y (second image above). If we plot all six of these inequalities we get the area that represents the proportion of triangles formed from our broken stick.

The shaded regions representing the conditions that form a triangle add up to 1/4 of the total area, or a 0.25 probability of forming a triangle. Now all we need to do to explain the odd results of the second simulation is figure out how much of these shaded regions represent an obtuse triangle and how much represents an acute triangle.

In order to do that, we can plot the inequalities we used earlier that were derived from the Pythagorean Theorem. Since any of the three pieces of our broken stick could be the longest piece, and either break x or break y could be to the left of the other, we need to plot six different inequalities. We get these inequalities by substituting our stick lengths for the values a, b, and c in the Pythagorean Theorem.

Substituting each of the three lengths x, (y - x), and (1 - y) for each of the values a, b, and c in the Pythagorean equation

a2 + b2 = c2

gives us the following equations

x2 + (y - x)2 = (1 - y)2
x2 + (1 - y)2 = (y - x)2
(y - x)2 + (1 - y)2 = x2

Similarly, substituting the three lengths y, (x - y), and (1 - x) for the values a, b, and c gives the remaining three equations

y2 + (x - y)2 = (1 - x)2
y2 + (1 - x)2 = (x - y)2
(x - y)2 + (1 - x)2 = y2

Utilities like the Online Equation Solver or QuickMath's equation solver come in handy for solving the equations for y before plotting them in a spread sheet or on a graphing calculator. If you add the plots for the six new equations to the existing plot you should see something like the following illustration.

The small region in the center of each of the two triangles in the plot represent the probability of the broken stick forming an acute triangle. The remaining areas near the edges of the the triangles sum to the probability of forming an obtuse triangle. Using integration to find the area of the bounded areas shows that these values are within a small margin of error of the probability we arrived at using the simulation program. (This post is already a little long, so calculating the integral of the bounded areas is left as an exercise for the reader.)

Related: If you liked this post, Professor Gilbert Strang shows several different approaches to a very similar problem in another BLOSSOMS video lecture, Are Random Triangles Acute or Obtuse? In that lecture all random triangles are considered, not just those constructed from the pieces of a broken stick.

## Thursday, August 13, 2009

### Interesting Miscellany

Education

25 Incredible TED Talks for Educators (via @dorait). If you only have time to watch one, don't miss Alan Kay's talk on innovative ways to use computers in education.

BLOSSOMS Video Library - Video lectures for students and teachers on a wide range of topics including Math, Engineering, Physics, Biology, and (coming soon) Chemistry. All videos start with the section for students, then wrap up with a section for teachers, discussing some of the finer points of the student lecture and ideas for in-class activities.

Math

For Today’s Graduate, Just One Word: Statistics - “I keep saying that the sexy job in the next 10 years will be statisticians,” said Hal Varian, chief economist at Google. “And I’m not kidding.”

Most lucrative college degrees - "The top 15 highest-earning college degrees all have one thing in common -- math skills."

Programming

Still More Java Puzzlers is a short PDF by Josh Bloch and Neal Gafter. These eight new Java language puzzles serve as a follow-up in miniature to Bloch and Gafter's earlier book Java Puzzlers.

## Monday, August 10, 2009

### Dodgson (Carroll)

In my last post, A Common Thread, I posed four puzzles and asked you readers to figure out what they all had in common. The common thread that binds all four puzzles is that they were all originally written by none other than Charles Lutwidge Dodgson, better known by his pen name, Lewis Carroll. (Incidentally, some of you may notice that the title of this blog and the "Now is the time..." quote that I use also come from the works of Lewis Carroll. It would be an understatement to say that I'm a huge fan of his work.)

Charles Dodgson was an English mathematician, logician, and writer. Dodgson was born the son of a vicar at the Old Parsonage, Newton-by-Daresbury, Cheshire. He was educated at the Rugby School, where the student mathematical society is still called the Dodgson Society in his honor, and later at Christ Church Oxford, where he would spend the rest of his life employed as a lecturer.

Dodgson is best known by his pen name, Lewis Carroll. It was under this name that he published his most famous book, Alice's Adventures in Wonderland, in 1865. The story of Alice's adventures was first told by Dodgson to the three daughters of H. G. Liddell, then the dean at Christ Church. Alice's adventures continued in 1871 in its sequel Through the Looking-Glass. His other works include the peoms Jabberwocky and The Hunting of the Snark.

Dodgson's work, including books written for children, is filled with logical puzzles and paradoxes. Many of the logic puzzles that appeared in his work and in personal correspondence are well-known today.

Do not read any further unless you want the solutions to the four puzzles presented in A Common Thread.

Milky Water
Your are given two glasses, one containing exactly 50 tablespoons of milk, the other containing exactly 50 tablespoons of water. You take one tablespoon of out of the milk glass and mix it with the water. You then take one tablespoon of the water/milk mixture and mix it into the pure milk to obtain a milk/water mixture. Are you left with more water in the milk/water mixture or more milk in the water/milk mixture?
Solution (pun intended): There is exactly the same amount of water in the milk/water mixture as there is milk in the water/milk mixture.

Starting with 50 tablespoons of each, you remove one tablespoon from the milk and add it to the water. this leaves 49 tablespoons of pure milk, and 51 tablespoons of water/milk mixture, which is 1/51 milk and 50/51 water. You then take one tablespoon of the water/milk mixture and add it to the milk. This leaves 50 tablespoons of the water/milk mixture, which has a 1/51 ratio of milk to water.

When you add the tablespoon of 50/51 water/milk mixture to the 49 tablespoons of pure milk, you create a mixture that has a ratio of 1/51 water to milk. To see why this is so, consider that the one tablespoon of water/milk mixture has 51 parts, 50 of them water, and one milk. If you divide the 49 tablespoons of pure milk into parts of the same size as the 51 parts in the single water/milk tablespoon, you get

49 x 51 = 2,499

parts of pure milk. When you add the tablespoon of water/milk, you add one more milk part, and 50 water parts, for a mixture that is 50 parts water and 2,500 parts milk, or 1/51 water, 50/51 milk.

Update: Reader roryparle pointed out to me in the comments that my solution is too specific. My solution assumes that the mixtures of milk and water are mixed homogeneously, which is not necessary.
Starting from a mixture of 50 parts water + 1 part milk, and another container of 49 parts milk, you take one part from the mixture. This will have some fraction, f, of a part of milk, and some fraction (1 - f) of a single part of water (to make the whole add up to 1 part of something). The remaining mixture will contain (1 - f) part milk (it had 1 to begin with and you removed f) and (49 + f) parts water (50 - (1 - f) = 50 - 1 + f = 49 + f).

Add the spoon you've just removed to the milk and you'll have 49 + f parts milk (49 that was there + f from the spoon) and (1 - f) parts water (all from the spoon).

This works for the fraction you assumed, f = 1/51, but also for the cases where you get no milk in the second spoon (f = 0), or you miraculously manage to completely separate the milk and water again (f = 1), or anything in between.
Thanks for the correction! It's great to know that people actually read these things. :)

Four to Five

Make a word ladder starting with FOUR and ending with FIVE. (Every step in a word ladder differs by only one letter from the previous step, but each step must be an English word. You may add a letter, remove a letter, or change a letter, but the words from one step to the next must differ by only one letter.)
Solution: This word ladder looks deceptively simple because it contains only four letters, but it is made more difficult by the fact that you need to change one of the letters, the third, at three different points in the ladder (in this particular solution; there are other solutions).

FOUR → FOUL → FOOL → FOOT → FORT → FORE → FIRE → FIVE

Update: Sharp-eyed reader Xetius pointed out in the comments that there is a shorter solution given the rules above.

FOUR → FOR → FIR → FIRE → FIVE

It seems that Dodgson's original rules for word ladders (he invented the game itself, not just this instance) didn't include the rules for adding and removing letters.

Clock Face

A clock face has the same symbol for all twelve hours, and both hands are exactly the same length (there is no second hand, only an hour hand and a minute hand). The clock stands opposite to a mirror. At what time between 6 and 7 o'clock (not inclusive) will the time read exactly the same on the clock as in the mirror?
Solution: This is a problem in visualization and symmetry. The clock face in the puzzle will read the same as its mirror-image when the left and right halves of the clock face are the same. That will be the case when the hands of the clock are in the position shown in the following illustration.

But at exactly what time will that occur? The clock face can be divided into 360 degrees, with the minute hand advancing at a rate of

360 degrees / hour
6 degrees / minute
1/10 degree / second

The hour hand advances at a rate of

30 degrees / hour
1/2 degree / minute
1/120 degree / second

If you draw a vertical line down the center of the clock face, then look at the angle that each hand of the clock advances to get to the symmetric position, you can see that the two angles add up to 180 degrees.

Now if we take X to be the amount of time elapsed, we can build the following formula:

(X * 1/10 deg/sec) + (X * 1/120 deg/sec) = 180 deg

Solving for X, we get:

X * (1/10 deg/sec + 1/120 deg/sec) = 180 deg
X = 180 deg / (1/10 deg/sec + 1/120 deg/sec)
X = 180 deg / (12/120 deg/sec + 1/120 deg/sec)
X = 180 deg / (13/120 deg/sec)

The next step is a little tricky if you haven't taken an algebra class in awhile. In order to get rid of the degrees and be left with an elapsed time, you need to multiply both the numerator and denominator by the reciprocal of the denominator. This is the same as multiplying the entire right-hand side by one.

X = (180 deg * 120/13 sec/deg) / (13/120 deg/sec * 120/13 sec/deg)

Since 13/120 deg/sec and 120/13 sec/deg are reciprocals of one another, multiplying them together results in 1, cancelling out the denominator. We are left with

X = (180 deg * 120/13 sec/deg)

Since we have degrees multiplied by seconds/degree, the degrees cancel and we're left with seconds.

X = 180 * 120/13 sec
X = 21600/13 seconds
X = 360/13 minutes

So the exact answer is 360/13 minutes after 6 o'clock, which is approximately 27 minutes and 42 seconds past six.

Ravens and Writing Desks

Why is a raven like a writing desk?
Solution: Dodgson didn't have a solution in mind at the time that he wrote this riddle, which first appeared in Alice's Adventures in Wonderland (in chapter 7, A Mad Tea Party), but he later came up with:
Because it can produce a few notes, though they are very flat; and it is nevar put wrong end in front!
which appeared in a later printing of the book. Note the alternate spelling of "nevar", which is "raven" spelled backwards.

Another famous puzzler, Sam Lloyd, proposed a clever alternate solution:
Because Poe wrote on both.

Notes:

The photograph of Dodgson above was taken by Oscar Gustav Rejlander, a pioneer in early photography and a friend of Dodgon's. It was Rejlander who inspired Dodgson to take up amateur photography himself.

For more information on the life and work of Charles Dodgson, read Lewis Carroll in Numberland: His Fantastical Mathematical Logical Life, by Robin Wilson.

## Saturday, August 8, 2009

Read the following four logic puzzles and tell me what they all have in common.

Milky Water
Your are given two glasses, one containing exactly 50 tablespoons of milk, the other containing exactly 50 tablespoons of water. You take one tablespoon of out of the milk glass and mix it with the water. You then take one tablespoon of the water/milk mixture and mix it into the pure milk to obtain a milk/water mixture. Are you left with more water in the milk/water mixture or more milk in the water/milk mixture?

Four to Five
Make a word ladder starting with FOUR and ending with FIVE. (Every step in a word ladder differs by only one letter from the previous step, but each step must be an English word. You may add a letter, remove a letter, or change a letter, but the words from one step to the next must differ by only one letter.)

Clock Face
A clock face has the same symbol for all twelve hours, and both hands are exactly the same length (there is no second hand, only an hour hand and a minute hand). The clock stands opposite to a mirror. At what time between 6 and 7 o'clock will the time read exactly the same on the clock as in the mirror?

Ravens and Writing Desks
Why is a raven like a writing desk?

Before you answer something very general like "they're all word problems" or "they're all logic puzzles," I'll tell you that the common thread that I have in mind is something very specific. I'll have the answer to the four puzzles and what they have in common in an upcoming post.

## Sunday, August 2, 2009

### How Many Triangles?

In a previous post, How many squares are there on a chess board?, I closed with the following challenge:

How many triangles (of all sizes) do you see in the equilateral triangle below?

A lot of people attempted a solution, and a few got it right, but this puzzle proved a bit more challenging than counting the squares on a chessboard so it's time to give the full solution. It might seem like a simple task of counting up the triangles, but it's even harder to keep track of which triangles you've already counted than it was with squares. In addition to that, I'm always much more interested in a general approach to a puzzle than I am in the solution to a specific instance of the puzzle.

Before we begin, let's get a bit of terminology out of the way. I'll be referring to each specific instance of this problem by the number of unit-triangles at its base. The unit-triangle is the smallest triangle in each image, and the base is the number of unit-triangles along the bottom edge. In the image above, there are five unit-triangles in the base. Let's call the number of unit-triangles in an image u(n), where n is the number of unit-triangles in the base, and the total number of triangles in an image T(n).

Starting at the beginning, we see that the simplest case consists of only one triangle.

u(1) = 1
T(1) = 1

Next we have a triangle that has two triangles at its base. Counting the unit-triangles we get four, plus the larger triangle they form, for a total of five.

u(2) = 4
T(2) = 5

Next we move up to a base-3 triangle. You can see from the image below that it's made up of 9 units.

u(3) = 9

In addition, there are three base-2 triangles (one in each corner, see images below), plus the base-3 triangle itself, for a total of 13.

T(3) = 13

At this point you should note that any base-n triangle consists of three base-(n-1) triangles, one for each corner. The only exception to this rule is at base-2, which we saw consists of four base-1 triangles, one for each corner and one in the middle. From here on, I won't illustrate the three corner base-(n-1) triangles.

A triangle with a base of four units consists of itself, 16 units, seven base-2 triangles, and the three base-3 triangles in each corner, for a total of 27.

u(4) = 16
T(4) = 27

I won't illustrate all seven of the base-2 triangles, but many people do miscount them, so I'll list them by their numbered units to help you visualize them.

{ 1, 2, 3, 4 }
{ 2, 5, 6, 7 }
{ 4, 7, 8, 9 }
{ 5, 10, 11, 12 }
{ 7, 12, 13, 14 }
{ 9, 14, 15, 16 }
{ 6, 7, 8, 13 }

Note that the last triangle listed, { 6, 7, 8, 13 }, is a downward-pointing triangle. This is important because there are more of these as you increase the size of the base, and because many people overlook them while counting. Make sure that you can see all the triangles listed before continuing on.

Finally, we come to the base-5 triangle that we set out to solve at the beginning. It's made up of 25 units, 13 base-2 triangles, six base-3 triangles, three base-4 triangles in the corners, and itself for a total of 48 triangles.

u(5) = 25
T(5) = 48

I won't go through and illustrate all 48 of them, but hopefully the visual cues I provided in the previous illustrations help you to arrive at the same count that I did.

A General Formula

Now that we have the solutions to several small instances of the triangle problem, we have enough information to search for a general formula. Other than the fact that for each instance the number of unit-triangles is the square of the base, I don't see any interesting patterns in the sequence, so I'll skip directly to searching for one. Searching for the sequence 1, 5, 13, 27, 48 in the Online Encyclopedia of Integer Sequences leads me to this resource.

The comments identify this problem as
Number of triangles in triangular matchstick arrangement of side n.
which is a very general way of stating the original problem (where the problem was originally posed by laying out matchsticks on a table, rather than drawing triangles in an image editor).

The formula given for the sequence is:

T(n) = floor(n * (n + 2) * (2n + 1) / 8)

I could stop there, but I want to explain what the floor function is, and why it's needed in this case. The floor function in mathematics simply gives the largest integer less than or equal to its input. It simply rounds down to the nearest whole number (unless the input is already a whole number, in which case the output is exactly the same whole number as the input).

To see why we need to floor the results of this calculation, consider two things. First, when we're counting the triangles in the original image, I hope it's apparent that we will always come up with a whole number of triangles. That is, we'll never have some fractional part of a triangle left over. The answer will always be an integer value. Second, if we look at the results of the formula without using the floor function, we can see that it is needed.

f(n) = n * (n + 2) * (2n + 1) / 8
f(1) = 1 * (1 + 2) * (2*1 + 1) / 8 = 1.125
f(2) = 2 * (2 + 2) * (2*2 + 1) / 8 = 5.000
f(3) = 3 * (3 + 2) * (2*3 + 1) / 8 = 13.125
f(4) = 4 * (4 + 2) * (2*4 + 1) / 8 = 27.000
f(5) = 5 * (5 + 2) * (2*5 + 1) / 8 = 48.125

Note that when n is odd, there is always some a fractional remainder left over from applying the formula. Flooring the result removes this residue, giving us the same whole number answer we would arrive at by counting.

Since the remainder is always exactly equal to 1/8, we could get the same result by using two different formulas, one for even inputs, and one for odd inputs. This is the approach taken with the formulas given on on Wolfram MathWorld's Triangle Tiling article.

In Closing...

Congratulations to everyone who took the time to work through the solution to this problem. I'd like to thank everyone who left a comment on the original post. Your questions and comments made that one of the most fun (for me) posts I've written so far. I hope you enjoyed it as much as I did.