First, a warning: this may be my geekiest post ever. If you want to give it a pass, you won’t hurt my feelings. In fact, I found a bunch of fluffy cats for you if you would prefer.

Anywhoo, I frequent a Web site called FiveThirtyEight.com that is about statistics and math, and applying them to sports and politics. On Fridays, they pose little (and not-so-little) math challenges for readers. A couple of weeks ago, they posed a question about numbers that were the difference between two perfect squares. As I was reading the question an ad came up to the side, pointing out that 4² = 1 + 3 + 5 + 7.

The mandate was clear: solve the puzzle, using the information in the ad.

I noodled on the problem idly for a while, and came up with some interesting observations, but it wasn’t until I really, really couldn’t sleep the night before last that I lay in the darkness and chewed on the puzzle (long after the submission deadline to receive accolades on the site, but that’s not what matters).

The question is here, but I’ll copy the relevant chunk for you:

Benjamin likes numbers that can be written as the difference between two perfect squares. He thinks they’re hip. For example, the number 40 is hip, since it equals 7²−3², or 49−9. But hold the phone, 40 is doubly hip, because it also equals 11²−9², or 121−81.

With apologies to Douglas Adams, 42 is not particularly hip. Go ahead and try finding two perfect squares whose difference is 42. I’ll wait.

Now, Benjamin is upping the stakes. He wants to know just how hip 1,400 might be. Can you do him a favor, and figure out how many ways 1,400 can be written as the difference of two perfect squares? Benjamin will really appreciate it.

Let’s do this! First we need to dig a little deeper into the information in the advertisement: 4² = 1 + 3 + 5 + 7. It turns out you can make this into a rule: a² = the sum of the first a odd integers. 12² is the sum of the first 12 odd integers, and so forth.

That’s pretty interesting, but the question was about the difference between two perfect squares, and that’s actually where the fun begins (for certain values of fun).

Consider 5² – 3². It’s the first five odd integers, minus the first three odd integers, leaving us with 7 + 9 = 16. The subtracted square cancels out part of the series of odd integers, and the difference is the sum of the ones left over.

So now we know that the difference between two squares can always be expressed as the sum of consecutive odd integers. And we also know that every series of consecutive odd integers sums to the difference between two squares.

Fun fact: Every odd number can be expressed as the difference between two squares: There will always be a value of a where a² – (a-1)² = n, where n is our odd number. Crazy!

A little side trip here to button things down: 5+7+9 adds up to a difference between what two perfect squares, a² – b²? Knowing how to figure this will come in handy later to check assumptions. 9 is the fifth odd integer, so we know a is 5. We can solve that for any series that ends with n to say that a = (n+1)/2. The series we’re working on here is three numbers long, so we can quickly surmise that b = a – 3, or more generally, b = a – l, where l is the length of the series. In this case, 5 + 7 + 9 = 5² – 2² = 21.

So now with that info in hand, we can turn to the actual question, but rephrase it “how many different series of consecutive odd integers add up to 1400?”

This is how far I’d gotten on the problem before the long, terrible, sleepless night. A computational solution would be easy at that point, just walking the numbers and testing the results. I wanted to find an analytical solution, but I kind of assumed it would be beyond me, or that series of odd numbers wouldn’t lend itself to such a generalization.

Wide awake in the darkness at 2am, I started to think about the problem from a programming standpoint, trying to optimize the algorithm. What else do you do when you can’t sleep, amirite?

First Optimization: know when to stop. There’s no point in testing the sum of a series after any term goes past half the total.

Second Optimization: The target number is even, so there’s no point testing series with an odd number of terms.

In fact… somewhere around 3:00 am I found the twist from a computational approach to an analytical one, merely by using the optimizations and discarding the code.

If the series of consecutive odd integers has two terms that add up to 1400, then they must be centered on 1400/2. If there is a series of four consecutive integers that add up to 1400, those numbers must be centered on 1400/4.

Let’s look a little deeper at the simplest case to deconstruct what that all means. 1400/2 = 700. the series of odd integers that centers on 700 is (699, 701). Just for giggles we can confirm that ((701+1)/2)² – (((701+1)/2) – 2)² = 1400. And it does!

By 3:30, doodling number lines in my head, I had observed that what I was doing was factoring 1400. But there was a hitch – I considered the number 10. There aren’t two consecutive odd numbers centered around five. I realized that both factors have to be even. For an even number to be the difference of two squares, it has to be a multiple of four. That’s why 42 is not hip.

So now we can finally get to the answer to the Riddler puzzle, by answering, “how many unique pairs of even factors does 1400 have?” To answer that, we can reduce 1400 to its prime factors, and count the different ways to arrange them into two buckets. 1400 is 2³ x 5² x 7. Since both factors must be even, there must be a 2 in each bucket. That means there are two ways to distribute the remaining 2 (either in one bucket or the other), three ways to distribute the three 5’s (two in one bucket, one in each, or two in the other bucket), and two ways to distribute the 7. That means 2 x 3 x 2 ways to allocate the remaining factors. But there’s one final hitch, because that method will yield both 2 x 700 and 700 x 2. So the final answer is half of that, or 6.

There are six pairs of integers, a and b, such that a² – b² = 1400.

• 2 x 700 = 699 + 701 = 351² – 349² = 1400
• 4 x 350 = 347 + 349 + 351 + 353 = 177² – 173² = 1400
• 10 x 140 = 131 + 133 + 135 + 137 + 139 + 141 + 143 + 145 + 147 + 149 = 75² – 65² = 1400
• and three other examples that are too long to fit here.

I didn’t do the actual factoring that night; by then it was 4:30. But I knew how to get the answer, for that or any number. To find the solution for odd numbers the process is similar, but the length of the number series will always be odd, and obviously there will be no even factors.

There are simpler ways to solve this problem, but I’m pleased that I could put a mostly-useless factoid from an advertisement to good use, right on the Web page it was displayed on. And yesterday involved a whole lot of caffeine.

3

Sweet!

Thanks!