Disjunctive sequence

---

title: "Disjunctive sequence" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["sequences-and-series"] description: "Sequence in which every finite string appears as a subsequence" topic_path: "general/sequences-and-series" source: "https://en.wikipedia.org/wiki/Disjunctive_sequence" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Sequence in which every finite string appears as a subsequence ::

A disjunctive sequence is an infinite sequence of characters drawn from a finite alphabet, in which every finite string appears as a substring. For instance, the Champernowne constant defined by concatenating the base-10 representations of the positive integers: : clearly contains all the strings and so is disjunctive.

Any normal sequence (a sequence in which each string of equal length appears with equal frequency) is disjunctive, but the converse is not true. For example, letting 0n denote the string of length n consisting of all 0s, consider the sequence

:0\ 0^1\ 1\ 0^2\ 00\ 0^4\ 01\ 0^8\ 10\ 0^{16}\ 11\ 0^{32}\ 000\ 0^{64}\ldots

obtained by splicing exponentially long strings of 0s into the shortlex ordering of all binary strings. Most of this sequence consists of long runs of 0s, and so it is not normal, but it is still disjunctive.

The complexity function of a disjunctive sequence S over an alphabet of size k is p**S(n) = k**n.

A disjunctive sequence is recurrent but never uniformly recurrent/almost periodic.

Examples

The following result | last1 = Calude | first1 = C. | author1-link = Cristian S. Calude | last2 = Priese | first2 = L. | author2-link = Lutz Priese | last3 = Staiger | first3 = L. | author3-link = Ludwig Staiger | publisher = University of Auckland, New Zealand | pages = 1–35 | title = Disjunctive sequences: An overview | year = 1997 | citeseerx = 10.1.1.34.1370 }} | last1 = Istrate | first1 = G. | author1-link = Gabriel Istrate | last2 = Păun | first2 = Gh. | author2-link = Gheorghe Păun | journal = Discrete Applied Mathematics | pages = 83–86 | title = Some combinatorial properties of self-reading sequences | volume = 55 | doi = 10.1016/0166-218X(94)90037-X | year = 1994 | zbl=0941.68656 | doi-access =

:If a1, a2, a3, ..., is a strictly increasing infinite sequence of positive integers such that n → ∞ (a**n+1 / a**n) = 1, :then for any positive integer m and any integer base b ≥ 2, there is an a**n whose expression in base b starts with the expression of m in base b. :(Consequently, the infinite sequence obtained by concatenating the base-b expressions for a1, a2, a3, ..., is disjunctive over the alphabet {0, 1, ..., b-1}.)

Two simple cases illustrate this result:

• a**n = n**k, where k is a fixed positive integer. (In this case, n → ∞ (a**n+1 / a**n) = n → ∞ ( (n+1)k / n**k ) = n → ∞ (1 + 1/n)k = 1.) : E.g., using base-ten expressions, the sequences :: 123456789101112... (k = 1, positive natural numbers), :: 1491625364964... (k = 2, squares), :: 182764125216343... (k = 3, cubes), :: etc., :are disjunctive on {0,1,2,3,4,5,6,7,8,9}.
• a**n = p**n, where p**n is the nth prime number. (In this case, n → ∞ (a**n+1 / a**n) = 1 is a consequence of p**n ~ n ln n.) : E.g., the sequences :: 23571113171923... (using base ten), :: 10111011111011110110001 ... (using base two), :: etc., are disjunctive on the respective digit sets.

Another result{{citation | last1 = Nakai | first1 = Yoshinobu | author1-link = Yoshinobu Nakai | last2 = Shiokawa | first2 = Iekata | author2-link = Iekata Shiokawa | journal = Acta Arithmetica | pages = 271–284 | title = Discrepancy estimates for a class of normal numbers | volume = LXII.3 | issue = 3 | url = http://matwbn.icm.edu.pl/ksiazki/aa/aa62/aa6235.pdf | year = 1992 | doi = 10.4064/aa-62-3-271-284 | doi-access = free}} that provides a variety of disjunctive sequences is as follows: :If a**n = (f(n)), where f is any non-constant polynomial with real coefficients such that f(x) 0 for all x 0, :then the concatenation a1a2a**3... (with the a**n expressed in base b) is a normal sequence in base b, and is therefore disjunctive on {0, 1, ..., b-1}.

E.g., using base-ten expressions, the sequences :: 818429218031851879211521610... (with f(x) = 2x3 - 5x2 + 11x ) :: 591215182124273034... (with f(x) = πx + e) are disjunctive on {0,1,2,3,4,5,6,7,8,9}.

Rich numbers

A rich number or disjunctive number is a real number whose expansion with respect to some base b is a disjunctive sequence over the alphabet {0,...,b−1}. Every normal number in base b is disjunctive but not conversely. The real number x is rich in base b if and only if the set { x bn mod 1} is dense in the unit interval.

Lexicon A number that is disjunctive to every base is called absolutely disjunctive or is said to be a lexicon. Every string in every alphabet occurs within a lexicon. A set is called "comeager" or "residual" if it contains the intersection of a countable family of open dense sets. The set of absolutely disjunctive reals is residual. It is conjectured that every real irrational algebraic number is absolutely disjunctive.

Notes

References

References

1. Bugeaud (2012) p.91
2. Bugeaud (2012) p.92
3. Calude & Zamfirescu (1999)
4. Adamczewski & Bugeaud (2010) p.414

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::