It is reminiscent of the Fibonacci definition in that each new value is a sum
of two previous values-but not of the immediately previous two values.
Instead, the two immediately previous values tell how far to count back
to obtain the numbers to be added to make the new value! The first 17
Q-numbers run as follows:1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8,- 5+6=11 •
~
new term
10, 9, 10, ...
~
how far to move
to the leftTo obtain the next one, move leftwards (from the three dots) respectively
10 and 9 terms; you will hit a 5 and a 6, shown by the arrows. Their
sum-II-yields the new value: Q( 18). This is the strange process by which
the list of known Q-numbers is w;ed to extend itself. The resulting se-
quence is, to put it mildly, erratic. The further out you go, the less sense it
seems to make. This is one of those very peculiar cases where what seems to
be a somewhat natural definition leads to extremely puzzling behavior:
chaos produced in a very orderly manner. One is naturally led to wonder
whether the apparent chaos conceals some subtle regularity. Of course, by
definition, there is regularity, but what is of interest is whether there is
another way of characterizing this sequence-and with luck, a nonrecursive
way.
Two Striking Recursive GraphsThe marvels of recursion in mathematics are innumerable, and it is not my
purpose to present them all. However, there are a couple of particularly
striking examples from my own experience which I feel are worth present-
ing. They are both graphs. One came up in the course of some number-
theoretical investigations. The other came up in the course of my Ph.D.
thesis work, in solid state physics. What is truly fascinating is that the
graphs are closely related.
The first one (Fig. 32) is a graph of a function which I call INT(x). It is
plotted here for x between ° and 1. For x between any other pair of
integers nand n + 1, you just find INT(x-n), then add n back. The
structure of the plot is quite jumpy. as you can see. It consists of an infinite
number of curved pieces, which get smaller and smaller towards the
corners-and incidentally, less and less curved. Now if you look closely at
each such piece, you will find that it is actually a copy of the full graph,
merely curved! The implications are wild. One of them is that the graph of
INT consists of nothing but copies of itself, nested down infinitely deeply.
If you pick up any piece of the graph, no matter how small, you are holding
a complete copy of the whole graph-in fact, infinitely many copies of it!
The fact that INT consists of nothing but copies of itself might make
you think it is too ephemeral to exist. Its definition sounds too circular.Recursive Structures and Processes