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