%I #73 Jan 11 2024 10:58:17
%S 1,1,2,2,2,2,4,4,2,2,4,4,4,4,8,8,2,2,4,4,4,4,8,8,4,4,8,8,8,8,16,16,2,
%T 2,4,4,4,4,8,8,4,4,8,8,8,8,16,16,4,4,8,8,8,8,16,16,8,8,16,16,16,16,32,
%U 32,2,2,4,4,4,4,8,8,4,4,8,8,8,8,16,16,4,4,8,8,8,8,16,16,8,8,16,16,16,16,32
%N a(n) = 2^wt(floor(n/2)) (i.e., 2^A000120(floor(n/2)), or A001316(floor(n/2))).
%C Number of conjugacy classes in the symmetric group S_n that have odd number of elements.
%C Also sequence A001316 doubled.
%C Number of even numbers whose binary expansion is a child of the binary expansion of n. - _Nadia Heninger_ and _N. J. A. Sloane_, Jun 06 2008
%C First differences of A151566. Sequence gives number of toothpicks added at the n-th generation of the leftist toothpick sequence A151566. - _N. J. A. Sloane_, Oct 20 2010
%C The Fi1 and Fi1 triangle sums, see A180662 for their definitions, of Sierpiński's triangle A047999 equal this sequence. - _Johannes W. Meijer_, Jun 05 2011
%C Also number of odd entries in n-th row of triangle of Stirling numbers of the first kind. - _Istvan Mezo_, Jul 21 2017
%D I. G. MacDonald: Symmetric functions and Hall polynomials Oxford: Clarendon Press, 1979. Page 21.
%H Indranil Ghosh, <a href="/A060632/b060632.txt">Table of n, a(n) for n = 0..65536</a> (terms 0..1000 from Harry J. Smith)
%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
%H Christina Talar Bekaroğlu, <a href="https://scholarworks.calstate.edu/concern/theses/bk128j63v">Analyzing Dynamics of Larger than Life: Impacts of Rule Parameters on the Evolution of a Bug's Geometry</a>, Master's thesis, Calif. State Univ. Northridge (2023). See p. 92.
%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%H <a href="/index/To#toothpick">Index entries for sequences related to toothpick sequences</a>
%F a(n) = sum{k=0..floor(n/2), C(n, 2k) mod 2} - _Paul Barry_, Jan 03 2005, Edited by _Harry J. Smith_, Sep 15 2009
%F a(n) = gcd(A056040(n), 2^n). - _Peter Luschny_, Jun 30 2011
%F G.f.: (1 + x) * Product_{k>=0} (1 + 2*x^(2^(k+1))). - _Ilya Gutkovskiy_, Jul 19 2019
%e a(3) = 2 because in S_3 there are two conjugacy classes with odd number of elements, the trivial conjugacy class and the conjugacy class of transpositions consisting of 3 elements: (12),(13),(23).
%e From _Omar E. Pol_, Oct 12 2011 (Start):
%e Written as a triangle:
%e 1,
%e 1,
%e 2,2,
%e 2,2,4,4,
%e 2,2,4,4,4,4,8,8,
%e 2,2,4,4,4,4,8,8,4,4,8,8,8,8,16,16,
%e 2,2,4,4,4,4,8,8,4,4,8,8,8,8,16,16,4,4,8,8,8,8,16,16,8,...
%e (End)
%p A060632 := proc(n) local k; add(binomial(n,2*k) mod 2, k=0..floor(n/2)); end: seq(A060632(n),n=0..94); # edited by _Johannes W. Meijer_, May 28 2011
%p A060632 := n -> 2^add(i, i = convert(iquo(n,2), base, 2)); # _Peter Luschny_, Jun 30 2011
%p A060632 := n -> igcd(2^n, n! / iquo(n,2)!^2); # _Peter Luschny_, Jun 30 2011
%t a[n_] := 2^DigitCount[Floor[n/2], 2, 1]; Table[a[n], {n, 0, 94}] (* _Jean-François Alcover_, Feb 25 2014 *)
%o (PARI) for (n=0, 1000, write("b060632.txt", n, " ", sum(k=0, floor(n/2), binomial(n, 2*k) % 2)) ) \\ _Harry J. Smith_, Sep 14 2009
%o (PARI) a(n)=2^hammingweight(n\2) \\ _Charles R Greathouse IV_, Feb 06 2017
%o (Magma) a000120:=func< n | &+Intseq(n, 2) >; [ 2^a000120(Floor(n/2)): n in [0..100] ]; // _Klaus Brockhaus_, Oct 15 2010
%o (Python)
%o def A060632(n):
%o return 2**bin(n/2)[2:].count("1") # _Indranil Ghosh_, Feb 06 2017
%Y Cf. A000120, A001316, A139251, A151566, A160407.
%K nonn
%O 0,3
%A Avi Peretz (njk(AT)netvision.net.il), Apr 15 2001
%E More terms from _James A. Sellers_, Apr 16 2001
%E Edited by _N. J. A. Sloane_, Jun 06 2008; Oct 11 2010
%E a(0) = 1 added by _N. J. A. Sloane_, Sep 14 2009
%E Formula corrected by _Harry J. Smith_, Sep 15 2009