A003159 Numbers whose binary representation ends in an even number of zeros. (Formerly M2306)

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, 39, 41, 43, 44, 45, 47, 48, 49, 51, 52, 53, 55, 57, 59, 60, 61, 63, 64, 65, 67, 68, 69, 71, 73, 75, 76, 77, 79, 80, 81, 83, 84, 85, 87, 89, 91, 92, 93, 95, 97, 99, 100, 101, 103, 105

Offset

1,2

Comments

Fraenkel (2010) called these the "vile" numbers.

Minimal with respect to property that parity of number of 1's in binary expansion alternates.

Minimal with respect to property that sequence is half its complement. [Corrected by Aviezri S. Fraenkel, Jan 29 2010]

If k appears then 2k does not.

Increasing sequence of positive integers k such that A035263(k)=1 (from paper by Allouche et al.). - Emeric Deutsch, Jan 15 2003

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

Indices of odd numbers in A007913, in A001511. - Philippe Deléham, Mar 27 2004

Partial sums of A026465. - Paul Barry, Dec 09 2004

A121701(2*a(n)) = A121701(a(n)); A096268(a(n)-1) = 0. - Reinhard Zumkeller, Aug 16 2006

A different permutation of the same terms may be found in A141290 and the accompanying array. - Gary W. Adamson, Jun 14 2008

a(n) = n-th clockwise Tower of Hanoi move; counterclockwise if not in the sequence. - Gary W. Adamson, Jun 14 2008

Indices of terms of Thue-Morse sequence A010060 which are different from the previous term. - Tanya Khovanova, Jan 06 2009

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

From Gary W. Adamson, Mar 21 2010: (Start)

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, ...).

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 + ....

(End)

The conjecture above was proved by Jean-Paul Allouche on Dec 21 2013. - Gary W. Adamson, Jan 22 2014

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

a=(1,3,4,5,6,8,9,10,11,12,14,...)=A184427;

b=(2,7,12,21,31,44,58,74,...)=A184428.

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

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Lars Blomberg, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)

J.-P. Allouche, Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence, arXiv preprint arXiv:1401.3727 [math.NT], 2014.

J.-P. Allouche, Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence, J. de Théorie des Nombres de Bordeaux, 27, no. 2 (2015), 375-388.

J.-P. Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe, and Bruce E. Sagan, A sequence related to that of Thue-Morse, Discrete Math., 139 (1995), 455-461.

J.-P. Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.

J.-P. Allouche, J. Shallit, and G. Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math. 292 (2005) 1-15.

George E. Andrews and David Newman, Binary Representations and Theta Functions, 2017.

L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Representations for a special sequence, Fib. Quart., 10 (1972), 499-518, 550.

R. Clerico, P. Fabbri, and F. Ortenzio, Pericolosamente vicino a Collatz, Rudi Mathematici, N. 226 (Nov 2017), p. 14 (in Italian).

M. Domaratzki, Trajectory-based codes, Acta Informatica, Volume 40, Numbers 6-7 / May, 2004.

E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.

A. Dubickas, On the distance from a rational power to the nearest integer, Journal of Number Theory, Volume 117, Issue 1, March 2006, pp. 222-239.

A. Dubickas, On a sequence related to that of Thue-Morse and its applications, Discrete Math. 307 (2007), no. 9-10, 1082--1093. MR2292537 (2008b:11086).

A. S. Fraenkel, New games related to old and new sequences, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper G6, 2004.

A. S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math. 312 (2012), no. 1, 42-46.

Aviezri S. Fraenkel, Home Page.

C. Kimberling, Problem E2850, Amer. Math. Monthly, 87 (1980), 671.

C. Kimberling, Complementary Equations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.4.

C. Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., 274 (2004), 147-160.

N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Slides of talk given at Rutgers University, Feb. 2012.

E. Sopena, i-Mark: A new subtraction division game, arXiv:1509.04199 [cs.DM], 2015.

D. Wakeham and D. R. Wood, On multiplicative Sidon sets, INTEGERS, 13 (2013), #A26.

Index entries for 2-automatic sequences.

Index entries for sequences related to binary expansion of n

Formula

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.

Limit_{n->oo} a(n)/n = 3/2. - Benoit Cloitre, Jun 13 2002

More precisely, a(n) = 3*n/2 + O(log n). - Charles R Greathouse IV, Sep 23 2012

a(n) = Sum_{k = 1..n} A026465(k). - Benoit Cloitre, May 31 2003

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

a(A003157(n)) is even. - Philippe Deléham, Feb 22 2004

Sequence consists of numbers of the form 4^i*(2*j + 1), i>=0, j>=0. - Jon Perry, Jun 06 2004

G.f.: (1/(1-x)) * Product_{k >= 1} (1 + x^A001045(k)). - Paul Barry, Dec 09 2004

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

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

a(n) = A121539(n) + 1. - Reinhard Zumkeller, Mar 01 2012

A003159 = { N | A007814(N) is even }. - M. F. Hasler, Oct 29 2013

Example

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

Maple

filter:= n -> type(padic:-ordp(n, 2), even):
select(filter, [$1..1000]); # Robert Israel, Jul 07 2014

Mathematica

f[n_Integer] := Block[{k = n, c = 0}, While[ EvenQ[k], c++; k /= 2]; c]; Select[ Range[105], EvenQ[ f[ # ]] & ]
Select[Range[150], EvenQ[IntegerExponent[#, 2]]&] (* Harvey P. Dale, Oct 19 2011 *)

Prog

(PARI) a(n)=if(n<2, n>0, n=a(n-1); until(valuation(n, 2)%2==0, n++); n)
(PARI) is(n)=valuation(n, 2)%2==0 \\ Charles R Greathouse IV, Sep 23 2012
(Haskell)
import Data.List (delete)
a003159 n = a003159_list !! (n-1)
a003159_list = f [1..] where f (x:xs) = x : f (delete  (2*x) xs)
-- Reinhard Zumkeller, Nov 04 2011
(Python)
from itertools import count, islice
def A003159_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:(n&-n).bit_length()&1, count(max(startvalue, 1)))
A003159_list = list(islice(A003159_gen(), 30)) # Chai Wah Wu, Jul 11 2022

Crossrefs

For the actual binary numbers see A280049.

Indices of even numbers in A007814.

Complement of A036554, also one-half of A036554.

Cf. A001285, A010060, A000041, A174065, A292118.

Sequence in context: A224985 A282808 A260401 * A361924 A187691 A141259

Adjacent sequences: A003156 A003157 A003158 * A003160 A003161 A003162

Keyword

nonn,nice,easy,eigen,base

Author

N. J. A. Sloane, Simon Plouffe

Extensions

Additional comments from Michael Somos

Edited by M. F. Hasler, Oct 29 2013

Incorrect formula removed by Peter Munn, Dec 04 2020

Status

approved