login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

%I

%S 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,

%T 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,

%U 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

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

%C 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_

%C 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

%C 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

%C 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

%C Fixed point of the morphism 0->010, 1->2, 2->3, ..., n->(n+1), .... - _Joerg Arndt_, Apr 29 2014

%C 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

%C 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

%C 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].)

%C a(n) is the number of 0's at the end of n when n is written in base 2.

%C 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

%C 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

%C The sequence is squarefree. [Allouche and Shallit]

%C a(n) is the number of zero coefficients in the n-th Stern polynomial, A125184. - _T. D. Noe_, Mar 01 2011

%C Lemma: For n < m with r = a(n) = a(m) there exists n < k < m with a(k) > r. Proof: We have n=b2^r and m=c2^r with b < c both odd; choose an even i between them; now a(i2^r) > r and n < i2^r < m. QED. Corollary: Every finite run of consecutive integers has a unique maximum 2-adic valuation. - _Jason Kimberley_, Sep 09 2011

%C A053398(n,k) = a(A003986(n-1,k-1)+1); a(n) = A053398(n,1) = A053398(n,n) = A053398(2*n-1,n) = min(A053398(n,k): k=1..n). - _Reinhard Zumkeller_, Aug 04 2014

%C a(n-2) is the 2-adic valuation of A000166(n) for n >= 2. - _Joerg Arndt_, Sep 06 2014

