On-Line Encyclopedia of Integer Sequences - Self-referential Sequences

Self-referential Sequences

Very early in the history of the OEIS, sequences defined in terms of the numbering of sequences in the OEIS itself were proposed. "I resisted adding these sequences for a long time, partly out of a desire to maintain the dignity of the database, and partly because A22 was only known to 11 terms !" Sloane reminisced. One of the earliest self-referential sequences Sloane accepted into the OEIS was  A031135 (later  A091967) "a(n) = n-th term of sequence A_n". This sequence spurred progress on finding more terms of  A000022. Some sequences are both finite and listed in full (keywords "fini" and "full"); these sequences will not always be long enough to contain a term that corresponds to their OEIS sequence number. In this case the corresponding term a(n) of A091967 is undefined.  A100544 lists the first term given in sequence A_n, but it needs to be updated from time to time because of changing opinions on offsets. Listing instead term a(1) of sequence A_n might seem a good alternative if it weren't for the fact that some sequences have offsets of 2 and greater. This line of thought leads to the question "Does sequence A_n contain the number n ?" and the sequences  A053873, "Numbers n such that OEIS sequence A_n contains n", and  A053169, "n is in this sequence if and only if n is not in sequence A_n". Thus, the composite number 2808 is in A053873 because  A002808 is the sequence of composite numbers, while the non-prime 40 is in A053169 because it's not in A000040, the prime numbers. Each n is a member of exactly one of these two sequences, and in principle it can be determined which sequence each n belongs to, with two exceptions (related to the two sequences themselves):

• It cannot be determined whether 53873 is a member of A053873 or not. If it is in the sequence then by definition it should be; if it is not in the sequence then (again, by definition) it should not be.
• It can be proved that 53169 both is and is not a member of A053169. If it is in the sequence then it should not be; if it is not in the sequence then it should be. This is a form of Russell's paradox.