A086799 -id:A086799 - cp's OEIS frontend

A006519 Highest power of 2 dividing n.

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

Offset: 1

N. J. A. Sloane, Simon Plouffe

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(3*x + 1, -3*x - 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 in place 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
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

			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.
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.
G.f. = x + 2*x^2 + x^3 + 4*x^4 + x^5 + 2*x^6 + x^7 + 8*x^8 + x^9 + ...

Kurt 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).

T. D. Noe, Table of n, a(n) for n = 1..10000
Dzmitry Badziahin and Jeffrey Shallit, An Unusual Continued Fraction, arXiv:1505.00667 [math.NT], 2015.
Dzmitry Badziahin and Jeffrey Shallit, An unusual continued fraction, Proc. Amer. Math. Soc. 144 (2016), 1887-1896.
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.
M. Beeler, R. W. Gosper and R. Schroeppel, Item 175, in Beeler, M., Gosper, R. W. and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb 29 1972.
Ron Brown and Jonathan L. Merzel, The number of Ducci sequences with a given period, Fib. Quart., 45 (2007), 115-121.
Daniel Bruns, Wojciech Mostowski, and Mattias Ulbrich, Implementation-level verification of algorithms with KeY, International Journal on Software Tools for Technology Transfer, November 2013.
Victor Meally, Letter to N. J. A. Sloane, May 1975.
Laurent Orseau, Levi H. S. Lelis, and Tor Lattimore, Zooming Cautiously: Linear-Memory Heuristic Search With Node Expansion Guarantees, arXiv:1906.03242 [cs.AI], 2019.
Laurent Orseau, Levi H. S. Lelis, Tor Lattimore, and Théophane Weber, Single-Agent Policy Tree Search With Guarantees, 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.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Eric Weisstein's World of Mathematics, Even Part.
Wikipedia, Converse nonimplication.
Index entries for sequences related to binary expansion of n.

Partial sums are in A006520, second partial sums in A022560.
Sequences used in definitions of this sequence: A000079, A001511, A004198, A007814.
Cf. A000265, A100338, A003484, A001620, A101119, A002487, A139250.
Sequences with related definitions: A038712, A171977, A135481 (GS(1, 6)).
This is Guy Steele's sequence GS(5, 2) (see A135416).
Related to A007913 via A225546.
A059897 is used to express relationship between sequence terms.
Cf. A091476 (Dgf at s=2).

import Data.Bits ((.&.))
a006519 n = n .&. (-n) :: Integer
-- Reinhard Zumkeller, Mar 11 2012, Dec 29 2011

using IntegerSequences
[EvenPart(n) for n in 1:102] |> println  # Peter Luschny, Sep 25 2021

[2^Valuation(n, 2): n in [1..100]]; // Vincenzo Librandi, Mar 27 2015

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

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 *)
Table[2^IntegerExponent[n, 2], {n, 128}] (* Jean-François Alcover, Feb 10 2012 *)
Table[BitAnd[BitNot[i - 1], i], {i, 1, 102}] (* Peter Luschny, Oct 10 2019 *)

PARI
```
{a(n) = 2^valuation(n, 2)};
```
PARI
```
a(n)=1<Joerg Arndt, Jun 10 2011
```

a(n)=bitand(n,-n); \\ Joerg Arndt, Jun 10 2011

a(n)=direuler(p=2,n,if(p==2,1/(1-2*X),1/(1-X)))[n] \\ Ralf Stephan, Mar 27 2015

def A006519(n): return n&-n # Chai Wah Wu, Jul 06 2022

