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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006519 Highest power of 2 dividing n.
(Formerly M0162)
177
1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 64, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4, 1, 2 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Least positive k such that m^k + 1 divides m^n + 1 (with fixed base m). - Vladimir Baltic, Mar 25 2002

To construct the sequence: start with 1, concatenate 1, 1 and double last term gives 1, 2. Concatenate those 2 terms, 1, 2, 1, 2 and double last term 1, 2, 1, 2 -> 1, 2, 1, 4. Concatenate those 4 terms: 1, 2, 1, 4, 1, 2, 1, 4 and double last term -> 1, 2, 1, 4, 1, 2, 1, 8, etc. - Benoit Cloitre, Dec 17 2002

a(n) = GCD(seq(binomial(2*n, 2*m+1)/2, m = 0 .. n - 1)) (odd numbered entries of even numbered rows of Pascal's triangle A007318 divided by 2), where GCD denotes the greatest common divisor of a set of numbers. Due to the symmetry of the rows it suffices to consider m = 0 .. floor((n-1)/2). - Wolfdieter Lang, Jan 23 2004

Equals the continued fraction expansion of a constant x (cf. A100338) such that the continued fraction expansion of 2*x interleaves this sequence with 2's: contfrac(2*x) = [2; 1, 2, 2, 2, 1, 2, 4, 2, 1, 2, 2, 2, 1, 2, 8, 2, ...].

Simon Plouffe observes that this sequence and A003484 (Radon function) are very similar, the difference being all zeros except for every 16th term (see A101119 for nonzero differences). Dec 02 2004

This sequence arises when calculating the next odd number in a Collatz sequence: Next(x) = (3 * x + 1) / A006519, or simply (3 x + 1) / BitAnd(3x+1, -3x-1). - Jim Caprioli, Feb 04 2005

a(n) = n if and only if n = 2^k. This sequence can be obtained by taking a(2^n) = 2^n inplace of a(2^n) = n and using the same sequence building approach as in A001511. - Amarnath Murthy, Jul 08 2005

Also smallest m such that m + n - 1 = m XOR (n - 1); A086799(n)=a(n)+n-1. - Reinhard Zumkeller, Feb 02 2007

Number of 1's between successive 0's in A159689. - Philippe Deléham, Apr 22 2009

Least number k such that all coefficients of k*E(n, x), the n-th Euler polynomial, are integers (Cf. A144845). - Peter Luschny, Nov 13 2009

In the binary expansion of n, delete everything left of the rightmost 1 bit. - Ralf Stephan, Aug 22 2013

The equivalent sequence for partitions is A194446. - Omar E. Pol, Aug 22 2013

Also the 2-adic value of 1/n, n >= 1. See the Mahler reference, definition on p. 7. This is a non-archimedean valuation. See Mahler, p. 10. Sometimes called 2-adic absolute value of 1/n. - Wolfdieter Lang, Jun 28 2014

REFERENCES

K. Mahler, p-adic numbers and their functions, second ed., Cambridge University Press, 1981.

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

LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000

Tyler Ball, Tom Edgar, and Daniel Juda, Dominance Orders, Generalized Binomial Coefficients, and Kummer’s Theorem, Mathematics Magazine, Vol. 87, No. 2, April 2014, pp. 135-143.

Beeler, M., Gosper, R. W. and Schroeppel, R., Item 175 in Beeler, M., Gosper, R. W. and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb 29 1972

R. Brown and J. L. Merzel, The number of Ducci sequences with a given period, Fib. Quart., 45 (2007), 115-121.

D. Bruns, W. Mostowski, M. Ulbrich, Implementation-level verification of algorithms with KeY, International Journal on Software Tools for Technology Transfer, November 2013.

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences

Eric Weisstein's World of Mathematics, Even Part

Index entries for sequences related to binary expansion of n

FORMULA

a(n) = n AND -n (where "AND" is bitwise). - Marc LeBrun, Sep 25 2000

Also: a(n) = gcd(2^n, n). - Labos Elemer, Apr 22 2003

Multiplicative with a(p^e) = p^e if p = 2; 1 if p > 2. - David W. Wilson, Aug 01 2001

G.f.: sum(k >= 0, 2^k*x^2^k/(1-x^2^(k+1))). - Ralf Stephan, May 06 2003

Dirichlet g.f.: zeta(s)*(2^s-1)/(2^s-2). - Ralf Stephan, Jun 17 2007

a(n) = 2^floor(A002487(n - 1) / A002487(n)). - Reikku Kulon, Oct 05 2008

a(n) = 2^A007814(n). - R. J. Mathar, Oct 25 2010

a((2*k-1)*2^e) = 2^e, k>=1, e>=0. - Johannes W. Meijer, Jun 07 2011

a(n) = denominator of Euler(n-1, 1). - Arkadiusz Wesolowski, Jul 12 2012

a(n) = A011782(A001511(n)). - Omar E. Pol, Sep 13 2013

a(n) = (n XOR floor(n/2)) XOR (n-1 XOR floor((n-1)/2)) = n - (n AND n-1) (where "AND" is bitwise). - Gary Detlefs, Jun 12 2014

a(n) = ((n XOR n-1)+1)/2. - Gary Detlefs, Jul 02 2014

EXAMPLE

2^3 divides 24, but 2^4 does not divide 24, so a(24) = 8.

2^0 divides 25, but 2^1 does not divide 25, so a(25) = 1.

2^1 divides 26, but 2^2 does not divide 26, so a(26) = 2.

G.f. = x + 2*x^2 + x^3 + 4*x^4 + x^5 + 2*x^6 + x^7 + 8*x^8 + x^9 + ...

MAPLE

with(numtheory): for n from 1 to 200 do if n mod 2 = 1 then printf(`%d, `, 1) else printf(`%d, `, 2^ifactors(n)[2][1][2]) fi; od:

A006519 := proc(n) if type(n, 'odd') then 1 ; else for f in ifactors(n)[2] do if op(1, f) = 2 then return 2^op(2, f) ; end if; end do: end if; end proc: # R. J. Mathar, Oct 25 2010

A006519 := n -> 2^padic[ordp](n, 2): # Peter Luschny, Nov 26 2010

MATHEMATICA

f[n_] := Block[{k = 0}, While[Mod[n, 2^k] == 0, k++ ]; 2^(k - 1)]; Table[ f[n], {n, 102}] (* Robert G. Wilson v Nov 17 2004 *)

a[n_] := 2^IntegerExponent[n, 2]; Table[a[n], {n, 1, 102}](* Jean-François Alcover, Feb 10 2012 *)

PROG

(PARI) a(n)=2^valuation(n, 2);

(PARI) a(n)=1<<valuation(n, 2); /* Joerg Arndt, Jun 10 2011 */

(PARI) a(n)=bitand(n, -n); /* Joerg Arndt, Jun 10 2011 */

(Haskell)

import Data.Bits ((.&.))

a006519 n = n .&. (-n) :: Integer

-- Reinhard Zumkeller, Mar 11 2012, Dec 29 2011

CROSSREFS

Partial sums are in A006520, second partial sums in A022560.

Cf. A000079, A007814, A100338, A003484, A101119.

This is Guy Steele's sequence GS(5, 2) (see A135416).

Cf. A002487. - Reikku Kulon, Oct 05 2008

Sequence in context: A118827 A118830 A055975 * A087258 A076775 A218621

Adjacent sequences:  A006516 A006517 A006518 * A006520 A006521 A006522

KEYWORD

nonn,easy,nice,mult

AUTHOR

N. J. A. Sloane, Simon Plouffe, Jul 11 1991

EXTENSIONS

More terms from James A. Sellers, Jun 20 2000

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 October 23 03:24 EDT 2014. Contains 248411 sequences.