%C 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_{j=1..r} p_j-th prime (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

%C a(n+1) is the difference between the two largest parts in the integer partition having viabin number n (0 is assumed to be a part). Example: a(20) = 2. Indeed, we have 19 = 10011_2, leading to the Ferrers board of the partition [3,1,1]. For the definition of viabin number see the comment in A290253. - _Emeric Deutsch_, Aug 24 2017

%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 27.

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

%D Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

%H T. D. Noe, <a href="/A007814/b007814.txt">Table of n, a(n) for n = 1..10000</a>

%H J. Arndt, <a href="http://arxiv.org/abs/1405.6503">Subset-lex: did we miss an order?</a>, arXiv:1405.6503 [math.CO], 2014.

%H K. Atanassov, <a href="http://www.gallup.unm.edu/~smarandache/Atanassov-SomeProblems.pdf">On Some of Smarandache's Problems</a>

%H Mathieu Guay-Paquet and Jeffrey Shallit, <a href="http://dx.doi.org/10.1016/j.disc.2009.06.004">Avoiding Squares and Overlaps Over the Natural Numbers</a>, (2009) Discrete Math., 309 (2009), 6245-6254.

%H Mathieu Guay-Paquet and Jeffrey Shallit, <a href="http://arxiv.org/abs/0901.1397">Avoiding Squares and Overlaps Over the Natural Numbers</a>, arXiv:0901.1397 [math.CO], 2009.

%H M. Hassani, <a href="http://jipam.vu.edu.au/article.php?sid=498">Equations and inequalities involving v_p(n!)</a>, J. Inequ. Pure Appl. Math. 6 (2005) vol. 2, #29

%H A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 61. <a href="http://tohbook.info">Book's website</a>

%H C. Kimberling, <a href="http://scholar.google.com/scholar?cluster=12438506788403082857">Affinely recursive sets and orderings of languages</a>, Discrete Math., 274 (2004), 147-160.

%H Nicolas Mallet, <a href="http://arxiv.org/abs/1507.05039">Trial for a proof of the Syracuse conjecture</a>, arXiv preprint arXiv:1507.05039 [math.GM], 2015.

%H S. Northshield, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Northshield/north4.html">An Analogue of Stern's Sequence for Z[sqrt(2)]</a>, Journal of Integer Sequences, 18 (2015), #15.11.6.

%H Simon Plouffe, <a href="http://arxiv.org/abs/1310.7195">On the values of the functions ... [zeta and Gamma] ...</a>, arXiv preprint arXiv:1310.7195 [math.NT], 2013.

%H A. Postnikov (MIT) and B. Sagan, <a href="http://arxiv.org/abs/math/0601339">What power of two divides a weighted Catalan number?</a>, arXiv:math/0601339 [math.CO], 2006.

%H Ville Salo, <a href="http://arxiv.org/abs/1411.6644">Decidability and Universality of Quasiminimal Subshifts</a>, arXiv preprint arXiv:1411.6644 [math.DS], 2014.

%H V. Shevelev, <a href="http://arXiv.org/abs/0904.2101">Several results on sequences which are similar to the positive integers</a>, arXiv:0904.2101 [math.NT], 2014.

%H F. Smarandache, <a href="http://www.gallup.unm.edu/~smarandache/OPNS.pdf">Only Problems, Not Solutions!</a>.

%H R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/P-adic_order">P-adic order</a>.

%H Paul Tarau. <a href="http://scholar.google.com/scholar?cluster=284705751770513453">A Groupoid of Isomorphic Data Transformations</a>. Calculemus 2009, 8th International Conference, MKM 2009, pp. 170-185,Springer, LNAI 5625.

%H P. M. B. Vitanyi, <a href="http://dx.doi.org/10.1137/0214001">An optimal simulation of counter machines</a>, SIAM J. Comput, 14:1(1985), 1-33.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Binary.html">Binary</a>, <a href="http://mathworld.wolfram.com/BinaryCarrySequence.html">Binary Carry Sequence</a>, and <a href="http://mathworld.wolfram.com/Double-FreeSet.html">Double-Free Set</a>.

%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(n) = A001511(n) - 1.

%F a(2*n) = A050603(2*n) = A001511(n).

%F a(n) = A091090(n-1) + A036987(n-1) - 1.

%F a(n) = if n is odd then 0 else 1 + a(n/2). - _Reinhard Zumkeller_, Aug 11 2001

%F Sum_{k=1..n} a(k) = n - A000120(n). - _Benoit Cloitre_, Oct 19 2002

%F G.f.: A(x) = Sum_{k>=1} x^(2^k)/(1-x^(2^k)). - _Ralf Stephan_, Apr 10 2002

%F 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

%F Totally additive with a(p) = 1 if p = 2, 0 otherwise.

%F Dirichlet g.f.: zeta(s)/(2^s-1). - _Ralf Stephan_, Jun 17 2007

%F 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

%F a(n) = floor(A002487(n - 1) / A002487(n)). - _Reikku Kulon_, Oct 05 2008

%F Sum_{k=1..n} (-1)^A000120(n-k)*a(k) = (-1)^(A000120(n)-1)*(A000120(n) - A000035(n)). - _Vladimir Shevelev_, Mar 17 2009

%F a(A001147(n) + A057077(n-1)) = a(2*n). - _Vladimir Shevelev_, Mar 21 2009

%F For n>=1, a(A004760(n+1)) = a(n). - _Vladimir Shevelev_, Apr 15 2009

%F 2^(a(n)) = A006519(n). - _Philippe Deléham_, Apr 22 2009

%F a(n) = A063787(n) - A000120(n). - _Gary W. Adamson_, Jun 04 2009

%F a(C(n,k)) = A000120(k) + A000120(n-k) - A000120(n). - _Vladimir Shevelev_, Jul 19 2009

%F a(n!) = n - A000120(n). - _Vladimir Shevelev_, Jul 20 2009

%F v_{2}(n) = Sum_{r>=1} (r / 2^(r+1)) Sum_{k=0..2^(r+1)-1} e^(2(k*Pi*i(n+2^r))/(2^(r+1))). - _A. Neves_, Sep 28 2010, corrected Oct 04 2010

%F a(n) mod 2 = A096268(n-1). - _Robert G. Wilson v_, Jan 18 2012

%F 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

%F a((2*n-1)*2^p) = p, p >= 0 and n >= 1. - _Johannes W. Meijer_, Feb 04 2013

%F a(n) = A067255(n,1). - _Reinhard Zumkeller_, Jun 11 2013

%F a(n) = log_2(n - (n AND n-1)). - _Gary Detlefs_, Jun 13 2014

%F a(n) = 1 + A000120(n-1) - A000120(n), where A000120 is the Hamming weight function. - _Stanislav Sykora_, Jul 14 2014

%F a((2*x-1)*2^n) = a((2*y-1)*2^n) for positive n, x and y. - _Juri-Stepan Gerasimov_, Aug 04 2016

%F a(n) = A285406(n) - A281264(n). - _Ralf Steiner_, Apr 18 2017

%F a(n) = A000005(n)/(A000005(2*n) - A000005(n)) - 1. - conjectured by _Velin Yanev_, Jun 30 2017, proved by _Nicholas Stearns_, Sep 11 2017

%e 2^3 divides 24, so a(24)=3.

%e From _Omar E. Pol_, Jun 12 2009: (Start)

%e Triangle begins:

%e 0;

%e 1,0;

%e 2,0,1,0;

%e 3,0,1,0,2,0,1,0;

%e 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;

%e 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;

%e 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,...

%e (End)

%p 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);