(1 to 128).map(Integer.lowestOneBit()) // _Alonso del Arte, Mar 04 2020

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
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) = zeta(s)*(1 - 2^(-s))/(1 - 2*2^(-s)). - 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
a(n) = A171977(n)/2. - Peter Kern, Jan 04 2017
a(n) = 2^(A001511(n)-1). - Doug Bell, Jun 02 2017
a(n) = abs(A003188(n-1) - A003188(n)). - Doug Bell, Jun 02 2017
Conjecture: a(n) = (1/(A000203(2*n)/A000203(n)-2)+1)/2. - Velin Yanev, Jun 30 2017
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
From Peter Munn, Dec 13 2019: (Start)
a(A225546(n)) = A225546(A007913(n)).
a(A059897(n,k)) = A059897(a(n), a(k)). (End)
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
a(n) = n / A000265(n). - Amiram Eldar, May 22 2025

More terms from James Sellers, Jun 20 2000

A038712 Let k be the exponent of highest power of 2 dividing n (A007814); a(n) = 2^(k+1)-1.

Original entry on oeis.org

1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 63, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 127, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 63, 1, 3

Offset: 1

Henry Bottomley, May 02 2000

n XOR n-1, i.e., nim-sum of a pair of consecutive numbers.
Denominator of quotient sigma(2*n)/sigma(n). - Labos Elemer, Nov 04 2003
a(n) = the Towers of Hanoi disc moved at the n-th move, using standard moves with discs labeled (1, 3, 7, 15, ...) starting from top (smallest = 1). - Gary W. Adamson, Oct 26 2009
Equals row sums of triangle A168312. - Gary W. Adamson, Nov 22 2009
In the binary expansion of n, delete everything left of the rightmost 1 bit, and set all bits to the right of it. - Ralf Stephan, Aug 22 2013
Every finite sequence of positive integers summing to n may be termwise dominated by a subsequence of the first n values in this sequence [see Bannister et al., 2013]. - David Eppstein, Aug 31 2013
Sum of powers of 2 dividing n. - Omar E. Pol, Aug 18 2019
Given the binary expansion of (n-1) as {b[k-1], b[k-2], ..., b[2], b[1], b[0]}, then the binary expansion of a(n) is {bitand(b[k-1], b[k-2], ..., b[2], b[1], b[0]), bitand(b[k-2], ..., b[2], b[1], b[0]), ..., bitand(b[2], b[1], b[0]), bitand(b[1], b[0]), b[0], 1}. Recursively stated - 0th bit (L.S.B) of a(n), a(n)[0] = 1, a(n)[i] = bitand(a(n)[i-1], (n-1)[i-1]), where n[i] = i-th bit in the binary expansion of n. - Chinmaya Dash, Jun 27 2020

			a(6) = 3 because 110 XOR 101 = 11 base 2 = 3.
From _Omar E. Pol_, Aug 18 2019: (Start)
Illustration of initial terms:
a(n) is also the area of the n-th region of an infinite diagram of compositions (ordered partitions) of the positive integers, where the length of the n-th horizontal line segment is equal to A001511(n) and the length of the n-th vertical line segment is equal to A006519(n), as shown below (first eight regions):
-----------------------------
n    a(n)    Diagram
-----------------------------
.            _ _ _ _
1     1     |_| | | |
2     3     |_ _| | |
3     1     |_|   | |
4     7     |_ _ _| |
5     1     |_| |   |
6     3     |_ _|   |
7     1     |_|     |
8    15     |_ _ _ _|
.
The above diagram represents the eight compositions of 4: [1,1,1,1],[2,1,1],[1,2,1],[3,1],[1,1,2],[2,2],[1,3],[4].
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, Superpatterns and universal point sets, 21st Int. Symp. Graph Drawing, 2013, arXiv:1308.0403 [cs.CG], 2013.
Klaus Brockhaus, Illustration of A038712 and A080277.
David Eppstein, 1317131 and majorization by subsequences.
Fabrizio Frati, M. Patrignani, and V. Roselli, LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs, arXiv preprint arXiv:1610.02841 [cs.CG], 2016.
Malgorzata J. Krawczyk, Paweł Oświęcimka, and Krzysztof Kułakowski, Ordered Avalanches on the Bethe Lattice, Entropy, Vol. 21, (2019) 968.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Index entries for sequences related to binary expansion of n.
Index entries for sequences related to Nim-sums.

