Today while reading a math puzzle column I have mentioned before, I learned two things.
First, there is a mathematical concept called a derangement. Second, there is (or at least was) a publication called Journal of Recreational Mathematics, which is about the best title for any publication ever. Were I remotely qualified, I would revive it, but I’m actually not even qualified to subscribe to it.
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 42 = 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 72−32, or 49−9. But hold the phone, 40 is doubly hip, because it also equals 112−92, 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: 42 = 1 + 3 + 5 + 7. It turns out you can make this into a rule: a2 = the sum of the first a odd integers. 122 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 52 – 32. 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 a2 – (a-1)2 = 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, a2 – b2? 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 = 52 – 22 = 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)2 – (((701+1)/2) – 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 23 x 52 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 a2 – b2 = 1400.
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.
A few weeks ago I was in a fabric store with the Official Sweetie of Muddled Ramblings and Half-Baked Ideas. My mission was to select the fabric for my holiday shirts. While I was poring over the seasonal offerings, and surprising OS with my sparkly decisions, there was a woman in the same section with her kid installed in her shopping cart.
That kid never stopped talking, and I’d guess that 90% of all utterances were questions. Mom tried to answer most of them, but deflected many.
I was in a time warp, looking at me and my mother, possibly on the shopping trip where I picked out the double-breasted suit pattern, the busy blue/purple pinstripe fabric for the jacket, and the fuchsia double-knit for the trousers of my Easter outfit when I was eight years old, give or take.
OSoMR&HBI has seen pictures of that outfit, so sparkly reindeer shirts should not have surprised her quite so much, my normal attire notwithstanding. You gotta sparkle for the holidays.
Anyway, while I was poking through the fabric options, the kid was offering up a never-ending stream of questions. Based on some of the questions, I got the feeling that we were on similar missions. While I can’t specifically remember any of his fabric-related questions, they were in the vein of “Why is it snowing on the dog?” Questions that really don’t have an answer.
Then for a while he asked simple mathematical questions, which his mother answered easily. “What is five plus fifteen?” “What is five plus twenty?”
Then he dropped the bomb. “What number do you get when you add up all the numbers?”
Getting no swift answer from his mother, the kid grappled with the question himself for a little while, naming a couple of very large numbers, quieter now as he realized that those were numbers too, and part of all the numbers, sensing rather than knowing that he was touching on a deeper sort of mathematics. He had asked a question it took mankind almost our entire history so far to even know how to ask, let alone how to answer.
I did not go over and accost mother and son and congratulate the kid on asking a massively awesome question, and tell the frazzled mom that her child was destined to grow up to be like me. She’ll find out soon enough, for better or for worse.
But I got to climb into a time machine that day, and see myself and my patient mother from the point of view of an aging man who still likes to sparkle now and then. It made me irrationally happy to know that in fabric stores, the impossible questions were still being asked.
I’m in a bar right now, and it’s not crowded. Nearby a group of maybe ten people has collected. They are clustered around a table, wedging in new arrivals rather than annex nearby unoccupied tables and pull them into the party.
Why not spread out? Why not bring in tables so that all involved have a place to set their glass? Let me tell you a little more about the group.
This is a gathering of geeks. ebay, if clothing is an indicator. (This group is indirectly responsible, then, for the recent debt I incurred. I forgive them.) Tech workers of varied ethnicity, having drinks and appetizers.
Two of them are female. The other nine (I’ve counted now) are all working to minimize the distance between themselves and the the non-Y-bearing nucleus of the group.
Only it’s not so simple. Allow me to expand on that theorem. The males (hereafter referred to as ‘dudes’) are actually competing for the closest eye contact with the females (or, ‘chicks’). Dudes don’t just want proximity, they want attention. This leads to a kidney-bean shaped cluster, as the value of space drops dramatically once out of the peripheral vision of the two chicks. Good thing, too; otherwise my little island of tranquility, directly behind the chicks, would be impinged upon by careless geek elbows.
One of the two chicks just shifted her posture inward, slicing off a section of the kidney bean. The isolated bunch immediately began talking about football.
