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
Examples
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)
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.
Crossrefs
Programs
-
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
-
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 # second Maple program: a:= n-> Bits[Xor](n, n-1): seq(a(n), n=1..98); # Alois P. Heinz, Feb 02 2023
-
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 *) -
PARI
vector(66,n,bitxor(n-1,n)) \\ Joerg Arndt, Sep 01 2013; corrected by Michel Marcus, Aug 02 2018
-
PARI
A038712(n) = ((1<<(1+valuation(n,2)))-1); \\ Antti Karttunen, Nov 24 2024
-
Python
def A038712(n): return n^(n-1) # Chai Wah Wu, Jul 05 2022
Formula
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
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
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) = 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
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
Comments