A038713 translated from binary, diagonals of A003987 on either side of main diagonal.
Cf. A062383. Partial sums give A080277.
Bisection of A089312. Cf. A088837.
a(n)-1 is exponent of 2 in A089893(n).
Cf. A130093.
This is Guy Steele's sequence GS(6, 2) (see A135416).
Cf. A001620, A168312, A220466, A361019 (Dirichlet inverse).

int a(int n) { return n ^ (n-1); } // Russ Cox, May 15 2007

import Data.Bits (xor)
a038712 n = n `xor` (n - 1) :: Integer  -- Reinhard Zumkeller, Apr 23 2012

nmax:=98: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := 2^(p+1)-1 od: od: seq(a(n), n=1..nmax); # Johannes W. Meijer, Feb 01 2013
# second Maple program:
a:= n-> Bits[Xor](n, n-1):
seq(a(n), n=1..98);  # Alois P. Heinz, Feb 02 2023

Table[Denominator[DivisorSigma[1, 2*n]/DivisorSigma[1, n]], {n, 1, 128}]
Table[BitXor[(n + 1), n], {n, 0, 100}] (* Vladimir Joseph Stephan Orlovsky, Jul 19 2011 *)

vector(66,n,bitxor(n-1,n)) \\ Joerg Arndt, Sep 01 2013; corrected by Michel Marcus, Aug 02 2018

A038712(n) = ((1<<(1+valuation(n,2)))-1); \\ Antti Karttunen, Nov 24 2024

def A038712(n): return n^(n-1) # Chai Wah Wu, Jul 05 2022

a(n) = A110654(n-1) XOR A008619(n). - Reinhard Zumkeller, Feb 05 2007
a(n) = 2^A001511(n) - 1 = 2*A006519(n) - 1 = 2^(A007814(n)+1) - 1.
Multiplicative with a(2^e) = 2^(e+1)-1, a(p^e) = 1, p > 2. - Vladeta Jovovic, Nov 06 2001; corrected by Jianing Song, Aug 03 2018
Sum_{n>0} a(n)*x^n/(1+x^n) = Sum_{n>0} x^n/(1-x^n). Inverse Moebius transform of A048298. - Vladeta Jovovic, Jan 02 2003
From Ralf Stephan, Jun 15 2003: (Start)
G.f.: Sum_{k>=0} 2^k*x^2^k/(1 - x^2^k).
a(2*n+1) = 1, a(2*n) = 2*a(n)+1. (End)
Equals A130093 * [1, 2, 3, ...]. - Gary W. Adamson, May 13 2007
Sum_{i=1..n} (-1)^A000120(n-i)*a(i) = (-1)^(A000120(n)-1)*n. - Vladimir Shevelev, Mar 17 2009
Dirichlet g.f.: zeta(s)/(1 - 2^(1-s)). - R. J. Mathar, Mar 10 2011
a(n) = A086799(2*n) - 2*n. - Reinhard Zumkeller, Aug 07 2011
a((2*n-1)*2^p) = 2^(p+1)-1, p >= 0. - Johannes W. Meijer, Feb 01 2013
a(n) = A000225(A001511(n)). - Omar E. Pol, Aug 31 2013
a(n) = A000203(n)/A000593(n). - Ivan N. Ianakiev and Omar E. Pol, Dec 14 2017
L.g.f.: -log(Product_{k>=0} (1 - x^(2^k))) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, Mar 15 2018
a(n) = 2^(1 + (A183063(n)/A001227(n))) - 1. - Omar E. Pol, Nov 06 2018
a(n) = sigma(n)/(sigma(2*n) - 2*sigma(n)) = 3*sigma(n)/(sigma(4*n) - 4*sigma(n)) = 7*sigma(n)/(sigma(8*n) - 8*sigma(n)), where sigma(n) = A000203(n). - Peter Bala, Jun 10 2022
Sum_{k=1..n} a(k) ~ n*log_2(n) + (1/2 + (gamma - 1)/log(2))*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 24 2022
a(n) = Sum_{d divides n} m(d)*phi(d), where m(n) = Sum_{d divides n} (-1)^(d+1)* mobius(d). - Peter Bala, Jan 23 2024

