Getting Help

In my last post, I described a problem I encountered more than twenty years ago, and my recent attempt at solving it. The problem:

Partition the numbers from 1 to 2n into pairs, so that the sum of the numbers in each pair is a perfect square. For what numbers is this possible?

I decided to answer the question by writing a program. As it turned out, that was harder than I thought it would be. I had a fair amount of experience doing this by hand, but that was not sufficient to yield a valid algorithm, given my limited programming skills. So I did what I usually do when I am stuck: I asked for help.

My son NeilFred Picciotto, who is a software engineer by profession, talked to me for a while about how to do this using recursion, and ended the lesson by saying that I would get more out of this project if I implemented those ideas on my own. And he was right! I learned a lot by doing it, and it was more satisfying than having him guide me by the nose the whole way. (His explanations were very helpful in getting me going, but they were appropriately general.)

And guess what: to my utter surprise, after 22, this problem can be solved with every even number! Or at any rate, every even number up to 2000 or so, which is where my program crashed, complaining that there was “too much recursion”.

Here is a Python-generated answer for 30:
(30, 19), (29, 20), (28, 21), (27, 22), (26, 23), (25, 24),
(18, 7), (17, 8), (16, 9),
(15, 1), (14, 2), (13, 3), (12, 4), (11, 5), (10, 6)

This of course led me to the next question: proving that this will always work after 22. Again, I was stumped, and after a while, I asked for help from a number theorist I know, Kiran Kedlaya. He figured this out quickly. His strategy was to build each solution from a smaller one, according to a consistent system that is sure to keep working. His approach required the numbers up to 60 to be done by hand, or by computer. You can see an outline of his proof in the Online Encyclopedia of Integer Sequences (OEIS), for sequence A253472. In order to fully understand Kiran’s strategy, I applied it to the corresponding problem for odd numbers (making pairs out of the numbers from 0 to 2n-1.) Again, it was satisfying to wrap this up on my own.

This brings us close to the end of the story.

When I shared the problem with Joshua Zucker, he told me that I was not the first to think about it, and directed me to a couple of references (which I added to the OEIS entry, so you can find them there.)

When I shared the problem with Gord Hamilton, he came up with a beautiful way to illustrate it, and with a different approach to how one might present it in the classroom. See his images and read about his approach in this week’s NumberPlay post at the New York Times.

–Henri