%I M0162 #262 Jan 28 2024 09:04:24

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

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

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

%N Highest power of 2 dividing n.

%C Least positive k such that m^k + 1 divides m^n + 1 (with fixed base m). - _Vladimir Baltic_, Mar 25 2002

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

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

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

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

%C 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(3*x + 1, -3*x - 1). - Jim Caprioli, Feb 04 2005

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

%C Also smallest m such that m + n - 1 = m XOR (n - 1); A086799(n) = a(n) + n - 1. - _Reinhard Zumkeller_, Feb 02 2007

%C Number of 1's between successive 0's in A159689. - _Philippe Deléham_, Apr 22 2009

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

%C In the binary expansion of n, delete everything left of the rightmost 1 bit. - _Ralf Stephan_, Aug 22 2013

%C The equivalent sequence for partitions is A194446. - _Omar E. Pol_, Aug 22 2013

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

%C First 2^(k-1) - 1 terms are also the heights of the successive rectangles and squares of width 2 that are adjacent to any of the four sides of the toothpick structure of A139250 after 2^k stages, with k >= 2. For example: if k = 5 the heights after 32 stages are [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1] respectively, the same as the first 15 terms of this sequence. - _Omar E. Pol_, Dec 29 2020

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

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

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

%H Dzmitry Badziahin and Jeffrey Shallit, <a href="http://arxiv.org/abs/1505.00667">An Unusual Continued Fraction</a>, arXiv:1505.00667 [math.NT], 2015.

%H Dzmitry Badziahin and Jeffrey Shallit, <a href="https://doi.org/10.1090/proc/12848">An unusual continued fraction</a>, Proc. Amer. Math. Soc. 144 (2016), 1887-1896.

%H Tyler Ball, Tom Edgar, and Daniel Juda, <a href="http://dx.doi.org/10.4169/math.mag.87.2.135">Dominance Orders, Generalized Binomial Coefficients, and Kummer's Theorem</a>, Mathematics Magazine, Vol. 87, No. 2, April 2014, pp. 135-143.

%H M. Beeler, R. W. Gosper and R. Schroeppel, <a href="http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item175">Item 175</a>, in Beeler, M., Gosper, R. W. and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb 29 1972.

%H Ron Brown and Jonathan L. Merzel, <a href="http://www.fq.math.ca/Papers1/45-2/brown.pdf">The number of Ducci sequences with a given period</a>, Fib. Quart., 45 (2007), 115-121.

%H Daniel Bruns, Wojciech Mostowski, and Mattias Ulbrich, <a href="http://dx.doi.org/10.1007/s10009-013-0293-y">Implementation-level verification of algorithms with KeY</a>, International Journal on Software Tools for Technology Transfer, November 2013.

%H Victor Meally, <a href="/A006516/a006516.pdf">Letter to N. J. A. Sloane, May 1975</a>.

%H Laurent Orseau, Levi H. S. Lelis, and Tor Lattimore, <a href="https://arxiv.org/abs/1906.03242">Zooming Cautiously: Linear-Memory Heuristic Search With Node Expansion Guarantees</a>, arXiv:1906.03242 [cs.AI], 2019.

%H Laurent Orseau, Levi H. S. Lelis, Tor Lattimore, and Théophane Weber, <a href="https://arxiv.org/abs/1811.10928">Single-Agent Policy Tree Search With Guarantees</a>, arXiv:1811.10928 [cs.AI], 2018, also in Advances in Neural Information Processing Systems, 32nd Conference on Neural Information Processing Systems (NIPS 2018), Montréal, Canada.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple ordinary generating functions</a>.

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

%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EvenPart.html">Even Part</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Converse_nonimplication">Converse nonimplication</a>.

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

