Gould's sequence

Gould's sequence or Dress's sequence is an integer sequence consisting only of powers of two, that counts the odd numbers in each row of Pascal's triangle. It begins:^[1]^[2]

1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, ... (sequence A001316 in the OEIS)

For instance, there is one odd number in the first row of Pascal's triangle, and two (both 1) in the second and third rows, but the fourth row (1, 3, 3, 1) has four odd numbers.

The $n$ th value in the sequence (starting from $n = 0$ ) gives the highest power of two that divides the central binomial coefficient ${\tbinom {2n}{n}}$ , the numerator of $2^{n}/n!$ (expressed as a fraction in lowest terms), and the number of live cells in the $n$ th generation of the Rule 90 cellular automaton starting from a single live cell.^[1]

The first $2 i$ values in the sequence may be constructed by recursively constructing the first $2 i - 1$ values, and then concatenating the doubles of the first $2 i - 1$ 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 $2 i$ in this sequence is at position $2 i - 1$ .^[1]

The sequence is named after Henry W. Gould and Andreas Dress.

The 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, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, ... (sequence A000120 in the OEIS)

in which the $n$ th value gives the number of nonzero bits in the binary representation of the number $n$ .^[1]^[2] Taking this sequence modulo two gives the Thue–Morse sequence.^[3] All three sequences are 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.^[4]^[5] 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.

References

^ ^a ^b ^c ^d Sloane, N. J. A. (ed.). "Sequence A001316 (Gould's sequence)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ ^a ^b Pólya, George; Tarjan, Robert E.; Woods, Donald R. (2009), Notes on Introductory Combinatorics, Progress in Computer Science and Applied Logic, vol. 4, Springer, p. 21, ISBN 9780817649531.
^ Northshield, Sam (2010), "Sums across Pascal's triangle mod 2", Congressus Numerantium, 200: 35–52, MR 2597704.
^ Gilleland, Michael, Some Self-Similar Integer Sequences, OEIS, retrieved 2016-09-10.
^ Schroeder, Manfred (1996), "Fractals in Music", in Pickover, Clifford A. (ed.), Fractal Horizons, New York: St. Martin's Press, pp. 207–223 {{citation}}: Unknown parameter |editorlink= ignored (|editor-link= suggested) (help). As cited by Gilleland.

[oeis-1] Sloane, N. J. A. (ed.). "Sequence A001316 (Gould's sequence)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[ptw-2] Pólya, George; Tarjan, Robert E.; Woods, Donald R. (2009), Notes on Introductory Combinatorics, Progress in Computer Science and Applied Logic, vol. 4, Springer, p. 21, ISBN 9780817649531.

[3] Northshield, Sam (2010), "Sums across Pascal's triangle mod 2", Congressus Numerantium, 200: 35–52, MR 2597704.

[4] Gilleland, Michael, Some Self-Similar Integer Sequences, OEIS, retrieved 2016-09-10.

[5] Schroeder, Manfred (1996), "Fractals in Music", in Pickover, Clifford A. (ed.), Fractal Horizons, New York: St. Martin's Press, pp. 207–223 {{citation}}: Unknown parameter |editorlink= ignored (|editor-link= suggested) (help). As cited by Gilleland.

[1]

[2]

[3]

[4]

[5]