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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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

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

REFERENCES

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

K. Atanassov, On the 37-th and the 38-th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 2, 83-85.

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. arXiv:0901.1397 [math.CO]

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]

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

Index entries for sequences related to binary expansion of n

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]

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.

Sequence in context: A162590 A191258 A191255 * A225345 A083280 A060689

Adjacent sequences:  A007811 A007812 A007813 * A007815 A007816 A007817

KEYWORD

nonn,nice,easy

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 .

Last modified August 22 05:47 EDT 2014. Contains 245921 sequences.