Definition corrected by N. J. A. Sloane, Sep 07 2015 at the suggestion of Marc LeBrun

Name corrected by Wolfdieter Lang, Aug 30 2016

A220466 a((2n-1)2^p) = 4^p(n-1) + 2^(p-1)(1+2^p), p >= 0 and n >= 1.

Original entry on oeis.org

1, 3, 2, 10, 3, 7, 4, 36, 5, 11, 6, 26, 7, 15, 8, 136, 9, 19, 10, 42, 11, 23, 12, 100, 13, 27, 14, 58, 15, 31, 16, 528, 17, 35, 18, 74, 19, 39, 20, 164, 21, 43, 22, 90, 23, 47, 24, 392, 25, 51, 26, 106, 27, 55, 28, 228, 29, 59, 30, 122, 31, 63, 32, 2080, 33, 67, 34, 138, 35

Offset: 1

Johannes W. Meijer, Dec 24 2012

The a(n) appeared in the analysis of A220002, a sequence related to the Catalan numbers.
The first Maple program makes use of a program by Peter Luschny for the calculation of the a(n) values. The second Maple program shows that this sequence has a beautiful internal structure, see the first formula, while the third Maple program makes optimal use of this internal structure for the fast calculation of a(n) values for large n.
The cross references lead to sequences that have the same internal structure as this sequence.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences with simple ordinary generating functions, The OEIS, Jan 01 2004.

Cf. A000027 (the natural numbers), A000120 (1's-counting sequence), A000265 (remove 2's from n), A001316 (Gould's sequence), A001511 (the ruler function), A003484 (Hurwitz-Radon numbers), A003602 (a fractal sequence), A006519 (highest power of 2 dividing n), A007814 (binary carry sequence), A010060 (Thue-Morse sequence), A014577 (dragon curve), A014707 (dragon curve), A025480 (nim-values), A026741, A035263 (first Feigenbaum symbolic sequence), A037227, A038712, A048460, A048896, A051176, A053381 (smooth nowhere-zero vector fields), A055975 (Gray code related), A059134, A060789, A060819, A065916, A082392, A085296, A086799, A088837, A089265, A090739, A091512, A091519, A096268, A100892, A103391, A105321 (a fractal sequence), A109168 (a continued fraction), A117973, A129760, A151930, A153733, A160467, A162728, A181988, A182241, A191488 (a companion to Gould's sequence), A193365, A220466 (this sequence).

-- Following Ralf Stephan's recurrence:
import Data.List (transpose)
a220466 n = a006519_list !! (n-1)
a220466_list = 1 : concat
   (transpose [zipWith (-) (map (* 4) a220466_list) a006519_list, [2..]])
-- Reinhard Zumkeller, Aug 31 2014

# First Maple program
a := n -> 2^padic[ordp](n, 2)*(n+1)/2 : seq(a(n), n=1..69); # Peter Luschny, Dec 24 2012
# Second Maple program
nmax:=69: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := 4^p*(n-1)  + 2^(p-1)*(1+2^p) od: od: seq(a(n), n=1..nmax);
# Third Maple program
nmax:=69: for p from 0 to ceil(simplify(log[2](nmax))) do n:=2^p: n1:=1: while n <= nmax do a(n) := 4^p*(n1-1)+2^(p-1)*(1+2^p): n:=n+2^(p+1): n1:= n1+1: od: od:  seq(a(n), n=1..nmax);

