A disjunctive sequence is an infinite sequence (over a finite alphabet of characters

Character (computing)

In computer and machine-based telecommunications terminology, a character is a unit of information that roughly corresponds to a grapheme, grapheme-like unit, or symbol, such as in an alphabet or syllabary in the written form of a natural language....

) in which every finite string appears as a substring

Substring

A subsequence, substring, prefix or suffix of a string is a subset of the symbols in a string, where the order of the elements is preserved...

. For instance, the binary Champernowne sequence

Champernowne constant

In mathematics, the Champernowne constant C10 is a transcendental real constant whose decimal expansion has important properties. It is named after mathematician D. G...

formed by concatenating all binary strings in shortlex order

Shortlex order

The shortlex order is an ordering for ordered sets of objects, where the sequences are primarily sorted by cardinality with the shortest sequences first, and sequences of the same length are sorted into lexicographical order....

, clearly contains all the binary strings and so is disjunctive. (The spaces above are not significant and are present solely to make clear the boundaries between strings).

Any normal sequence

Normal number

In mathematics, a normal number is a real number whose infinite sequence of digits in every base b is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b, also all possible b2 pairs of digits are equally likely with density b−2,...

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


obtained by splicing exponentially long strings of 0s into the shortlex order

Shortlex order

The shortlex order is an ordering for ordered sets of objects, where the sequences are primarily sorted by cardinality with the shortest sequences first, and sequences of the same length are sorted into lexicographical order....

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

Examples

The following result can be used to generate a variety of disjunctive sequences:

If a₁, a₂, a₃, ..., is a strictly increasing infinite sequence of positive integers such that lim

Limit of a sequence

The limit of a sequence is, intuitively, the unique number or point L such that the terms of the sequence become arbitrarily close to L for "large" values of n...

 _{n → ∞} (a_n+1 / a_n) = 1,

then for any positive integer m and any integer base

Radix

In mathematical numeral systems, the base or radix for the simplest case is the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.In any numeral...

 b ≥ 2, there is an a_n whose expression in base b starts with the expression of m in base b.

Two simple cases illustrate this result:

• a_n = n^k, where k is a fixed positive integer. (In this case, lim _{n → ∞} (a_n+1 / a_n) = lim _{n → ∞} ( (n+1)^k / n^k ) = lim _{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 n^th prime number
  Prime number
  A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
  
  . (In this case, lim _{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.