There are a number of integer sequences which are known to have a few "ordinary" size values, and then to suddenly grow at unbelievably fast rates. The TREE sequence is one of these sequences, which starts "1, 3" and then grows to an unimaginably large value which completely dwarfs even things like Graham's Number. Another example is given by the sequence of Ackermann numbers, which also has an extremely large third term, though not as large as that of TREE(3).

I'm interested in a variant of the above concept: integer sequences which seem to start off normally, then have one or a few values which then become mind-bogglingly large, and then which end up going back to "ordinary-sized" values for the rest of the sequence. Does anyone know of things like this which arise "naturally," perhaps in the context of graph theory or combinatorics or something similar?

Obviously one can construct sequences that fit this pattern by splicing things together, but I'm mostly interested in the case where this behavior somehow occurs in some kind of natural integer sequence.

  • 9
    $\begingroup$ The number of regular polytopes in $n$-dimensions comes to mind: $$1,\ \infty,\ 5,\ 6,\ 3,\ 3, \cdots$$ Not really an integer sequence though. $\endgroup$ – EuYu Feb 20 '13 at 8:24

Goodstein sequences provide a fine example.

  • 3
    $\begingroup$ It may be worth noting that the general shape of all Goodstein sequences whose "ordinal descent" passes through ω^2 is "piecewise linear", starting off with linear segments that increase most rapidly, then reach a long plateau, then decrease from this maximum all the way down to 0 in one very long linear segment. Some illustrations are in Wolfram's ANKOS wolframscience.com/nksonline/page-1163a-text?firstview=1 (It can be shown that in the entire sequence of terms, almost exactly 25% are increasing, almost exactly 25% equal the maximum, and 50% are decreasing.) $\endgroup$ – r.e.s. Feb 26 '13 at 15:03
  • 1
    $\begingroup$ Maybe these sequences don't quite meet the description "few" in "have one or a few values which then become mind-bogglingly large". $\endgroup$ – Marc van Leeuwen Feb 26 '13 at 17:58
  • 1
    $\begingroup$ @r.e.s., thank you --- I was not aware of these facts about Goodstein sequences. $\endgroup$ – Gerry Myerson Feb 26 '13 at 23:00
  • $\begingroup$ I should have made it clear that the linear segments begin when the decreasing ordinal sequence reaches ω^2, any earlier Goodstein sequence terms typically increasing at much higher rates. Remarkably, virtually 100% of the terms occur after the one corresponding to ω^2, in a succession of increasingly long linear segments whose slopes are b-1, b-2, ...,1, 0, -1 (b being the base when the quadratic term appears, and the -1 being the slope of the final descent to 0). Some details are at sites.google.com/site/res0001/… $\endgroup$ – r.e.s. Feb 27 '13 at 2:18

Take the sequence where the $n$th term $g(n)$ is given by the number of groups of order $n$. We start: \begin{align*} g(1) &= 1\\ g(2) &= 1\\ g(3) &= 1\\ g(4) &= 2\\ &\vdots\\ g(14) &= 2\\ g(15) &= 1\\ g(16) &= \bf{14}\\ g(17) &= 1\\ &\vdots\\ g(30) &= 4\\ g(31) &= 1\\ g(32) &= \bf{51}\\ g(33) &= 1\\ &\vdots\\ g(1020) &= 37\\ g(1021) &= 1\\ g(1022) &= 4\\ g(1023) &= 2\\ g(1024) &= \bf{49487365422}\\ g(1025) &= 4\\ &\vdots \end{align*} Groups really love to have order a power of $2$! A more complete table can be found here.

  • $\begingroup$ Excellent answer! $\endgroup$ – Dylan Yott Jun 16 '13 at 22:50
  • $\begingroup$ The question asked for sequences that "end up going back to 'ordinary-sized' values for the rest of the sequence." This sequence continues to have ever more enormous values no matter how far out you go. $\endgroup$ – Gerry Myerson Dec 9 '15 at 22:20

The continued fraction expansion of $\pi$ begins: $3+\frac{1}{7+\frac{1}{15+\frac{1}{1+\frac{1}{292+\frac{1}{1+\frac{1}{1+\ldots}}}}}}$.

In condensed form and with more digits: $\pi = [3: 7, 15, 1, 292, 1, 1, 1, 2, \ldots]$. The $292$ is the interesting element of the sequence, and it corresponds to the following good rational approximation of $\pi \approx \frac{355}{113}$, comes from truncating the continued fraction at $15+1$, just before the $292$. Thanks to Gerry Myerson to pointing out my error here.

Does this sequence answer your question? Maybe. There is a theorem from real analysis using the ideas of ergodic theory that states, for almost every real number $x \in \mathbb R$, the natural number $n$ appears in the continued fraction expansion of $x$ with frequency $log_{2} \left ( \frac{(n+1)^{2}}{n(n+2)} \right )$.

This quantity clearly goes to zero as $n$ grows. However, I may be wrong but I don't think this forces the sequence to go to zero, but it certainly doesn't go to infinity.

The prove this fact, consider the Gauss measure $\nu (E) = \frac{1}{log(2)} \int_{0}^{1} \frac{1}{1+t} dt$, on $([0,1]\setminus \mathbb Q)$. Also consider the transformation $U(x)= \{\frac{1}{x}\}$, where $\{\}$ denotes fractional part. This transformation is ergodic, and from here proving the theorem is a straightforward application of the ergodic theorem.

  • $\begingroup$ The theorem is about almost every real number, not almost every rational number. Concerning the partial quotients of $\pi$, very little is known, but it is expected that there are arbitrarily large ones. The especially good rational approximations come from stopping just before a big partial quotient; there's nothing especially good about stopping after $292+1$. $\endgroup$ – Gerry Myerson Feb 25 '13 at 12:26
  • $\begingroup$ Wow, that's absolutely right, let me edit this. $\endgroup$ – Dylan Yott Feb 26 '13 at 13:52
  • $\begingroup$ @Gerry Myerson. A statement about almost every rational number would be quite boring. Also thanks for pointing out that I was truncating at the wrong step, that was a bit silly. $\endgroup$ – Dylan Yott Feb 26 '13 at 13:57
  • $\begingroup$ The continued fraction for $\root3\of5$ also has a large partial quotient early on, $ [1,1,2,2,4,3,3,1,5,1,1,4,10,17,1,14,1,1,3052,1,\dots]$. $\endgroup$ – Gerry Myerson Feb 13 '19 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.