A220466 = Module[{n, p}, p = IntegerExponent[#, 2]; n = (#/2^p + 1)/2; 4^p*(n - 1) + 2^(p - 1)*(1 + 2^p)] &; Array[A220466, 50] (* JungHwan Min, Aug 22 2016 *)

a(n)=if(n%2,n\2+1,4*a(n/2)-2^valuation(n/2,2)) \\ Ralf Stephan, Dec 17 2013

a((2*n-1)*2^p) = 4^p*(n-1) + 2^(p-1)*(1+2^p), p >= 0 and n >= 1. Observe that a(2^p) = A007582(p).
a(n) = ((n+1)/2)*(A060818(n)/A060818(n-1))
a(n) = (-1/64)*(q(n+1)/q(n))/(2*n+1) with q(n) = (-1)^(n+1)*2^(4*n-5)*(2*n)!*A060818(n-1) or q(n) = (1/8)*A220002(n-1)*1/(A098597(2*n-1)/A046161(2*n))*1/(A008991(n-1)/A008992(n-1))
Recurrence: a(2n) = 4a(n) - 2^A007814(n), a(2n+1) = n+1. - Ralf Stephan, Dec 17 2013

A129760 Bitwise AND of binary representation of n-1 and n.

Original entry on oeis.org

0, 0, 2, 0, 4, 4, 6, 0, 8, 8, 10, 8, 12, 12, 14, 0, 16, 16, 18, 16, 20, 20, 22, 16, 24, 24, 26, 24, 28, 28, 30, 0, 32, 32, 34, 32, 36, 36, 38, 32, 40, 40, 42, 40, 44, 44, 46, 32, 48, 48, 50, 48, 52, 52, 54, 48, 56, 56, 58, 56, 60, 60, 62, 0, 64, 64, 66, 64, 68, 68, 70, 64, 72, 72, 74

Offset: 1

Russ Cox, May 15 2007

Also the number of Ducci sequences with period n.
Also largest number less than n having in binary representation fewer ones than n has; A048881(n-1) = A000120(a(n)) = A000120(n)-1. - Reinhard Zumkeller, Jun 30 2010
a(n) is the parent of vertex n in the binomial tree.  The binomial tree is root vertex n=0, then for n>=1 the parent of n is n with its least significant 1-bit changed to a 0-bit.  Binomial tree order 5, n=0 to 31 inclusive, is the frontispiece of Knuth volume 1, second and subsequent editions.  Vertices are shown there with n in binary dots and a(n) is the next vertex towards the root at the bottom of the page. - Kevin Ryde, Jul 24 2019

			a(6) = 6 AND 5 = binary 110 AND 101 = binary 100 = 4.

Donald E. Knuth, The Art of Computer Programming, volume 1, second edition, frontispiece. Reproduced with brief description of the art in Donald E. Knuth, Selected Papers on Fun and Games, 2010, Chapter 47 Geek Art, figure 16, page 679.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ron Brown and Jonathan L. Merzel, The number of Ducci sequences with a given period, Fib. Quart., 45 (2007), 115-121.

Cf. A038712, A086799, A104594, A059991, A006519, A109168, A220466.

C
```
int a(int n) { return n & (n-1); }
```

[n - 2^Valuation(n, 2): n in [1..100]]; // Vincenzo Librandi, Jul 25 2019

nmax := 75: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := (2*n-2) * 2^p od: od: seq(a(n), n=1..nmax); # Johannes W. Meijer, Jun 22 2011, revised Jan 25 2013
A129760 := n -> Bits:-And(n-1, n):
seq(A129760(n), n=1..75); # Peter Luschny, Sep 26 2019

Table[BitAnd[n, n - 1], {n, 1, 100}] (* Vladimir Joseph Stephan Orlovsky, Jul 19 2011 *)

a(n)=bitand(n,n-1) \\ Charles R Greathouse IV, Jun 23 2011

def a(n): return n & (n-1)
print([a(n) for n in range(1, 71)]) # Michael S. Branicky, Jul 13 2022

a(n) = n AND n-1.
Equals n - A006519(n). - N. J. A. Sloane, May 26 2008
From Johannes W. Meijer, Jun 22 2011: (Start)
a((2*n-1)*2^p) = (2*n-2)*(2^p), p>=0.
a(2*n-1) = (2*n-2), n>=1, and a(2^p+1) = 2^p, p>=1. (End)

A063787 a(2^k) = k + 1 and a(2^k + i) = 1 + a(i) for k >= 0 and 0 < i < 2^k.

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4

Offset: 1

Reinhard Zumkeller, Aug 16 2001

nonn

Hamming weights of odd numbers. - Friedjof Tellkamp, Jan 11 2024

			k = 3: a(2^3) = a(8) = 4 = 3 + 1.
k = 3, i = 5: a(2^3 + 5) = a(13) = 3 = 1 + 2 = 1 + a(5).
From _Omar E. Pol_, Jun 12 2009: (Start)
Triangle begins:
  1;
  2,2;
  3,2,3,3;
  4,2,3,3,4,3,4,4;
  5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5;
  6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6;
  7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,...
(End)

Michael Gilleland, Some Self-Similar Integer Sequences

Cf. A000079, A000120, A007814, A086799, A047457, A131136.

Cf. A330038 (partial sums).

Table[DigitCount[2 n - 1, 2, 1], {n, 1, 105}] (* Friedjof Tellkamp, Jan 11 2024 *)

a(n) = hammingweight(n-1) + 1; \\ Michel Marcus, Nov 23 2022

def a(n): return bin(n-1).count('1') + 1
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, Dec 16 2021

a(n) = A000120(n-1) + 1.
a(n) = log(A131136)/log(2). - Stephen Crowley, Aug 25 2008
a(n) = A007814(n) + A000120(n). - Gary W. Adamson, Jun 04 2009
a(n) = A000120(A086799(n)). - Reinhard Zumkeller, Jul 31 2010
a(n) = A000120(A047457(n)-1) = A000120(A047457(n)+1). - Ilya Lopatin, Mar 16 2014
a(n) = A000120(2n-1). - Friedjof Tellkamp, Jan 11 2024

A182187 a(n) is the least m >= n such that the Hamming distance D(n,m) = 2.

Original entry on oeis.org

3, 2, 4, 5, 7, 6, 10, 11, 11, 10, 12, 13, 15, 14, 22, 23, 19, 18, 20, 21, 23, 22, 26, 27, 27, 26, 28, 29, 31, 30, 46, 47, 35, 34, 36, 37, 39, 38, 42, 43, 43, 42, 44, 45, 47, 46, 54, 55, 51, 50, 52, 53, 55, 54, 58, 59, 59, 58, 60, 61, 63, 62, 94, 95, 67, 66, 68

Offset: 0

Vladimir Shevelev, Apr 17 2012

a(n) = n<+>2 (see comment in A206853).

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A206853 (trajectory of 1), A207063 (trajectory of 0).
Cf. A209544 (primes which are not terms), A209554 (and also not n<+>3).
Cf. A086799 ((n-1)<+>1), A182209 (n<+>3), A182336 (n<+>4).
Cf. A205509, A205510, A205511, A205302, A205649, A205533, A122565, A206852, A206960, A007814.

HD:= (i, j)-> add(h, h=Bits[Split](Bits[Xor](i, j))):
a:= proc(n) local c;
      for c from n do if HD(n, c)=2 then return c fi od
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 17 2012

t={}; Do[i=n+1; While[Count[IntegerDigits[BitXor[n,i],2],1]!=2,i++]; AppendTo[t,i],{n,0,66}]; t (* Jayanta Basu, May 26 2013 *)

a(n) = bitxor(n, 3<>1+1,2)); \\ Kevin Ryde, Jul 09 2021

def a(n):
  m = n + 1
  while bin(n^m).count('1') != 2: m += 1
  return m
print([a(n) for n in range(67)]) # Michael S. Branicky, Mar 02 2021

def A182187(n):
    S = n.bits(); T = S; c = n; L = len(S)
    while true:
         H = sum(a != b for a, b in zip(S, T))
         if H == 2: return c
         c += 1; T = c.bits()
         if len(T) > L: L += 1; S.append(0)
[A182187(n) for n in (0..66)]   # Peter Luschny, May 26 2013

If n is odd, then a(n) = n+2^(A007814(n+1)-1); if n == 2 (mod 4), then a(n) = n+2^(A007814(n+2)-1); if n == 0 (mod 4), then a(n) = n+3.
Using this formula, we can prove the conjecture formulated in comment in A209554 in the case k=2. Moreover, let us show that if N does not have the form 8*t or 8*t+1, then it can be represented in the form n<+>2. Indeed, in the cases N = 8*t+2, 8*t+4, 8*t+6, 8*t+3, 8*t+5 and 8*t+7 it is sufficient to choose n=N-4, n=N-2, n=N-1, n=N-3, n=N-2 and n = N-3 respectively; in the cases 8*t, 8*t+1, for every choice of n <= N, we do not obtain the equality n<+>2 = N.
In addition, note that n<+>1 = n + 2^A007814(n+1) = A086799(n+1).

More terms from Alois P. Heinz, Apr 17 2012

A175329 a(n) = bitwise OR of prime(n) and prime(n+1).

Original entry on oeis.org

3, 7, 7, 15, 15, 29, 19, 23, 31, 31, 63, 45, 43, 47, 63, 63, 63, 127, 71, 79, 79, 95, 91, 121, 101, 103, 111, 111, 125, 127, 255, 139, 139, 159, 151, 159, 191, 167, 175, 191, 183, 191, 255, 197, 199, 215, 223, 255, 231, 237, 239, 255, 251, 507, 263, 271, 271, 287

Offset: 1

Leroy Quet, Apr 07 2010

Read each binary representation of the primes from right to left and then OR respective digits to form the binary equivalent of each term of this sequence.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Wikipedia, Bitwise operation

Cf. A000040, A175330 (bitwise AND).

Cf. A086799 (bitwise OR of n and n-1).

read("transforms") ; A175329 := proc(n) ORnos(ithprime(n),ithprime(n+1)) ; end proc: seq(A175329(n),n=1..60) ; # R. J. Mathar, Apr 15 2010
# second Maple program:
a:= n-> Bits[Or](ithprime(n), ithprime(n+1)):
seq(a(n), n=1..70);  # Alois P. Heinz, Apr 16 2020

A175329[n_]:=BitOr[Prime[n],Prime[n+1]];Array[A175329,100] (* Paolo Xausa, Oct 13 2023 *)
BitOr@@#&/@Partition[Prime[Range[60]],2,1] (* Harvey P. Dale, Mar 01 2024 *)

a(n) = bitor(prime(n), prime(n+1)); \\ Michel Marcus, Apr 20 2020

More terms from R. J. Mathar, Apr 15 2010

A179857 Smallest number greater than n having in binary representation exactly twice the number of ones as n has in binary representation.

Original entry on oeis.org

3, 3, 15, 5, 15, 15, 63, 9, 15, 15, 63, 15, 63, 63, 255, 17, 23, 23, 63, 23, 63, 63, 255, 27, 63, 63, 255, 63, 255, 255, 1023, 33, 39, 39, 63, 39, 63, 63, 255, 43, 63, 63, 255, 63, 255, 255, 1023, 51, 63, 63, 255, 63, 255, 255, 1023, 63, 255, 255, 1023, 255, 1023, 1023

Offset: 1

Reinhard Zumkeller, Jul 31 2010

a(n) = Min{m: m > n and A000120(m) = 2*A000120(n)};
a(n) is odd;
n < a(n) < A000290(A062383(n));
a(A000079(n)) = A000051(n);
A024036 and A000225 give record values and where they occur.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Index entries for sequences related to binary expansion of n

Cf. A000120, A086799.
Cf. A000290, A062383.
Cf. A000051, A000079.
Cf. A000225, A024036.

br2[n_]:=Module[{k=If[EvenQ[n],n+1,n+2],t=2*DigitCount[n,2,1]},While[ DigitCount[ k,2,1]!=t,k=k+2];k]; Array[br2,70] (* Harvey P. Dale, Sep 20 2016 *)

a(n) = my(k=n+1, h=hammingweight(n)); while (hammingweight(k) != 2*h, k++); k; \\ Michel Marcus, Nov 13 2023

Definition clarified by Harvey P. Dale, Sep 20 2016

A182209 a(n) is the least m >= n, such that the Hamming distance D(n,m) = 3.

Original entry on oeis.org

7, 6, 5, 4, 9, 8, 8, 9, 15, 14, 13, 12, 16, 17, 18, 19, 23, 22, 21, 20, 25, 24, 24, 25, 31, 30, 29, 28, 36, 37, 38, 39, 39, 38, 37, 36, 41, 40, 40, 41, 47, 46, 45, 44, 48, 49, 50, 51, 55, 54, 53, 52, 57, 56, 56, 57, 63, 62, 61, 60, 76, 77, 78, 79, 71, 70, 69

Offset: 0

Vladimir Shevelev, Apr 18 2012

a(n) = n<+>3 (see comment in A206853).

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Cf. A086799 ((n-1)<+>1), A182187 (n<+>2), A182336 (n<+>4).
Cf. A209554 (primes which are not terms nor n<+>2 terms).
Cf. A205509, A205510, A205511, A205302, A205649, A205533, A122565, A206852, A206960, A007814.

HD:= (i, j)-> add(h, h=Bits[Split](Bits[Xor](i, j))):
a:= proc(n) local c;
      for c from n do if HD(n, c)=3 then return c fi od
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 18 2012

a(n) = bitxor(n, if(bitand(n,14)==4, 13, 7<>2+1,2))); \\ Kevin Ryde, Jul 10 2021

