Examples of "self-referential" sequences

Question

I recently found the so-called Van Eck's sequence, in which $a(n)$ is the answer to the question "except for $a_{n-1}$ itself, how far back did we last see $a_{n-1}$?" ($a_n=0$ if $ a_{n-1}$ never appeared before):

$$0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5, 3, 0, 3, 2, 9, 0, 4, 9, 3, 6, 14, 0, 6, 3, 5,\dots$$

I'm intrigued by the idea that the sequence is created by considering a feature of the sequence itself - it is self-referential in a funny way, almost circularly defined. I'm having a hard time pinning down this characteristic precisely, so forgive me the vagueness of the question:

What are some examples of other such "self-referential" sequences?

I tried creating some myself, but they turned out to be not very interesting. For instance, "$a_n$ is the number of sub-sequences in $(a)_1^{n-1}$ that are $a_{n-1}$ long" is just $1,1,2,2,3,4,5,6,\dots$

Homemade sequences are also very welcome!

---

Edit: I just found the look-and-say sequence, which is also rather neat:

$$1, 11, 21, 1211, 111221, 312211, 13112221,\dots,$$ which is constructed by enumerating the number of certain numbers in a row found in the previous entry, i.e., the second entry is "one $1 =11$", the third is "two $1$s $=21$", etc.

Answer 1

$$1, 2,2, 1,1, 2,1, 2,2,1, 2,2,1,1,2, 1,1,2,2,1,2,1, 2,1,2,2,1,1,2,1,1,2, 1,1,2,1,1,2,2,1,2\dots$$ The Kolakoski sequence (OEIS sequence A000002) is the infinite sequence $a_1,a_2,a_3,a_4,a_5,\dots$ of ones and twos consisting of a block of $a_1$ ones followed by a block of $a_2$ twos, then $a_3$ ones, $a_4$ twos, $a_5$ ones, and so on. It is an unproven conjecture that the sequence contains equal proportions of ones and twos, i.e., that $$\lim_{n\to\infty}\frac{a_1+a_2+\cdots+a_n}n=1.5$$ Another unproven conjecture is that the finite subwords of the Kolakoski sequence can be characterized as the so-called $C^\infty$-words; see
William D. Weakley, On the number of $C^\infty$-words of each length, Journal of Combinatorial Theory Serie A 51 (1989), 55–62
and
Yun Bao Huang and William D. Weakley, A note on the complexity of $C^\infty$-words, Theoretical Computer Science 411 (2010), 3731–3735.

Answer 2

Sequences can be self-referential in a multitude of ways, and OEIS contains examples for quite a few of them. We're barely scratching the surface.

Can't believe nobody mentioned the Golomb's sequence: $a_n$ is the number of times $n$ occurs. It has relatively calm and ordered (that is, not chaotic) demeanor, but a peculiar growth order: $O(n^{\varphi-1})$. There are some links to related sequences, too.

Also, look at this little gem: $a_{n+1}=a_c+1$, where $c$ is the number of times $a_n$ appeared among the previous terms. It is unbounded, but grows mighty slowly (though admittedly not as slowly as Gijswijt's, you can't beat that).

Answer 3

Hofstadter Sequences include "Fibonacci-like" examples such as $$ G(n) = n - G(G(n-1))\, , $$ where the term needed to calculate the current value is found by counting back a number of steps equal to the previous value.

Answer 4

Here is a home-made sequence. I didn't find it on OEIS! Start with $x_1=2$, say. Then define $$x_{n+1} = |\{i \in \{1,\dots,n-1\} \;:\; x_i=x_n\}|$$ i.e. the number of times you see $x_n$ in $\{x_1,\dots,x_{n-1}\}$. For instance, you get: $$2,0,0,1,0,2,1,1,2,2,3,0,3,1,…$$

---

Starting with $x_1=1$, you get $$1,0,0,1,1,2,0,2,1,3,0,3,1,4,0,4,1,…,n,0,n,1,…$$ and with $x_1=2$, you get $$2,0,0,1,0,2,1,1,2,2,3,0,3,1,3,2,\; 4,0,4,1,4,2,\; 5,0,5,1,5,2,\;…,\; n,0,n,1,n,2, \; n+1,0,n+1,1,n+1,2, \;…$$

Starting with some $x_1 ≥ 1$ yields a sequence with the pattern $n,0,n,1,n,2,…,n,x_1$.

Answer 5

Aronson's sequence. Quoting from Wikipedia,

Aronson's sequence is an integer sequence defined by the English sentence "T is the first, fourth, eleventh, sixteenth, ... letter in this sentence." Spaces and punctuation are ignored. The first few numbers in the sequence are:

1, 4, 11, 16, 24, 29, 33, 35, 39, 45, 47, 51, 56, 58, 62, 64, 69, 73, 78, 80, 84, 89, 94, 99, 104, 111, 116, 122, 126, 131, 136, 142, 147, 158, 164, 169, ... (sequence A005224 in the OEIS).

There's more discussion at the Wikipedia page, with links to related sequences.

Answer 6

Fibonacci Sequence is self-referential:

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

...and is grounded with the definitions of the first two numbers:

F(0) = 0

F(1) = 1

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

https://en.wikipedia.org/wiki/Fibonacci_number

https://oeis.org/A000045

---

Leonardo numbers, related, are self-referential:

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

...and is grounded with the definitions of the first two numbers:

a(0) = 1

a(1) = 1

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, ...

https://en.wikipedia.org/wiki/Leonardo_number

https://oeis.org/A001595