Tuesday, May 11, 2004

A bizarre fast growing function

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

Disqus for The Geomblog