Gouldian sequence

The self-similar sawtooth shape of the Gouldian sequence.

The Gould's sequence ( English Gould’s sequence [ guːldz ˈsiːkwəns ]) is an integer sequence named after Henry W. Gould that counts the odd numbers in each line of Pascal's triangle . It consists exclusively of powers of two and begins with:

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 OEIS

For example, the sixth number in this sequence is 4 because there are four odd numbers in the sixth row of Pascal's triangle, the four marked numbers in the sequence 1 , 5 , 10, 10, 5 , 1 .

history

The episode is named after Henry W. Gould who studied it in the early 1960s. However, the fact that these numbers represent powers of two, where the exponent of the nth number is equal to the number of ones in the binary representation of , was already known to JWL Glaisher in 1899. ${\ displaystyle n}$

Proof that the numbers in Gould's sequence represent powers of two was presented as a task in the 1956 William Lowell Putnam Mathematical Competition .

Further interpretations

The nth value in the sequence, starting from n = 0), gives the highest power of two that divides the mean binomial coefficient and the numerator of (expressed as a fully abbreviated fraction). ${\ displaystyle {\ tbinom {2n} {n}}}$ ${\ displaystyle 2 ^ {n} / n!}$

Sierpinski's triangle , which is generated by rule 90 , or by marking the positions of odd numbers in Pascal's triangle . Gould's sequence counts the number of living cells in each row of this pattern.

Gould's sequence also gives the number of living cells in the nth generation of the cellular automaton of rule 90 , based on a single living cell. It has a characteristic exponentially growing sawtooth shape that can be used to identify physical processes that behave similarly to rule 90.

Related episodes

The binary logarithms (exponents of the powers of two) of the Gouldian sequence themselves form an integral 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 OEIS ,

in which the nth value gives the number of bits set in the binary representation of the number n, sometimes represented in mathematical notation as . The nth value in Gould's sequence is equivalent to this ${\ displaystyle \ #_ {1} (n)}$

