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

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 divisible by 2, and odd if it is not.. For example, −4, 0, and 82 are even numbers, while −3, 5, 23, and 69 are odd numbers. The ...

s are in each row of

Pascal's triangle In mathematics, Pascal's triangle is an infinite triangular array of the binomial coefficients which play a crucial role in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Bla ...

. 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 the fast-growing hierarchy, is exactly equal to f_1^n(1). In the Hardy hi ...

, 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). Gould's sequence is also a

fractal sequence In mathematics, a fractal sequence is one that contains itself as a proper subsequence. An example is ::1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, ... If the first occurrence of each n is deleted, the remaining sequence is i ...

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 \textn \geq 0. They are called central since they show up exactly in the middle of the even-numbered rows in Pascal's triangle. The first ...

\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 mathematics, mathematical study of cellular automaton, 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 ...

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, tessel ...

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 exponentiation, power to which the number must be exponentiation, raised to obtain the value . That is, for any real number , :x=\log_2 n \quad\Longleftrightarrow\quad 2^x=n. For example, th ...

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 for representing numbers that uses only two symbols for the natural numbers: typically "0" (zero) and "1" (one). A ''binary number'' may also ...

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 or Prouhet–Thue–Morse sequence is the binary sequence (an infinite sequence of 0s and 1s) that can be obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus ...

. The

partial sum In mathematics, a series is, roughly speaking, an addition of infinitely many terms, one after the other. The study of series is a major part of calculus and its generalization, mathematical analysis. Series are used in most areas of mathemati ...

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 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 self-similar ...

: 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 list of mathematics competitions, mathematics competition for undergraduate college students enrolled at institutions of higher learning in th ...

References

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