# Examples of "self-referential" sequences

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.

• This statement that I am making is a good example of a self-referential statement. Sep 11, 2016 at 17:59
• @Michael If only it was a sequence! Sep 11, 2016 at 18:00
• for my small understanding, could you please tell why it is fundamentally different from a sequence defined , for example , by the mean of the 4 previous elements ? TY very much
– user354674
Sep 11, 2016 at 18:09
• Look up the Kolakoski sequence.
– bof
Sep 12, 2016 at 10:48
• Thue-Morse Sep 12, 2016 at 12:22

$$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.

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).

• Very interesting examples, thanks! Oct 10, 2016 at 22:40

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.

• Given your explanation, did you mean to say "G(n)=G(n-G(n-1))"? Sep 12, 2016 at 13:04

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$.

• Do you have a Mathematica script for producing it? I tried f[n_] := Count[Table[f[n - 1], {n, 1, n - 2}], f[n - 1]], but that didn't work (I would have been surprised if it did, 'cause I never tried to define a recursive function in Mathematica before). Sep 12, 2016 at 10:58
• @Lovsovs: ahah, I was just trying to produce such a Mathematica script... without any success for now! Sep 12, 2016 at 10:59
• Here it is: f = 2; f[n_] := Count[Table[f[k - 1], {k, 2, n - 1}], f[n - 1]]; Table[f[n], {n, 1, 20}]! But it takes an extreme amount of power/time to calculate it! Sep 12, 2016 at 11:53
• @Lovsovs Start the definition with f[n_]:=f[n]=...; in such a way it will remember what it did for $n-1$ and will use it for computing $f(n)$. E.g., up to $n=1000$ in 0.25 sec on my laptop. Sep 12, 2016 at 12:10
• Here is an animation of the sequence for different values of $k\in(0,50)$ (which is $x(1)$, i.e., the seed). Sep 12, 2016 at 17:30

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).

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