{\ displaystyle 2 ^ {\ #_ {1} (n)}.}

If you take the sequence of the exponents modulo two, you get the Thue – Morse sequence .

The partial sums of the Gouldian sequence,

0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, 49, 57, 65, 81, 83, 87, 91, 99, 103, 111, ... sequence A006046 in OEIS

count all odd numbers in the first n rows of Pascal's triangle. These numbers grow proportionally , but with a constant of proportionality that oscillates periodically between 0.812556… and 1 as a function of . ${\ textstyle n ^ {\ log _ {2} 3} \ approx n ^ {1.585}}$ ${\ textstyle \ log n}$

Recursive construction and self-similarity

The first values of the Gouldian sequence can be constructed by recursively constructing the first values and concatenating twice the first values. For example, concatenating the first four values 1, 2, 2, 4 with their twofold 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 occurs at that position . ${\ textstyle 2 ^ {i}}$ ${\ textstyle 2 ^ {i-1}}$ ${\ textstyle 2 ^ {i-1}}$ ${\ textstyle 2 ^ {i}}$ ${\ textstyle 2 ^ {i} -1}$

The Gouldian sequence, the sequence of exponents of powers of two, and the Thue – Morse sequence are all self-similar : They have the property that the subsequence of values at even positions in the entire sequence is the same as the original sequence, a property that they also share share some other episodes such as the Stern-Brocot episode . In the Gouldian sequence, the values at odd places are twice as large as their respective predecessors, while in the exponent sequence the values at odd places are one greater than their predecessor.

Individual evidence

↑ ^a ^b ^c ^d ^e N. JA Sloane: Sloane's A001316. Gould's sequence. In: The On-Line Encyclopedia of Integer Sequences . OEIS Foundation, accessed February 25, 2017 .

↑ ^a ^b George Pólya, Robert Tarjan, Donald R. Woods: Notes on Introductory Combinatorics (= Progress in Computer Science and Applied Logic ). Birkhäuser, Boston 1983, ISBN 0-8176-4953-0 , p. 21 , doi : 10.1007 / 978-0-8176-4953-1 ( books.google.com [accessed February 25, 2017]).

^ Andrew Granville: Zaphod Beeblebrox's brain and the fifty-ninth row of Pascal's triangle . In: American Mathematical Monthly . tape 99 , no. 4 , 1992, pp. 318-331 , doi : 10.2307 / 2324898 .

↑ James Whitbread Lee Glaisher: On the residue of a binomial-theorem coefficient with respect to a prime modulus . In: The Quarterly Journal of Pure and Applied Mathematics . tape 30 , 1899, pp. 150–156 ( books.google.com [accessed February 25, 2017]).

^ Andrew M. Gleason, RE Greenwood, Leroy Milton Kelly: The William Lowell Putnam Mathematical Competition: Problems and Solutions: 1938–1964 . Ed .: Mathematical Association of America . 1980, ISBN 978-0-88385-462-4 , pp. 46 ( books.google.com [accessed February 25, 2017]).

↑ Stephen Wolfram: Geometry of binomial coefficients . In: American Mathematical Monthly . tape 91 , no. 9 , 1984, pp. 566-571 , doi : 10.2307 / 2323743 .

↑ Jens Christian Claussen, Jan Nagler, Heinz Georg Schuster: Sierpinski signal generates 1 ∕ f ^α spectra . In: Physical Review E . tape 70 , no. 3 . American Physical Society, September 2004, pp. 032101 , doi : 10.1103 / PhysRevE.70.032101 , arxiv : cond-mat / 0308277 , bibcode : 2004PhRvE..70c2101C (4 pages).

↑ Sam Northshield: Sums across Pascal's triangle mod 2 . In: Congressus Numerantium . tape 200 , 2010, p. 35–52 ( digitalcommons.plattsburgh.edu [PDF; 225 kB ; accessed on February 25, 2017]). digitalcommons.plattsburgh.edu ( Memento of the original from September 10, 2015 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2
^ Heiko Harborth: Number of odd binomial coefficients . In: Proceedings of the American Mathematical Society . tape 62 , no. 1 , 1976, p. 19-22 , doi : 10.2307 / 2041936 .
^ G. Larcher: On the number of odd binomial coefficients . In: Acta Mathematica Hungarica . tape 71 , no. 3 , 1996, p. 183-203 , doi : 10.1007 / BF00052108 .
↑ Stephen Wolfram: Geometry of binomial coefficients . In: American Mathematical Monthly . tape 91 , no. 9 , 1984, pp. 566-571 , doi : 10.2307 / 2323743 .
↑ Michael Gilleland: Some Self-Similar Integer Sequences. In: The On-Line Encyclopedia of Integer Sequences . OEIS Foundation, accessed February 25, 2017 .
↑ Manfred Schroeder: Fractal Horizons . Ed .: Clifford A. Pickover. St. Martin's Press, New York 1996, Fractals in Music, pp. 207-223 .

[:0-1] N. JA Sloane: Sloane's A001316. Gould's sequence. In: The On-Line Encyclopedia of Integer Sequences . OEIS Foundation, accessed February 25, 2017 .

[:1-2] George Pólya, Robert Tarjan, Donald R. Woods: Notes on Introductory Combinatorics (= Progress in Computer Science and Applied Logic ). Birkhäuser, Boston 1983, ISBN 0-8176-4953-0 , p. 21 , doi : 10.1007 / 978-0-8176-4953-1 ( books.google.com [accessed February 25, 2017]).

[3] Andrew Granville: Zaphod Beeblebrox's brain and the fifty-ninth row of Pascal's triangle . In: American Mathematical Monthly . tape 99 , no. 4 , 1992, pp. 318-331 , doi : 10.2307 / 2324898 .

[4] James Whitbread Lee Glaisher: On the residue of a binomial-theorem coefficient with respect to a prime modulus . In: The Quarterly Journal of Pure and Applied Mathematics . tape 30 , 1899, pp. 150–156 ( books.google.com [accessed February 25, 2017]).

[5] Andrew M. Gleason, RE Greenwood, Leroy Milton Kelly: The William Lowell Putnam Mathematical Competition: Problems and Solutions: 1938–1964 . Ed .: Mathematical Association of America . 1980, ISBN 978-0-88385-462-4 , pp. 46 ( books.google.com [accessed February 25, 2017]).

[6] Stephen Wolfram: Geometry of binomial coefficients . In: American Mathematical Monthly . tape 91 , no. 9 , 1984, pp. 566-571 , doi : 10.2307 / 2323743 .

[7] Jens Christian Claussen, Jan Nagler, Heinz Georg Schuster: Sierpinski signal generates 1 ∕ f ^α spectra . In: Physical Review E . tape 70 , no. 3 . American Physical Society, September 2004, pp. 032101 , doi : 10.1103 / PhysRevE.70.032101 , arxiv : cond-mat / 0308277 , bibcode : 2004PhRvE..70c2101C (4 pages).