

A003159


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


88



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 different permutation of the same terms may be found in A141290 and the accompanying array.  Gary W. Adamson, Jun 14 2008
a(n) = nth clockwise Tower of Hanoi move; counterclockwise if not in the sequence.  Gary W. Adamson, Jun 14 2008
Indices of terms of ThueMorse 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
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 nth 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/((1x)*(1x^3)*(1x^4)*(1x^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/((1x^2)*(1x^6)*(1x^8)*...) = 1 + x^2 + x^4 + 2*x^6 + 3*x^8 + 4*x^10 + ....
(End)
The conjecture above was proved by JeanPaul Allouche on Dec 21 2013.  Gary W. Adamson, Jan 22 2014
If the lower sWythoff sequence of s is s, then s=A003159. (See A184117 for the definition of lower and upper sWythoff sequences.) Starting with any nondecreasing sequence s of positive integers, A003159 is the limit when the lower sWythoff operation is iterated. For example, starting with s=(1,4,9,16,...)=(n^2), we obtain lower and upper sWythoff 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

J.P. Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe, and Bruce E. Sagan, A sequence related to that of ThueMorse, Discrete Math., 139 (1995), 455461.
J.P. Allouche and Jeffrey Shallit, The Ubiquitous ProuhetThueMorse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, SpringerVerlag, 1999, pp. 116.
C. Kimberling, Problem E2850, Amer. Math. Monthly, 87 (1980), 671.


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.
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
Sequence consists of numbers of the form 4^i*(2*j + 1), i>=0, j>=0.  Jon Perry, Jun 06 2004
a(1) = 1, a(2) = 3, and for n >= 2 we get a(n+1) = 4 + a(n) + a(n1)  a(a(n)n+1)  a(a(n1)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


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 base2 representation.
2=10 and 6=110 end in one (=odd number) of trailing zeros in their base2 representation, therefore are not terms of this sequence.  M. F. Hasler, Oct 29 2013


MAPLE

filter:= n > type(padic:ordp(n, 2), even):


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(n1); until(valuation(n, 2)%2==0, n++); n)
(Haskell)
import Data.List (delete)
a003159 n = a003159_list !! (n1)
a003159_list = f [1..] where f (x:xs) = x : f (delete (2*x) xs)
(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)))


CROSSREFS

For the actual binary numbers see A280049.
Indices of even numbers in A007814.


KEYWORD

nonn,nice,easy,eigen,base


AUTHOR



EXTENSIONS

Incorrect formula removed by Peter Munn, Dec 04 2020


STATUS

approved



