Gould's sequence

The {{mvar|n}}th value in the sequence (starting from {{math|1=n = 0}}) gives the highest power of 2 that divides the central binomial coefficient $\backslash tbinom\{2n\}\{n\}$, and it gives the numerator of $2^n/n!$ (expressed as a fraction in lowest terms).

File:PascalungeradeDreiecke.svg generated by Rule 90, or by marking the positions of odd numbers in Pascal's triangle. Gould's sequence counts the number of live cells in each row of this pattern.]]

Gould's sequence also gives the number of live cells in the {{mvar|n}}th generation of the Rule 90 cellular automaton starting from a single live cell.{{citation

| last = Wolfram | first = Stephen | authorlink = Stephen Wolfram

| doi = 10.2307/2323743

| issue = 9

| journal = American Mathematical Monthly

| mr = 764797

| pages = 566–571

| title = Geometry of binomial coefficients

| volume = 91

| year = 1984| jstor = 2323743 }}.

It has a characteristic growing sawtooth shape that can be used to recognize physical processes that behave similarly to Rule 90.{{citation|first1=Jens Christian|last1=Claussen|first2=Jan|last2=Nagler|first3=Heinz Georg|last3=Schuster|title=Sierpinski signal generates 1/f ^α spectra|journal=Physical Review E|volume=70|year=2004|issue=3|page=032101|doi=10.1103/PhysRevE.70.032101|pmid=15524560|arxiv=cond-mat/0308277|bibcode = 2004PhRvE..70c2101C |s2cid=39929111}}.

The binary logarithms (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, ... {{OEIS|A000120}}

in which the {{mvar|n}}th value gives the number of nonzero bits in the binary representation of the number {{mvar|n}}, sometimes written in mathematical notation as $\backslash \#\_1(n)$. Equivalently, the {{mvar|n}}th value in Gould's sequence is

:$2^\{\backslash \#\_1(n)\}.$

Taking the sequence of exponents modulo two gives the Thue–Morse sequence.{{citation

| last = Northshield

| first = Sam

| journal = Congressus Numerantium

| mr = 2597704

| pages = 35–52

| title = Sums across Pascal's triangle mod 2

| url = http://digitalcommons.plattsburgh.edu/cgi/viewcontent.cgi?article=1008&context=mathematics_facpubs

| volume = 200

| year = 2010

| access-date = 2016-09-10

| archive-url = https://web.archive.org/web/20150910124203/http://digitalcommons.plattsburgh.edu/cgi/viewcontent.cgi?article=1008&context=mathematics_facpubs

| archive-date = 2015-09-10

| url-status = dead

}}.

The partial sums of Gould's sequence,

:0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, ... {{OEIS|A006046}}

count all odd numbers in the first {{mvar|n}} rows of Pascal's triangle. These numbers grow proportionally to $n^\{\backslash log\_2\; 3\}\backslash approx\; n^\{1.585\}$,

but with a constant of proportionality that oscillates between 0.812556... and 1, periodically as a function of {{math|log n}}.{{citation

| last = Harborth | first = Heiko | authorlink = Heiko Harborth

| doi = 10.2307/2041936

| issue = 1

| journal = Proceedings of the American Mathematical Society

| mr = 0429714

| pages = 19–22

| title = Number of odd binomial coefficients

| volume = 62

| year = 1976| jstor = 2041936 | doi-access = free

}}.{{citation

| last = Larcher | first = G.

| doi = 10.1007/BF00052108 | doi-access =

| issue = 3

| journal = Acta Mathematica Hungarica

| mr = 1397551

| pages = 183–203

| title = On the number of odd binomial coefficients

| volume = 71

| year = 1996| s2cid = 121576268

}}.

The first {{math|2ⁱ}} values in Gould's sequence may be constructed by recursively constructing the first {{math|2^{i − 1}}} values, and then concatenating the doubles of the first {{math|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 {{math|2ⁱ}} in this sequence is at position {{math|2ⁱ − 1}}.

Gould's sequence, the sequence of its exponents, and the Thue–Morse sequence are all 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.{{citation|url=https://oeis.org/selfsimilar.html|title=Some Self-Similar Integer Sequences|first=Michael|last=Gilleland|publisher=OEIS|accessdate=2016-09-10}}.{{citation|title=Fractal Horizons|location=New York|publisher=St. Martin's Press|year=1996|editor-first=Clifford A.|editor-last=Pickover|editor-link=Clifford A. Pickover|first=Manfred|last=Schroeder|contribution=Fractals in Music|pages=207–223}}. As cited by Gilleland. 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.

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 {{mvar|n}}th number equal to the number of ones in the binary representation of {{mvar|n}}, was already known to J. W. L. Glaisher in 1899.{{citation

| last = Granville | first = Andrew | authorlink = Andrew Granville

| doi = 10.2307/2324898

| issue = 4

| journal = American Mathematical Monthly

| mr = 1157222

| pages = 318–331

| title = Zaphod Beeblebrox's brain and the fifty-ninth row of Pascal's triangle

| volume = 99

| year = 1992| jstor = 2324898 }}.{{citation

| last = Glaisher | first = J. W. L. | author-link = James Whitbread Lee Glaisher

| journal = The Quarterly Journal of Pure and Applied Mathematics

| pages = 150–156

| title = On the residue of a binomial-theorem coefficient with respect to a prime modulus

| url = https://books.google.com/books?id=j7sKAAAAIAAJ&pg=PA150

| volume = 30

| year = 1899}}. See in particular the final paragraph of p. 156.

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.{{citation

| editor1-last = Gleason | editor1-first = Andrew M. | editor1-link = Andrew M. Gleason

| editor2-last = Greenwood | editor2-first = R. E.

| editor3-last = Kelly | editor3-first = Leroy Milton | editor3-link = Leroy Milton Kelly

| isbn = 9780883854624

| page = 46

| publisher = Mathematical Association of America

| title = The William Lowell Putnam Mathematical Competition: Problems and Solutions: 1938–1964

| url = https://books.google.com/books?id=1zmhHT7lIc0C&pg=PA46

| year = 1980}}.

{{reflist|30em}}

Category:Integer sequences

Category:Factorial and binomial topics

Category:Fractals

Category:Scaling symmetries