cp's OEIS Frontend

A003159 Numbers whose binary representation ends in an even number of zeros.

%I A003159 M2306 #222 Jun 05 2025 11:10:59
%S A003159 1,3,4,5,7,9,11,12,13,15,16,17,19,20,21,23,25,27,28,29,31,33,35,36,37,
%T A003159 39,41,43,44,45,47,48,49,51,52,53,55,57,59,60,61,63,64,65,67,68,69,71,
%U A003159 73,75,76,77,79,80,81,83,84,85,87,89,91,92,93,95,97,99,100,101,103,105
%N A003159 Numbers whose binary representation ends in an even number of zeros.
%C A003159 Fraenkel (2010) called these the "vile" numbers.
%C A003159 Minimal with respect to property that parity of number of 1's in binary expansion alternates.
%C A003159 Minimal with respect to property that sequence is half its complement. [Corrected by _Aviezri S. Fraenkel_, Jan 29 2010]
%C A003159 If k appears then 2k does not.
%C A003159 Increasing sequence of positive integers k such that A035263(k)=1 (from paper by Allouche et al.). - _Emeric Deutsch_, Jan 15 2003
%C A003159 a(n) is an odious number (see A000069) for n odd; a(n) is an evil number (see A001969) for n even. - _Philippe Deléham_, Mar 16 2004
%C A003159 Indices of odd numbers in A007913, in A001511. - _Philippe Deléham_, Mar 27 2004
%C A003159 Partial sums of A026465. - _Paul Barry_, Dec 09 2004
%C A003159 A121701(2*a(n)) = A121701(a(n)); A096268(a(n)-1) = 0. - _Reinhard Zumkeller_, Aug 16 2006
%C A003159 A different permutation of the same terms may be found in A141290 and the accompanying array. - _Gary W. Adamson_, Jun 14 2008
%C A003159 a(n) = n-th clockwise Tower of Hanoi move; counterclockwise if not in the sequence. - _Gary W. Adamson_, Jun 14 2008
%C A003159 Indices of terms of Thue-Morse sequence A010060 which are different from the previous term. - _Tanya Khovanova_, Jan 06 2009
%C A003159 The sequence has the following fractal property. Remove the odd numbers from the sequence, leaving 4,12,16,20,28,36,44,48,52,... Dividing these terms by 4 we get 1,3,4,5,7,9,11,12,..., which is the original sequence back again. - _Benoit Cloitre_, Apr 06 2010
%C A003159 From _Gary W. Adamson_, Mar 21 2010: (Start)
%C A003159 A conjectured identity relating to the partition sequence, A000041 as polcoeff p(x); A003159, and its characteristic function A035263: (1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, ...); and A036554 indicating n-th terms with zeros in A035263: (2, 6, 8, 10, 14, 18, 22, ...).
%C A003159 The conjecture states that p(x) = A(x) = A(x^2) when A(x) = polcoeff A174065 = the Euler transform of A035263 = 1/((1-x)*(1-x^3)*(1-x^4)*(1-x^5)*...) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 4*x^5 + ... and the aerated variant = the Euler transform of the complement of A035263: 1/((1-x^2)*(1-x^6)*(1-x^8)*...) = 1 + x^2 + x^4 + 2*x^6 + 3*x^8 + 4*x^10 + ....
%C A003159 (End)
%C A003159 The conjecture above was proved by Jean-Paul Allouche on Dec 21 2013. - _Gary W. Adamson_, Jan 22 2014
%C A003159 If the lower s-Wythoff sequence of s is s, then s=A003159. (See A184117 for the definition of lower and upper s-Wythoff sequences.)  Starting with any nondecreasing sequence s of positive integers, A003159 is the limit when the lower s-Wythoff operation is iterated.  For example, starting with s=(1,4,9,16,...)=(n^2), we obtain lower and upper s-Wythoff sequences
%C A003159   a=(1,3,4,5,6,8,9,10,11,12,14,...)=A184427;
%C A003159   b=(2,7,12,21,31,44,58,74,...)=A184428.
%C A003159   Then putting s=a and repeating the operation gives a'=(1,3,4,5,7,9,11,12,14,...), which has the same first eight terms as A003159. - _Clark Kimberling_, Jan 14 2011
%D A003159 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003159 Lars Blomberg, <a href="/A003159/b003159.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%H A003159 Jean-Paul Allouche, <a href="http://arxiv.org/abs/1401.3727">Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence</a>, arXiv preprint arXiv:1401.3727 [math.NT], 2014.
%H A003159 Jean-Paul Allouche, <a href="http://dx.doi.org/10.5802/jtnb.906">Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence</a>, J. de Théorie des Nombres de Bordeaux, 27, no. 2 (2015), 375-388.
%H A003159 Jean-Paul Allouche, <a href="https://webusers.imj-prg.fr/~jean-paul.allouche/121-12221.pdf">On the morphism 1 -> 121, 2 -> 12221</a>, CNRS France, 2024. See pp. 3, 6.
%H A003159 Jean-Paul Allouche, <a href="/A026465/a026465.pdf">On the morphism 1 -> 121, 2 -> 12221</a>, Preprint, 2024 [Local copy, with permission]
%H A003159 Jean-Paul Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe, and Bruce E. Sagan, <a href="http://dx.doi.org/10.1016/0012-365X(93)00147-W">A sequence related to that of Thue-Morse</a>, Discrete Math., 139 (1995), 455-461.
%H A003159 Jean-Paul Allouche and Jeffrey Shallit, <a href="https://cs.uwaterloo.ca/~shallit/Papers/ubiq15.pdf">The Ubiquitous Prouhet-Thue-Morse Sequence</a>, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
%H A003159 Jean-Paul Allouche, Jeffrey Shallit, and Guentcho Skordev, <a href="http://dx.doi.org/10.1016/j.disc.2004.12.004">Self-generating sets, integers with missing blocks and substitutions</a>, Discrete Math. 292 (2005) 1-15.
%H A003159 George E. Andrews and David Newman, <a href="https://georgeandrews1.github.io/pdf/322.pdf">Binary Representations and Theta Functions</a>, 2017.
%H A003159 L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/10-5/carlitz3-a.pdf">Representations for a special sequence</a>, Fib. Quart., 10 (1972), 499-518, 550.
%H A003159 R. Clerico, P. Fabbri, and F. Ortenzio, <a href="http://www.rudimathematici.com/archivio/226.pdf">Pericolosamente vicino a Collatz</a>, Rudi Mathematici, N. 226 (Nov 2017), p. 14 (in Italian).
%H A003159 Michael Domaratzki, <a href="http://dx.doi.org/10.1007/s00236-004-0140-4">Trajectory-based codes</a>, Acta Informatica, Volume 40, Numbers 6-7 / May, 2004.
%H A003159 Emeric Deutsch and Bruce E. Sagan, <a href="https://arxiv.org/abs/math/0407326">Congruences for Catalan and Motzkin numbers and related sequences</a>, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.
%H A003159 Artūras Dubickas, <a href="http://dx.doi.org/10.1016/j.jnt.2005.07.004">On the distance from a rational power to the nearest integer</a>, Journal of Number Theory, Volume 117, Issue 1, March 2006, pp. 222-239.
%H A003159 Artūras Dubickas, <a href="http://dx.doi.org/10.1016/j.disc.2006.08.001">On a sequence related to that of Thue-Morse and its applications</a>, Discrete Math. 307 (2007), no. 9-10, 1082--1093. MR2292537 (2008b:11086).
%H A003159 Aviezri S. Fraenkel, <a href="http://www.emis.de/journals/INTEGERS/papers/eg6/eg6.Abstract.html">New games related to old and new sequences</a>, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper G6, 2004.
%H A003159 Aviezri S. Fraenkel, <a href="http://dx.doi.org/10.1016/j.disc.2011.03.032">The vile, dopey, evil and odious game players</a>, Discrete Math. 312 (2012), no. 1, 42-46.
%H A003159 Aviezri S. Fraenkel, <a href="http://www.wisdom.weizmann.ac.il/~fraenkel/">Home Page</a>.
%H A003159 Russell Jay Hendel, <a href="https://arxiv.org/abs/2505.20547">A Family of Sequences Generalizing the Thue Morse and Rudin Shapiro Sequences</a>, arXiv:2505.20547 [cs.FL], 2025. See p. 3.
%H A003159 Clark Kimberling, <a href="http://www.jstor.org/stable/2320962">Problem E2850</a>, Amer. Math. Monthly, 87 (1980), 671.
%H A003159 Clark Kimberling, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Kimberling/kimberling26.html">Complementary Equations</a>, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.4.
%H A003159 Clark Kimberling, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00085-2">Affinely recursive sets and orderings of languages</a>, Discrete Math., 274 (2004), 147-160.
%H A003159 N. J. A. Sloane, <a href="/A003159/a003159.pdf">The On-Line Encyclopedia of Integer Sequences</a>, Slides of talk given at Rutgers University, Feb. 2012.
%H A003159 Jan Snellman, <a href="https://arxiv.org/abs/2504.02795">Greedy Regular Convolutions</a>, arXiv:2504.02795 [math.NT], 2025.
%H A003159 Eric Sopena, <a href="http://arxiv.org/abs/1509.04199">i-Mark: A new subtraction division game</a>, arXiv:1509.04199 [cs.DM], 2015.
%H A003159 David Wakeham and David R. Wood, <a href="http://www.emis.de/journals/INTEGERS/papers/n26/n26.Abstract.html">On multiplicative Sidon sets</a>, INTEGERS, 13 (2013), #A26.
%H A003159 <a href="/index/Ar#2-automatic">Index entries for 2-automatic sequences</a>.
%H A003159 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A003159 a(0) = 1; for n >= 0, a(n+1) = a(n) + 1 if (a(n) + 1)/2 is not already in the sequence, = a(n) + 2 otherwise.
%F A003159 Limit_{n->oo} a(n)/n = 3/2. - _Benoit Cloitre_, Jun 13 2002
%F A003159 More precisely, a(n) = 3*n/2 + O(log n). - _Charles R Greathouse IV_, Sep 23 2012
%F A003159 a(n) = Sum_{k = 1..n} A026465(k). - _Benoit Cloitre_, May 31 2003
%F A003159 a(n+1) = (if a(n) mod 4 = 3 then A007814(a(n) + 1) mod 2 else a(n) mod 2) + a(n) + 1; a(1) = 1. - _Reinhard Zumkeller_, Aug 03 2003
%F A003159 a(A003157(n)) is even. - _Philippe Deléham_, Feb 22 2004
%F A003159 Sequence consists of numbers of the form 4^i*(2*j + 1), i>=0, j>=0. - _Jon Perry_, Jun 06 2004
%F A003159 G.f.: (1/(1-x)) * Product_{k >= 1} (1 + x^A001045(k)). - _Paul Barry_, Dec 09 2004
%F A003159 a(1) = 1, a(2) = 3, and for n >= 2 we get a(n+1) = 4 + a(n) + a(n-1) - a(a(n)-n+1) - a(a(n-1)-n+2). - _Benoit Cloitre_, Apr 08 2010
%F A003159 If A(x) is the counting function for a(n) <= x, then A(2^n) = (2^(n+1) + (-1)^n)/3. - _Vladimir Shevelev_, Apr 15 2010
%F A003159 a(n) = A121539(n) + 1. - _Reinhard Zumkeller_, Mar 01 2012
%F A003159 A003159 = { N | A007814(N) is even }. - _M. F. Hasler_, Oct 29 2013
%e A003159 1=1, 3=11, 5=101 and 7=111 have no (0 = even) trailing zeros, 4=100 has 2 (= even) trailing zeros in the base-2 representation.
%e A003159 2=10 and 6=110 end in one (=odd number) of trailing zeros in their base-2 representation, therefore are not terms of this sequence. - _M. F. Hasler_, Oct 29 2013
%p A003159 filter:= n -> type(padic:-ordp(n,2),even):
%p A003159 select(filter,[$1..1000]); # _Robert Israel_, Jul 07 2014
%t A003159 f[n_Integer] := Block[{k = n, c = 0}, While[ EvenQ[k], c++; k /= 2]; c]; Select[ Range[105], EvenQ[ f[ # ]] & ]
%t A003159 Select[Range[150],EvenQ[IntegerExponent[#,2]]&] (* _Harvey P. Dale_, Oct 19 2011 *)
%o A003159 (PARI) a(n)=if(n<2,n>0,n=a(n-1); until(valuation(n,2)%2==0,n++); n)
%o A003159 (PARI) is(n)=valuation(n,2)%2==0 \\ _Charles R Greathouse IV_, Sep 23 2012
%o A003159 (Haskell)
%o A003159 import Data.List (delete)
%o A003159 a003159 n = a003159_list !! (n-1)
%o A003159 a003159_list = f [1..] where f (x:xs) = x : f (delete  (2*x) xs)
%o A003159 -- _Reinhard Zumkeller_, Nov 04 2011
%o A003159 (Python)
%o A003159 from itertools import count, islice
%o A003159 def A003159_gen(startvalue=1): # generator of terms >= startvalue
%o A003159     return filter(lambda n:(n&-n).bit_length()&1,count(max(startvalue,1)))
%o A003159 A003159_list = list(islice(A003159_gen(),30)) # _Chai Wah Wu_, Jul 11 2022
%o A003159 (Python)
%o A003159 def A003159(n):
%o A003159     def f(x):
%o A003159         c, s = n+x, bin(x)[2:]
%o A003159         l = len(s)
%o A003159         for i in range(l&1^1,l,2):
%o A003159             c -= int(s[i])+int('0'+s[:i],2)
%o A003159         return c
%o A003159     m, k = n, f(n)
%o A003159     while m != k: m, k = k, f(k)
%o A003159     return m # _Chai Wah Wu_, Jan 29 2025
%Y A003159 For the actual binary numbers see A280049.
%Y A003159 Indices of even numbers in A007814.
%Y A003159 Complement of A036554, also one-half of A036554.
%Y A003159 Cf. A001285, A010060, A000041, A174065, A292118.
%K A003159 nonn,nice,easy,eigen,base
%O A003159 1,2
%A A003159 _N. J. A. Sloane_, _Simon Plouffe_
%E A003159 Additional comments from _Michael Somos_
%E A003159 Edited by _M. F. Hasler_, Oct 29 2013
%E A003159 Incorrect formula removed by _Peter Munn_, Dec 04 2020