Ackermann's function is a familar fast growing function to any of us who have studied the union-find data structure. Here is a sequence from Neil Sloane's Sequence Encyclopedia that has some intriguing growth properties.
Sequence A090822
a(1) = 1; for n>1, a(n) = largest integer k such that the word
a(1)a(2)...a(n-1) is of the form xy^k for words x and y
(where y has positive length), i.e. the maximal number of repeating
blocks at the end of the sequence so far.
The sequence goes 1,1,2,1,1,2,2,2,3,1,1,2,.....
The first time 4 occurs is at position 220, and the first time N occurs is
roughly near (2^(2^(3^(4^...(^N)))). It seems strange that such an
innocent-looking sequence has such bizarre behaviour.
For more on fast growing functions, definitely read Scott Aaronson's Busy Beaver article.
Update (7/20/2004): There is now a paper on this sequence proving that it is unbounded.
No comments:
Post a Comment