This site is supported by donations to The OEIS Foundation.

The submissions stack has been unacceptably high for several months now. Please voluntarily restrict your submissions and please help with the editing. (We don't want to have to impose further limits.)

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A007814 Exponent of highest power of 2 dividing n, a.k.a. the binary carry sequence, the ruler sequence, or the 2-adic valuation of n. 295
 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS This sequence is an exception to my usual rule that when every other term of a sequence is 0 then those 0's should be omitted. In this case we would get A001511. - N. J. A. Sloane To construct the sequence: start with 0,1, concatenate to get 0,1,0,1. Add + 1 to last term gives 0,1,0,2. Concatenate those 4 terms to get 0,1,0,2,0,1,0,2. Add + 1 to last term etc. - Benoit Cloitre, Mar 06 2003 The sequence is invariant under the following two transformations: increment every element by one (1, 2, 1, 3, 1, 2, 1, 4, ..), put a zero in front and between adjacent elements (0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ..). The intermediate result is A001511. - Ralf Hinze (ralf(AT)informatik.uni-bonn.de), Aug 26 2003 Fixed point of the morphism 0->01, 1->02, 2->03, 3->04, ..., n->0(n+1), ..., starting from a(1) = 0. - Philippe Deléham, Mar 15 2004 Fixed point of the morphism 0->010, 1->2, 2->3, ..., n->(n+1), .... - Joerg Arndt, Apr 29 2014 a(n) is also the number of times to repeat a step on an even number in the hailstone sequence referenced in the Collatz conjecture. - Alex T. Flood (whiteangelsgrace(AT)gmail.com), Sep 22 2006 Let F(n) be the n-th Fermat number (A000215). Then F(a(r-1)) divides F(n)+2^k for r = mod(k,2^n) and r != 1. - T. D. Noe, Jul 12 2007 The following relation holds: 2^A007814(n)*(2*A025480(n-1)+1) = A001477(n) = n. (See functions hd, tl and cons in [Paul Tarau 2009]). a(n) is the number of 0's at the end of n when n is written in base 2. a(n+1) is the number of 1's at the end of n when n is written in base 2. - M. F. Hasler, Aug 25 2012 Shows which bit to flip when creating the binary reflected Gray code (bits are numbered from the right, offset is 0).  That is, A003188(n) XOR A003188(n+1) == 2^A007814(n). - Russ Cox, Dec 04 2010 The sequence is squarefree. [Allouche and Shallit] a(n) is the number of zero coefficients in the n-th Stern polynomial, A125184. - T. D. Noe, Mar 01 2011 Lemma: For nr. Proof: We have n=b2^r and m=c2^r with br and n=2. - Joerg Arndt, Sep 06 2014 a(n) = number of 1's  in the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product(p_j-th prime, j=1...r) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(24) =3; indeed, the partition having Heinz number 24 = 2*2*2*3  is [1,1,1,2]. - Emeric Deutsch, Jun 04 2015 REFERENCES J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 27. K. Atanassov, On the 37th and the 38th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 2, 83-85. Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2. LINKS T. D. Noe, Table of n, a(n) for n = 1..10000 J. Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503, 2014 K. Atanassov, On Some of Smarandache's Problems Mathieu Guay-Paquet and Jeffrey Shallit, Avoiding Squares and Overlaps Over the Natural Numbers, (2009) Discrete Math., 309 (2009), 6245-6254. Mathieu Guay-Paquet and Jeffrey Shallit, Avoiding Squares and Overlaps Over the Natural Numbers, arXiv:0901.1397 [math.CO], 2009. M. Hassani, Equations and inequalities involving v_p(n!), J. Inequ. Pure Appl. Math. 6 (2005) vol. 2, #29 A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 61. Book's website C. Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., 274 (2004), 147-160. Simon Plouffe, On the values of the functions ... [zeta and Gamma] ..., arXiv preprint arXiv:1310.7195, 2013 A. Postnikov (MIT) and B. Sagan, What power of two divides a weighted Catalan number?, arXiv:math/0601339 [math.CO] Ville Salo, Decidability and Universality of Quasiminimal Subshifts, arXiv preprint arXiv:1411.6644, 2014 V. Shevelev, Several results on sequences which are similar to the positive integers, arXiv:0904.2101 [math.NT] F. Smarandache, Only Problems, Not Solutions!. R. Stephan, Some divide-and-conquer sequences ... R. Stephan, Table of generating functions Wikipedia, P-adic order. Paul Tarau. A Groupoid of Isomorphic Data Transformations. Calculemus 2009, 8th International Conference, MKM 2009, pp. 170-185,Springer, LNAI 5625. P. M. B. Vitanyi, An optimal simulation of counter machines, SIAM J. Comput, 14:1(1985), 1-33. Eric Weisstein's World of Mathematics, Binary Carry Sequence Eric Weisstein's World of Mathematics, Double-Free Set Eric Weisstein's World of Mathematics, Binary FORMULA a(n) = A001511(n) - 1. a(2*n) = A050603(2*n) = A001511(n). a(n) = A091090(n-1) + A036987(n-1) - 1. a(n) = if n is odd then 0 else 1 + a(n/2). - Reinhard Zumkeller, Aug 11 2001 Sum(k=1, n, a(k)) = n-A000120(n). - Benoit Cloitre, Oct 19 2002 G.f.: A(x) = Sum(k=1, infinity, x^(2^k)/(1-x^(2^k))). - Ralf Stephan, Apr 10 2002 G.f. A(x) satisfies A(x) = A(x^2) + x^2/(1-x^2). A(x) = B(x^2) = B(x) - x/(1-x), where B(x) is the g.f. for A001151. - Franklin T. Adams-Watters, Feb 09 2006 Totally additive with a(p) = 1 if p = 2, 0 otherwise. Dirichlet g.f.: zeta(s)/(2^s-1). - Ralf Stephan, Jun 17 2007 Define 0 <= k <= 2^n - 1; binary: k = b(0) + 2.b(1) + 4.b(2) + ... + 2^(n-1).b(n-1); where b(x) are 0 or 1 for 0 <= x <= n - 1; Define c(x) = 1 - b(x) for 0 <= x <= n - 1; Then: a(k) = c(0) + c(0).c(1) + c(0).c(1).c(2) + ... + c(0).c(1)...c(n-1); a(k+1) = b(0) + b(0).b(1) + b(0).b(1).b(2) + ... + b(0).b(1)...b(n-1). - Arie Werksma (werksma(AT)tiscali.nl), May 10 2008 a(n) = floor(A002487(n - 1) / A002487(n)). - Reikku Kulon, Oct 05 2008 Sum(k=1,n, (-1)^A000120(n-k)*a(k)) = (-1)^(A000120(n)-1)*(A000120(n)-A000035(n)). - Vladimir Shevelev, Mar 17 2009 a(A001147(n) + A057077(n-1)) = a(2*n). - Vladimir Shevelev, Mar 21 2009 For n>=1, a(A004760(n+1)) = a(n). - Vladimir Shevelev, Apr 15 2009 2^(a(n)) = A006519(n). - Philippe Deléham, Apr 22 2009 a(n) = A063787(n) - A000120(n). - Gary W. Adamson, Jun 04 2009 a(C(n,k)) = A000120(k)+A000120(n-k)-A000120(n). - Vladimir Shevelev, Jul 19 2009 a(n!) = n-A000120(n). - Vladimir Shevelev, Jul 20 2009 v_{2}(n) = sum_{r>=1} \frac{r}{2^{r+1}} sum_{k=0..2^{r+1}-1} e^{\frac{2(k*pi i(n+2^r)}{2^{r+1}}}. - A. Neves, Sep 28 2010, corrected Oct 04 2010 a(n)(mod 2) = A096268(n-1). - Robert G. Wilson v, Jan 18 2012 a(A005408(n)) = 1; a(A016825(n)) = 3; A017113(a(n)) = 5; A051062(a(n)) = 7; a(n) = (A037227(n)-1)/2. - Reinhard Zumkeller, Jun 30 2012 a((2*n-1)*2^p) = p, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 04 2013 a(n) = A067255(n,1). - Reinhard Zumkeller, Jun 11 2013 a(n) = log_2(n - (n AND n-1)). - Gary Detlefs, Jun 13 2014 a(n) = 1+A000120(n-1)-A000120(n), where A000120 is the Hamming weight function. - Stanislav Sykora, Jul 14 2014 EXAMPLE 2^3 divides 24, so a(24)=3. From Omar E. Pol, Jun 12 2009: (Start) Triangle begins: 0; 1,0; 2,0,1,0; 3,0,1,0,2,0,1,0; 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0; 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0; 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,... (End) MAPLE ord := proc(n) local i, j; if n=0 then return 0; fi; i:=0; j:=n; while j mod 2 <> 1 do i:=i+1; j:=j/2; od: i; end proc: seq(ord(n), n=1..111); A007814 := n -> padic[ordp](n, 2): seq(A007814(n), n=1..111); # Peter Luschny, Nov 26 2010 MATHEMATICA Table[IntegerExponent[n, 2], {n, 64}] (* Eric W. Weisstein *) p=2; Array[ If[ Mod[ #, p ]==0, Select[ FactorInteger[ # ], Function[ q, q[ [ 1 ] ]==p ], 1 ][ [ 1, 2 ] ], 0 ]&, 96 ] DigitCount[BitXor[x, x - 1], 2, 1] - 1; a different version based on the same concept: Floor[Log[2, BitXor[x, x - 1]]] (* Jaume Simon Gispert (jaume(AT)nuem.com), Aug 29 2004 *) Nest[Join[ #, ReplacePart[ #, Length[ # ] -> Last[ # ] + 1]] &, {0, 1}, 5] (* N. J. Gunther, May 23 2009 *) Nest[ Flatten[# /. a_Integer -> {0, a + 1}] &, {0}, 7] (* Robert G. Wilson v, Jan 17 2011 *) PROG (PARI) A007814(n)=valuation(n, 2); (Haskell) a007814 n = if m == 0 then 1 + a007814 n' else 0             where (n', m) = divMod n 2 -- Reinhard Zumkeller, Jul 05 2013, May 14 2011, Apr 08 2011 (Haskell) a007814 n | odd n = 0 | otherwise = 1 + a007814 (n div 2) --  Walt Rorie-Baety, Mar 22 2013 (Matlab) %Input: %  n: an integer %Output: %  m: max power of 2 such that 2^m divides n %  M: 1-by-K matrix where M(i) is the max power of 2 such that 2^M(i) divides n function [m, M] = Omega2(n)   M = NaN*zeros(1, n);   M(1)=0; M(2)=1;     for k=3:n       if M(k-2)~=0         M(k)=M(k-k/2)+1;       else         M(k)=0;       end     end     m=M(end); end % Redjan Shabani, Jul 17 2012 (R) sapply(1:100, function(x) sum(gmp::factorize(x)==2)) # Christian N. K. Anderson, Jun 20 2013 (MAGMA) [Valuation(n, 2): n in [1..120]]; // Bruno Berselli, Aug 05 2013 CROSSREFS First differences of A011371. Bisection of A050605 and |A088705|. Pairwise sums are A050603 and A136480. This is Guy Steele's sequence GS(1, 4) (see A135416). Cf. A053398(1,n). Column/row 1 of table A050602. Cf. A122840, A122841, A007949 (3-adic), A112765 (5-adic), A214411 (7-adic). Cf. A006519, A002487, A063787, A000079, A051064, A055457, A220466, A215366. Sequence in context: A191258 A254990 A191255 * A225345 A083280 A060689 Adjacent sequences:  A007811 A007812 A007813 * A007815 A007816 A007817 KEYWORD nonn,nice,easy,changed AUTHOR John Tromp, Dec 11 1996 EXTENSIONS Formula index adapted to the offset of A025480 by R. J. Mathar, Jul 20 2010 Edited by Ralf Stephan, Feb 08 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .