A089312 -id:A089312 - cp's OEIS frontend

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

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

A089309 Write n in binary; a(n) = length of the rightmost run of 1's.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 2, 1, 3, 4, 1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 3, 1, 4, 5, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 2, 1, 3, 4, 2, 1, 1, 2, 1, 1, 2, 3, 3, 1, 1, 2, 4, 1, 5, 6, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 2, 1, 3, 4, 1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 3, 1, 4, 5, 2, 1, 1, 2, 1, 1, 2, 3, 1

Offset: 0

N. J. A. Sloane, Dec 22 2003

Equivalent to: remove trailing zeros, add one, count trailing zeros. - Ralf Stephan, Aug 31 2013

a(n) is also the difference between the two largest distinct parts in the integer partition having viabin number n (we assume that 0 is a part). The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2,2,2,1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20. Note that a(20) = 1 = the difference between the two largest distinct parts of the partition [2,2,2,1]. - Emeric Deutsch, Aug 17 2017

			13 = 1101 so a(13) = 1.

Alois P. Heinz, Table of n, a(n) for n = 0..16384
Francis Laclé, 2-adic parity explorations of the 3n+ 1 problem, hal-03201180v2 [cs.DM], 2021.
Index entries for sequences related to binary expansion of n

Cf. A089310, A089311, A089312, A089313.

a := proc(n) if n = 0 then 0 elif `mod`(n, 2) = 0 then a((1/2)*n) elif `mod`(n, 4) = 1 then 1 else 1+a((1/2)*n-1/2) end if end proc: seq(a(n), n = 0 .. 104); # Emeric Deutsch, Aug 17 2017

Table[If[n == 0, 0, Length@ Last@ Select[Split@ IntegerDigits[n, 2], First@ # == 1 &]], {n, 0, 104}] (* Michael De Vlieger, Aug 17 2017 *)

a(n) = if (n==0, 0, valuation(n/2^valuation(n, 2)+1, 2)); \\ Ralf Stephan, Aug 31 2013; Michel Marcus, Apr 30 2020

def A089309(n): return (~((m:=n>>(~n&n-1).bit_length())+1)&m).bit_length() # Chai Wah Wu, Jul 13 2022

a(2*n) = a(n), a(2*n+1) = A007814(2*n+2) = A001511(n+1). - Ralf Stephan, Jan 31 2004

a(0) = 0, a(2*n) = a(n), a(4*n+1) = 1, a(4*n+3) = 1 + a(2*n+1) (the Maple program makes use of these equations). - Emeric Deutsch, Aug 17 2017

More terms from Vladeta Jovovic and John W. Layman, Jan 21 2004

A089313 Write n in binary; a(n) = number represented by second block of 1's from the right.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 3, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 3, 3, 3, 0, 7, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 0, 3, 3, 3, 3, 1, 3, 3, 0, 7, 7, 7, 0, 15, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 7, 1, 1, 0, 3, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 3, 0, 7, 7, 7, 7, 1, 7, 7, 0

Offset: 0

N. J. A. Sloane, Dec 22 2003

			13 = 1101 so a(13) = 3.

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A089309, A089310, A089311, A089312.

f:= proc(n) local t,q,r;
  r:= 0: t:= n;
  while t::even do t:= t/2 od;
  while t::odd do t:= (t-1)/2 od;
  if t = 0 then return 0 fi;
  while t::even do t:= t/2 od;
  while t::odd do r:= 2*r+1; t:= (t-1)/2 od;
  r
end proc:
f(0):= 0:
map(f, [$0..120]); # Robert Israel, Aug 03 2025

sb1[n_]:=With[{c=If[#[[1]]==0,Nothing,#]&/@Split[IntegerDigits[n,2]]},If[Length[c]==1,0,FromDigits[c[[-2]],2]]]; Join[{0},Table[sb1[n],{n,120}]] (* Harvey P. Dale, Aug 02 2025 *)

{ a(n) = local(b,l,r,c); b=binary(n); l=length(b); while(l&&b[l]==0,l--); while(l&&b[l]==1,l--); while(l&&b[l]==0,l--); r=0; c=0; while(l&&b[l],r+=2^c;l--;c++); r; }
for(i=0,200,print1(a(i),", ")) \\ Lambert Klasen (Lambert.Klasen(AT)gmx.net), Sep 09 2005

a(n) = 2^A089310(n)-1. - David Wasserman, Sep 09 2005

More terms from David Wasserman and Lambert Klasen (Lambert.Klasen(AT)gmx.net), Sep 09 2005

Corrected and extended by Harvey P. Dale, Aug 02 2025

A089310 Write n in binary; a(n) = number of 1's in second block of 1's from right.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 2, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 2, 2, 2, 0, 3, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 0, 2, 2, 2, 2, 1, 2, 2, 0, 3, 3, 3, 0, 4, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 3, 1, 1, 0, 2, 2, 2

Offset: 0

N. J. A. Sloane, Dec 22 2003

			13 = 1101 so a(13) = 2.

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A089309, A089311, A089312, A089313.

f:= proc(n) local t,q,r;
  r:= 0: t:= n;
  while t::even do t:= t/2 od;
  while t::odd do t:= (t-1)/2 od;
  if t = 0 then return 0 fi;
  while t::even do t:= t/2 od;
  while t::odd do r:= r+1; t:= (t-1)/2 od;
  r
end proc:
f(0):= 0:
map(f, [$0..100]); # Robert Israel, Aug 03 2025

a(n)=my(b, c, s); if(n==0,return(0)); b=binary(n); c=length(b); while(!b[c], c=c-1); while(c>0&&b[c], c=c-1); if(c<=0, 0, while(!b[c], c=c-1); s=0; while(c>0&&b[c], c=c-1;s=s+1);s) /* Ralf Stephan, Feb 01 2004 */

More terms from Ralf Stephan, Feb 01 2004

cp's OEIS Frontend

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

A089309 Write n in binary; a(n) = length of the rightmost run of 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A089313 Write n in binary; a(n) = number represented by second block of 1's from the right.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A089310 Write n in binary; a(n) = number of 1's in second block of 1's from right.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Extensions