def d(n, m): return bin(n^m).count('1')
def a(n):
    m = n+1
    while d(n, m) != 3: m += 1
    return m
print([a(n) for n in range(67)]) # Michael S. Branicky, Jul 06 2021

If n==i mod 8, then a(n) = n-2*i+7, i=0,1,2,3; if n==4 mod 16, then a(n) = n+5; if n==12 mod 16, then a(n) = n+2^(A007814(n+4)-2); if n==5 mod 16, then a(n) = n+3; if n==13 mod 16, then a(n) = n+2^(A007814(n+3)-2); if n==6 mod 8, then a(n) = n+2^(A007814(n+2)-2); if n==7 mod 8, then a(n) = n+2^(A007814(n+1)-2).

Using this formula, we can prove conjecture formulated in comment in A209554 in case k=3. Moreover, one can prove that N could be represented in form n<+>2 or n<+>3 iff N is not a number of the forms 32*t, 32*t+1. - Vladimir Shevelev, Apr 25 2012

cp's OEIS Frontend

A339597 When 2*n+1 first appears in A086799.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

PARI

Python

Formula

A006519 Highest power of 2 dividing n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Scala

Formula

Extensions

A038712 Let k be the exponent of highest power of 2 dividing n (A007814); a(n) = 2^(k+1)-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A220466 a((2*n-1)*2^p) = 4^p*(n-1) + 2^(p-1)*(1+2^p), p >= 0 and n >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A129760 Bitwise AND of binary representation of n-1 and n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Magma

Maple

A220466 a((2n-1)2^p) = 4^p(n-1) + 2^(p-1)(1+2^p), p >= 0 and n >= 1.