%F a(n) = n AND -n (where "AND" is bitwise, and negative numbers are represented in two's complement in a suitable bit width). - _Marc LeBrun_, Sep 25 2000, clarified by _Alonso del Arte_, Mar 16 2020

%F Also: a(n) = gcd(2^n, n). - _Labos Elemer_, Apr 22 2003

%F Multiplicative with a(p^e) = p^e if p = 2; 1 if p > 2. - _David W. Wilson_, Aug 01 2001

%F G.f.: Sum_{k>=0} 2^k*x^2^k/(1 - x^2^(k+1)). - _Ralf Stephan_, May 06 2003

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

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

%F a(n) = 2^A007814(n). - _R. J. Mathar_, Oct 25 2010

%F a((2*k - 1)*2^e) = 2^e, k >= 1, e >= 0. - _Johannes W. Meijer_, Jun 07 2011

%F a(n) = denominator of Euler(n-1, 1). - _Arkadiusz Wesolowski_, Jul 12 2012

%F a(n) = A011782(A001511(n)). - _Omar E. Pol_, Sep 13 2013

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

%F a(n) = ((n XOR n-1)+1)/2. - _Gary Detlefs_, Jul 02 2014

%F a(n) = A171977(n)/2. - _Peter Kern_, Jan 04 2017

%F a(n) = 2^(A001511(n)-1). - _Doug Bell_, Jun 02 2017

%F a(n) = abs(A003188(n-1) - A003188(n)). - _Doug Bell_, Jun 02 2017

%F Conjecture: a(n) = (1/(A000203(2*n)/A000203(n)-2)+1)/2. - _Velin Yanev_, Jun 30 2017

%F a(n) = (n-1) o n where 'o' is the bitwise converse nonimplication. 'o' is not commutative. n o (n+1) = A135481(n). - _Peter Luschny_, Oct 10 2019

%F From _Peter Munn_, Dec 13 2019: (Start)

%F a(A225546(n)) = A225546(A007913(n)).

%F a(A059897(n,k)) = A059897(a(n), a(k)).

%F (End)

%F Sum_{k=1..n} a(k) ~ (1/(2*log(2)))*n*log(n) + (3/4 + (gamma-1)/(2*log(2)))*n, where gamma is Euler's constant (A001620). - _Amiram Eldar_, Nov 15 2022

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

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

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

%e Per _Marc LeBrun_'s 2000 comment, a(n) can also be determined with bitwise operations in two's complement. For example, given n = 48, we see that n in binary in an 8-bit byte is 00110000 while -n is 11010000. Then 00110000 AND 11010000 = 00010000, which is 16 in decimal, and therefore a(48) = 16.

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

%p 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:

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

%p A006519 := n -> 2^padic[ordp](n,2): # _Peter Luschny_, Nov 26 2010

%t lowestOneBit[n_] := Block[{k = 0}, While[Mod[n, 2^k] == 0, k++]; 2^(k - 1)]; Table[lowestOneBit[n], {n, 102}] (* _Robert G. Wilson v_ Nov 17 2004 *)

%t Table[2^IntegerExponent[n, 2], {n, 128}] (* _Jean-François Alcover_, Feb 10 2012 *)

%t Table[BitAnd[BitNot[i - 1], i], {i, 1, 102}] (* _Peter Luschny_, Oct 10 2019 *)

%o (PARI) {a(n) = 2^valuation(n, 2)};

%o (PARI) a(n)=1<<valuation(n,2); \\ _Joerg Arndt_, Jun 10 2011

%o (PARI) a(n)=bitand(n,-n); \\ _Joerg Arndt_, Jun 10 2011

%o (PARI) a(n)=direuler(p=2,n,if(p==2,1/(1-2*X),1/(1-X)))[n] \\ _Ralf Stephan_, Mar 27 2015

%o (Haskell)

%o import Data.Bits ((.&.))

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

%o -- _Reinhard Zumkeller_, Mar 11 2012, Dec 29 2011

%o (Magma) [2^Valuation(n, 2): n in [1..100]]; // _Vincenzo Librandi_, Mar 27 2015

%o (Scala) (1 to 128).map(Integer.lowestOneBit(_)) // _Alonso del Arte_, Mar 04 2020

%o (Julia)

%o using IntegerSequences

%o [EvenPart(n) for n in 1:102] |> println # _Peter Luschny_, Sep 25 2021

%o (Python)

%o def A006519(n): return n&-n # _Chai Wah Wu_, Jul 06 2022

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

%Y Sequences used in definitions of this sequence: A000079, A001511, A004198, A007814.

%Y Cf. A100338, A003484, A001620, A101119, A002487, A139250.

%Y Sequences with related definitions: A038712, A171977, A135481 (GS(1, 6)).

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

%Y Related to A007913 via A225546.

%Y A059897 is used to express relationship between sequence terms.

%Y Cf. A091476 (Dgf at s=2).

%K nonn,easy,nice,mult,hear

%O 1,2

%A _N. J. A. Sloane_, _Simon Plouffe_

%E More terms from _James A. Sellers_, Jun 20 2000