Gould's sequence is an

integer sequence In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers. An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. Fo ...

named after Henry W. Gould that counts how many

odd number In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is a multiple of two, and odd if it is not.. For example, −4, 0, 82 are even because \begin -2 \cdot 2 &= -4 \\ 0 \cdot 2 &= 0 \\ 41 ...

s are in each row of

Pascal's triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, althoug ...

. It consists only of

powers of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent. In a context where only integers are considered, is restricted to non-negative ...

, and begins:. :1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, ... For instance, the sixth number in the sequence is 4, because there are four odd numbers in the sixth row of Pascal's triangle (the four bold numbers in the sequence 1, 5, 10, 10, 5, 1).

Additional interpretations

The th value in the sequence (starting from ) gives the highest power of 2 that divides the

central binomial coefficient In mathematics the ''n''th central binomial coefficient is the particular binomial coefficient : = \frac = \prod\limits_^\frac \textn \geq 0. They are called central since they show up exactly in the middle of the even-numbered rows in Pascal ...

\tbinom

, and it gives the numerator of

2^n/n!

(expressed as a fraction in lowest terms). PascalungeradeDreiecke

Gould's sequence also gives the number of live cells in the th generation of the

Rule 90 In the mathematical study of cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value. In each time step al ...

cellular automaton A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tess ...

starting from a single live cell.. It has a characteristic growing sawtooth shape that can be used to recognize physical processes that behave similarly to Rule 90..

Related sequences

The

binary logarithm In mathematics, the binary logarithm () is the power to which the number must be raised to obtain the value . That is, for any real number , :x=\log_2 n \quad\Longleftrightarrow\quad 2^x=n. For example, the binary logarithm of is , the ...

s (exponents in the powers of two) of Gould's sequence themselves form an integer sequence, :0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ... in which the th value gives the number of nonzero bits in the

binary representation A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one). The base-2 numeral system is a positional notation ...

of the number , sometimes written in mathematical notation as

\#_1(n)

. Equivalently, the th value in Gould's sequence is :

2^.

Taking the sequence of exponents modulo two gives the

Thue–Morse sequence In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thu ...

. The

partial sum In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, math ...

s of Gould's sequence, :0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, ... count all odd numbers in the first rows of Pascal's triangle. These numbers grow proportionally to

n^\approx n^

, but with a constant of proportionality that oscillates between 0.812556... and 1, periodically as a function of .

Recursive construction and self-similarity

The first values in Gould's sequence may be constructed by recursively constructing the first values, and then concatenating the doubles of the first values. For instance, concatenating the first four values 1, 2, 2, 4 with their doubles 2, 4, 4, 8 produces the first eight values. Because of this doubling construction, the first occurrence of each power of two in this sequence is at position . Gould's sequence, the sequence of its exponents, and the Thue–Morse sequence are all

self-similar __NOTOC__ In mathematics, a self-similar object is exactly or approximately similar to a part of itself (i.e., the whole has the same shape as one or more of the parts). Many objects in the real world, such as coastlines, are statistically s ...

: they have the property that the subsequence of values at even positions in the whole sequence equals the original sequence, a property they also share with some other sequences such as Stern's diatomic sequence. In Gould's sequence, the values at odd positions are double their predecessors, while in the sequence of exponents, the values at odd positions are one plus their predecessors.

History

The sequence is named after Henry W. Gould, who studied it in the early 1960s. However, the fact that these numbers are powers of two, with the exponent of the th number equal to the number of ones in the

of , was already known to J. W. L. Glaisher in 1899. Proving that the numbers in Gould's sequence are powers of two was given as a problem in the 1956

William Lowell Putnam Mathematical Competition The William Lowell Putnam Mathematical Competition, often abbreviated to Putnam Competition, is an annual mathematics competition for undergraduate college students enrolled at institutions of higher learning in the United States and Canada (regard ...

References

{{reflist, 30em Integer sequences Factorial and binomial topics Fractals Scaling symmetries