Automatic sequence
In mathematics and theoretical computer science, an automatic sequence (also called a k-automatic sequence or a k-recognizable sequence when one wants to indicate that the base of the numerals used is k) is an infinite sequence of terms characterized by a finite automaton. The n-th term of an automatic sequence a(n) is a mapping of the final state reached in a finite automaton accepting the digits of the number n in some fixed base k.
An automatic set is a set of non-negative integers S for which the sequence of values of its characteristic function χS is an automatic sequence; that is, S is k-automatic if χS(n) is k-automatic, where χS(n) = 1 if n S and 0 otherwise.
Automatic sequences may be defined in a number of ways, all of which are equivalent. Four common definitions are as follows.
Let k be a positive integer, and let D = (Q, Σk, δ, q0, Δ, τ) be a deterministic finite automaton with output, where
Extend the transition function δ from acting on single digits to acting on strings of digits by defining the action of δ on a string s consisting of digits s1s2...st as:
Define a function a from the set of positive integers to the output alphabet Δ as follows:
where s(n) is n written in base k. Then the sequence a = a(1)a(2)a(3)... is a k-automatic sequence.
An automaton reading the base k digits of s(n) starting with the most significant digit is said to be direct reading, while an automaton starting with the least significant digit is reverse reading. The above definition holds whether s(n) is direct or reverse reading.
...
Wikipedia