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

 

Logo
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. 65

%I #152 Jan 24 2024 08:03:01

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

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

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

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

%C n XOR n-1, i.e., nim-sum of a pair of consecutive numbers.

%C Denominator of quotient sigma(2*n)/sigma(n). - _Labos Elemer_, Nov 04 2003

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

%C Equals row sums of triangle A168312. - _Gary W. Adamson_, Nov 22 2009

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

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

%C Sum of powers of 2 dividing n. - _Omar E. Pol_, Aug 18 2019

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

%H Reinhard Zumkeller, <a href="/A038712/b038712.txt">Table of n, a(n) for n = 1..10000</a>

%H M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, <a href="http://arxiv.org/abs/1308.0403">Superpatterns and universal point sets</a>, 21st Int. Symp. Graph Drawing, 2013, arXiv:1308.0403 [cs.CG], 2013.

%H Klaus Brockhaus, <a href="/A038712/a038712.gif">Illustration of A038712 and A080277</a>.

%H David Eppstein, <a href="https://11011110.github.io/blog/2013/08/04/1317131-and-majorization.html">1317131 and majorization by subsequences</a>.

%H Fabrizio Frati, M. Patrignani, and V. Roselli, <a href="https://arxiv.org/abs/1610.02841">LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs</a>, arXiv preprint arXiv:1610.02841 [cs.CG], 2016.

%H Malgorzata J. Krawczyk, Paweł Oświęcimka, and Krzysztof Kułakowski, <a href="https://doi.org/10.3390/e21100968">Ordered Avalanches on the Bethe Lattice</a>, Entropy, Vol. 21, (2019) 968.

%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 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.

%H <a href="/index/Ni#Nimsums">Index entries for sequences related to Nim-sums</a>.

%F a(n) = A110654(n-1) XOR A008619(n). - _Reinhard Zumkeller_, Feb 05 2007

%F a(n) = 2^A001511(n) - 1 = 2*A006519(n) - 1 = 2^(A007814(n)+1) - 1.

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

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

%F From _Ralf Stephan_, Jun 15 2003: (Start)

%F G.f.: Sum_{k>=0} 2^k*x^2^k/(1 - x^2^k).

%F a(2*n+1) = 1, a(2*n) = 2*a(n)+1. (End)

%F Equals A130093 * [1, 2, 3, ...]. - _Gary W. Adamson_, May 13 2007

%F Sum_{i=1..n} (-1)^A000120(n-i)*a(i) = (-1)^(A000120(n)-1)*n. - _Vladimir Shevelev_, Mar 17 2009

%F Dirichlet g.f.: zeta(s)/(1 - 2^(1-s)). - _R. J. Mathar_, Mar 10 2011

%F a(n) = A086799(2*n) - 2*n. - _Reinhard Zumkeller_, Aug 07 2011

%F a((2*n-1)*2^p) = 2^(p+1)-1, p >= 0. - _Johannes W. Meijer_, Feb 01 2013

%F a(n) = A000225(A001511(n)). - _Omar E. Pol_, Aug 31 2013

%F a(n) = A000203(n)/A000593(n). - _Ivan N. Ianakiev_ and _Omar E. Pol_, Dec 14 2017

%F L.g.f.: -log(Product_{k>=0} (1 - x^(2^k))) = Sum_{n>=1} a(n)*x^n/n. - _Ilya Gutkovskiy_, Mar 15 2018

%F a(n) = 2^(1 + (A183063(n)/A001227(n))) - 1. - _Omar E. Pol_, Nov 06 2018

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

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

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

%e a(6) = 3 because 110 XOR 101 = 11 base 2 = 3.

%e From _Omar E. Pol_, Aug 18 2019: (Start)

%e Illustration of initial terms:

%e 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):

%e -----------------------------

%e n a(n) Diagram

%e -----------------------------

%e . _ _ _ _

%e 1 1 |_| | | |

%e 2 3 |_ _| | |

%e 3 1 |_| | |

%e 4 7 |_ _ _| |

%e 5 1 |_| | |

%e 6 3 |_ _| |

%e 7 1 |_| |

%e 8 15 |_ _ _ _|

%e .

%e 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].

%e (End)

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

%p # second Maple program:

%p a:= n-> Bits[Xor](n, n-1):

%p seq(a(n), n=1..98); # _Alois P. Heinz_, Feb 02 2023

%t Table[Denominator[DivisorSigma[1, 2*n]/DivisorSigma[1, n]], {n, 1, 128}]

%t Table[BitXor[(n + 1), n], {n, 0, 100}] (* _Vladimir Joseph Stephan Orlovsky_, Jul 19 2011 *)

%o (C) int a(int n) { return n ^ (n-1); } // _Russ Cox_, May 15 2007

%o (Haskell)

%o import Data.Bits (xor)

%o a038712 n = n `xor` (n - 1) :: Integer -- _Reinhard Zumkeller_, Apr 23 2012

%o (PARI) vector(66,n,bitxor(n-1,n)) \\ _Joerg Arndt_, Sep 01 2013; corrected by _Michel Marcus_, Aug 02 2018

%o (Python)

%o def A038712(n): return n^(n-1) # _Chai Wah Wu_, Jul 05 2022

%Y A038713 translated from binary, diagonals of A003987 on either side of main diagonal.

%Y Cf. A062383. Partial sums give A080277.

%Y Bisection of A089312. Cf. A088837.

%Y a(n)-1 is exponent of 2 in A089893(n).

%Y Cf. A130093.

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

%Y Cf. A001620, A168312, A220466.

%K easy,nonn,mult

%O 1,2

%A _Henry Bottomley_, May 02 2000

%E Definition corrected by _N. J. A. Sloane_, Sep 07 2015 at the suggestion of _Marc LeBrun_

%E Name corrected by _Wolfdieter Lang_, Aug 30 2016

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 March 29 05:43 EDT 2024. Contains 371264 sequences. (Running on oeis4.)