Sunday, November 21, 2010

Numerical Sequence Puzzle

What's the next number in this sequence, and how is it determined?

1, 3, 5, 9, 15, 31, 61, 125, 251, 503, 1015, 2035, 4081, 8177, 16367, 32747, 65511, ?

Years ago I spent some time playing around with integer sequence puzzles. I ended up constructing a few puzzles based on ideas I had never seen used before. Sometime between 1995 and 1998 I published four of them in my user profile on the Free Internet Chess Server. Over the years since then I've had a number of people contact me with attempted solutions. A couple dozen or so people were able to solve three of them, but the one shown above remained unsolved for years. Several people submitted solutions that matched as far out as I had revealed terms but diverged later, so I kept publishing more and more terms hoping someone would be able to solve it.

Finally in 2006, someone sent me a solution that matched my sequence as far out as I cared to check. I recently discovered that the puzzle generated more activity than I realized. From what I have been able to piece together, one of the guys on the chess server who attempted to solve it posted the problem to http://forum.fok.nl/topic/267468 in 2003. People kept posting to that thread for almost two years, but nobody got the correct answer. Some of the attempts were relayed to me by the original poster, but he never referred me to the forum. Then, in 2005, someone reposted the puzzle to another forum. A few weeks later, someone posted the solution that was sent to me in 2006.

However, the specification for that solution was much more complicated than my original one. So I decided to post this problem here. I omitted the link to the post with the matching answer to encourage you to try it on your own. But I'm looking for the simple solution I originally used, which to my knowledge has not been published anywhere.

EDIT @ 22:07 on 11/21: And we have a winner. The first comment was submitted by Anonymous and had the correct answer. I'm curious whether (s)he derived it from the one already posted or figured it out from scratch.