%p A007814 := n -> padic[ordp](n,2): seq(A007814(n), n=1..111); # _Peter Luschny_, Nov 26 2010

%t Table[IntegerExponent[n, 2], {n, 64}] (* _Eric W. Weisstein_ *)

%t p=2; Array[ If[ Mod[ #, p ]==0, Select[ FactorInteger[ # ], Function[ q, q[ [ 1 ] ]==p ], 1 ][ [ 1, 2 ] ], 0 ]&, 96 ]

%t 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 *)

%t Nest[Join[ #, ReplacePart[ #, Length[ # ] -> Last[ # ] + 1]] &, {0, 1}, 5] (* N. J. Gunther, May 23 2009 *)

%t Nest[ Flatten[# /. a_Integer -> {0, a + 1}] &, {0}, 7] (* _Robert G. Wilson v_, Jan 17 2011 *)

%o (PARI) A007814(n)=valuation(n,2);

%o (Haskell)

%o a007814 n = if m == 0 then 1 + a007814 n' else 0

%o where (n', m) = divMod n 2

%o -- _Reinhard Zumkeller_, Jul 05 2013, May 14 2011, Apr 08 2011

%o (Haskell)

%o a007814 n | odd n = 0 | otherwise = 1 + a007814 (n `div` 2)

%o -- _Walt Rorie-Baety_, Mar 22 2013

%o (MATLAB)

%o % Input:

%o % n: an integer

%o % Output:

%o % m: max power of 2 such that 2^m divides n

%o % M: 1-by-K matrix where M(i) is the max power of 2 such that 2^M(i) divides n

%o function [m,M] = Omega2(n)

%o M = NaN*zeros(1,n);

%o M(1)=0; M(2)=1;

%o for k=3:n

%o if M(k-2)~=0

%o M(k)=M(k-k/2)+1;

%o else

%o M(k)=0;

%o end

%o end

%o m=M(end);

%o end

%o % _Redjan Shabani_, Jul 17 2012

%o (R) sapply(1:100,function(x) sum(gmp::factorize(x)==2)) # _Christian N. K. Anderson_, Jun 20 2013

%o (MAGMA) [Valuation(n, 2): n in [1..120]]; // _Bruno Berselli_, Aug 05 2013

%o (Python)

%o import math

%o def a(n): return int(math.log(n - (n & n - 1), 2)) # _Indranil Ghosh_, Apr 18 2017

%o (Scheme) (define (A007814 n) (let loop ((n n) (e 0)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; _Antti Karttunen_, Oct 06 2017

%Y First differences of A011371. Bisection of A050605 and |A088705|. Pairwise sums are A050603 and A136480. Difference of A285406 and A281264.

%Y This is Guy Steele's sequence GS(1, 4) (see A135416). Cf. A053398(1,n). Column/row 1 of table A050602.

%Y Cf. A007949 (3-adic), A112765 (5-adic), A214411 (7-adic).

%Y Cf. A000079, A002487, A006519, A051064, A055457, A063787, A122840, A122841, A215366, A220466.

%K nonn,nice,easy

%O 1,4

%A _John Tromp_, Dec 11 1996

%E Formula index adapted to the offset of A025480 by _R. J. Mathar_, Jul 20 2010

%E Edited by _Ralf Stephan_, Feb 08 2014

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 21 06:38 EST 2018. Contains 299390 sequences. (Running on oeis4.)