login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A038712 Let k be the exponent of highest power of 2 dividing n (A007814); a(n) = 2^(k+1)-1. 62
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

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.

FORMULA

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

EXAMPLE

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)

MAPLE

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

MATHEMATICA

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 *)

PROG

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

(Haskell)

import Data.Bits (xor)

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

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

(Python)

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

CROSSREFS

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.

Sequence in context: A021991 A112132 A053381 * A354587 A065745 A268670

Adjacent sequences: A038709 A038710 A038711 * A038713 A038714 A038715

KEYWORD

easy,nonn,mult,changed

AUTHOR

Henry Bottomley, May 02 2000

EXTENSIONS

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

Name corrected by Wolfdieter Lang, Aug 30 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 03:44 EST 2022. Contains 358649 sequences. (Running on oeis4.)