How hard could this be? Q(n)…

An interesting talk tomorrow in NJ, by Douglas Hofstadter…


In 1963, while playing a novel number-theoretical game with a friend, I dreamt up a curious recursive definition for an integer-valued function, which I dubbed “Q(n)”. Here is the recursion:

Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2))

The two initial values I supplied were Q(1) = 1 and Q(2) = 1. This function’s behavior turned out to be very unpredictable. I spent a good deal of time exploring it computationally, and also invented and explored some variations on the theme. To my frustration, though, I wasn’t able to prove anything about Q(n) (not even that it existed for all positive values of n!), no matter how hard I worked. Eventually, as often tends to happen when one has pushed oneself as far as one can go and has hit up against one’s limits, Q(n) slowly faded into the background of my life. Many years later, my mathematician/physicist
friend Greg Huber proposed that we go back to the canonical and very natural but unsolved questions about the mysterious function Q(n), with its magnetic appeal and crystalline beauty, and carefully study them. I went for Greg’s bait hook, line, and sinker, but soon I found, to my great frustration, that unlike Greg, who had made some small progress analytically, I was completely unable to prove anything analytically about Q(n). Soon Greg found himself in a similar position of frustration. After a period of stagnation, finding ourselves in a box canyon with no escape route except using a computer to do experimental mathematics, together he and I invented a two-parameter family of functions closely related to Q(n) and we explored their behavior computationally. We found some delightful surprises and some deep insights. However, despite all the progress, a lot of mystery remained (and still remains). In this talk, I will mainly describe Greg Huber’s and my collaborative discoveries.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s