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!)
A006516 a(n) = 2^(n-1)*(2^n - 1), n >= 0.
(Formerly M4183)
128

%I M4183 #250 Feb 07 2024 19:42:40

%S 0,1,6,28,120,496,2016,8128,32640,130816,523776,2096128,8386560,

%T 33550336,134209536,536854528,2147450880,8589869056,34359607296,

%U 137438691328,549755289600,2199022206976,8796090925056,35184367894528,140737479966720,562949936644096

%N a(n) = 2^(n-1)*(2^n - 1), n >= 0.

%C a(n) is also the number of different lines determined by pair of vertices in an n-dimensional hypercube. The number of these lines modulo being parallel is in A003462. - Ola Veshta (olaveshta(AT)my-deja.com), Feb 15 2001

%C Let G_n be the elementary Abelian group G_n = (C_2)^n for n >= 1: A006516 is the number of times the number -1 appears in the character table of G_n and A007582 is the number of times the number 1. Together the two sequences cover all the values in the table, i.e., A006516(n) + A007582(n) = 2^(2n). - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 01 2001

%C a(n) is the number of n-letter words formed using four distinct letters, one of which appears an odd number of times. - _Lekraj Beedassy_, Jul 22 2003 [See, e.g., the Balakrishnan reference, problems 2.67 and 2.68, p. 69. - _Wolfdieter Lang_, Jul 16 2017]

%C Number of 0's making up the central triangle in a Pascal's triangle mod 2 gasket. - _Lekraj Beedassy_, May 14 2004

%C m-th triangular number, where m is the n-th Mersenne number, i.e., a(n)=A000217(A000225(n)). - _Lekraj Beedassy_, May 25 2004

%C Number of walks of length 2n+1 between two nodes at distance 3 in the cycle graph C_8. - _Herbert Kociemba_, Jul 02 2004

%C The sequence of fractions a(n+1)/(n+1) is the 3rd binomial transform of (1, 0, 1/3, 0, 1/5, 0, 1/7, ...). - _Paul Barry_, Aug 05 2005

%C Number of monic irreducible polynomials of degree 2 in GF(2^n)[x]. - _Max Alekseyev_, Jan 23 2006

%C (A007582(n))^2 + a(n)^2 = A007582(2n). E.g., A007582(3) = 36, a(3) = 28; A007582(6) = 2080. 36^2 + 28^2 = 2080. - _Gary W. Adamson_, Jun 17 2006

%C The sequence 6*a(n), n>=1, gives the number of edges of the Hanoi graph H_4^{n} with 4 pegs and n>=1 discs. - _Daniele Parisse_, Jul 28 2006

%C 8*a(n) is the total border length of the 4*n masks used when making an order n regular DNA chip, using the bidimensional Gray code suggested by Pevzner in the book "Computational Molecular Biology." - Bruno Petazzoni (bruno(AT)enix.org), Apr 05 2007

%C If we start with 1 in binary and at each step we prepend 1 and append 0, we construct this sequence: 1 110 11100 1111000 etc.; see A109241(n-1). - _Artur Jasinski_, Nov 26 2007

%C Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which x does not equal y. - _Ross La Haye_, Jan 02 2008

%C Wieder calls these "conjoint usual 2-combinations." The set of "conjoint strict k-combinations" is the subset of conjoint usual k-combinations where the empty set and the set itself are excluded from possible selection. These numbers C(2^n - 2,k), which for k = 2 (i.e., {x,y} of the power set of a set) give {1, 0, 1, 15, 91, 435, 1891, 7875, 32131, 129795, 521731, ...}. - _Ross La Haye_, Jan 15 2008

%C If n is a member of A000043 then a(n) is also a perfect number (A000396). - _Omar E. Pol_, Aug 30 2008

%C a(n) is also the number whose binary representation is A109241(n-1), for n>0. - _Omar E. Pol_, Aug 31 2008

%C From _Daniel Forgues_, Nov 10 2009: (Start)

%C If we define a spoof-perfect number as:

%C A spoof-perfect number is a number that would be perfect if some (one or more) of its odd composite factors were wrongly assumed to be prime, i.e., taken as a spoof prime.

%C And if we define a "strong" spoof-perfect number as:

%C A "strong" spoof-perfect number is a spoof-perfect number where sigma(n) does not reveal the compositeness of the odd composite factors of n which are wrongly assumed to be prime, i.e., taken as a spoof prime.

%C The odd composite factors of n which are wrongly assumed to be prime then have to be obtained additively in sigma(n) and not multiplicatively.

%C Then:

%C If 2^n-1 is odd composite but taken as a spoof prime then 2^(n-1)*(2^n - 1) is an even spoof perfect number (and moreover "strong" spoof-perfect).

%C For example:

%C a(8) = 2^(8-1)*(2^8 - 1) = 128*255 = 32640 (where 255 (with factors 3*5*17) is taken as a spoof prime);

%C sigma(a(8)) = (2^8 - 1)*(255 + 1) = 255*256 = 2*(128*255) = 2*32640 = 2n is spoof-perfect (and also "strong" spoof-perfect since 255 is obtained additively);

%C a(11) = 2^(11-1)*(2^11 - 1) = 1024*2047 = 2096128 (where 2047 (with factors 23*89) is taken as a spoof prime);

%C sigma(a(11)) = (2^11 - 1)*(2047 + 1) = 2047*2048 = 2*(1024*2047) = 2*2096128 = 2n is spoof-perfect (and also "strong" spoof-perfect since 2047 is obtained additively).

%C I did a Google search and didn't find anything about the distinction between "strong" versus "weak" spoof-perfect numbers. Maybe some other terminology is used.

%C An example of an even "weak" spoof-perfect number would be:

%C n = 90 = 2*5*9 (where 9 (with factors 3^2) is taken as a spoof prime);

%C sigma(n) = (1+2)*(1+5)*(1+9) = 3*(2*3)*(2*5) = 2*(2*5*(3^2)) = 2*90 = 2n is spoof-perfect (but is not "strong" spoof-perfect since 9 is obtained multiplicatively as 3^2 and is thus revealed composite).

%C Euler proved:

%C If 2^k - 1 is a prime number, then 2^(k-1)*(2^k - 1) is a perfect number and every even perfect number has this form.

%C The following seems to be true (is there a proof?):

%C If 2^k - 1 is an odd composite number taken as a spoof prime, then 2^(k-1)*(2^k - 1) is a "strong" spoof-perfect number and every even "strong" spoof-perfect number has this form?

%C There is only one known odd spoof-perfect number (found by Rene Descartes) but it is a "weak" spoof-perfect number (cf. 'Descartes numbers' and 'Unsolved problems in number theory' links below). (End)

%C a(n+1) = A173787(2*n+1,n); cf. A020522, A059153. - _Reinhard Zumkeller_, Feb 28 2010

%C Also, row sums of triangle A139251. - _Omar E. Pol_, May 25 2010

%C From _Gary W. Adamson_, Oct 26 2010: (Start)

%C Starting with "1" = (1, 1, 2, 4, 8, ...) convolved with A002450: (1, 5, 21, 85, 341, ...); and (1, 3, 7, 15, 31, ...) convolved with A002001: (1, 3, 12, 48, 192, ...). - _Gary W. Adamson_, Oct 26 2010

%C a(n) is also the number of toothpicks in the corner toothpick structure of A153006 after 2^n - 1 stages. - _Omar E. Pol_, Nov 20 2010

%C The number of n-dimensional odd theta functions of half-integral characteristic. (Gunning, p.22) - _Michael Somos_, Jan 03 2014

%C a(n) = A000217((2^n)-1) = 2^(2n-1) - 2^(n-1) is the nearest triangular number below 2^(2n-1); cf. A007582, A233327. - _Antti Karttunen_, Feb 26 2014

%C a(n) is the sum of all the remainders when all the odd numbers < 2^n are divided by each of the powers 2,4,8,...,2^n. - _J. M. Bergot_, May 07 2014

%C Let b(m,k) = number of ways to form a sequence of m selections, without replacement, from a circular array of m labeled cells, such that the first selection of a cell whose adjacent cells have already been selected (a "first connect") occurs on the k-th selection. b(m,k) is defined for m >=3, and for 3 <= k <= m. Then b(m,k)/2m ignores rotations and reflection. Let m=n+2, then a(n) = b(m,m-1))/2m. Reiterated, a(n) is the (m-1)th column of the triangle b(m,k)/2m, whose initial rows are (1), (1 2), (2 6 4), (6 18 28 8), (24 72 128 120 16), (120 360 672 840 496 32), (720 2160 4128 5760 5312 2016 64); see A249796. Note also that b(m,3)/2m = n!, and b(m,m)/2m = 2^n. Proofs are easy. - _Tony Bartoletti_, Oct 30 2014

%C Beginning at a(1) = 1, this sequence is the sum of the first 2^(n-1) numbers of the form 4*k + 1 = A016813(k). For example, a(4) = 120 = 1 + 5 + 9 + 13 + 17 + 21 + 25 + 29. - _J. M. Bergot_, Dec 07 2014

%C a(n) is the number of edges in the (2^n - 1)-dimensional simplex. - _Dimitri Boscainos_, Oct 05 2015

%C a(n) is the number of linear elements in a complete plane graph in 2^n points. - _Dimitri Boscainos_, Oct 05 2015

%C a(n) is the number of linear elements in a complete parallelotope graph in n dimensions. - _Dimitri Boscainos_, Oct 05 2015

%C a(n) is the number of lattices L in Z^n such that the quotient group Z^n / L is C_4. - _Álvar Ibeas_, Nov 26 2015

%C a(n) gives the quadratic coefficient of the polynomial ((x + 1)^(2^n) + (x - 1)^(2^n))/2, cf. A201461. - _Martin Renner_, Jan 14 2017

%C Let f(x)=x+2*sqrt(x) and g(x)=x-2*sqrt(x). Then f(4^n*x)=b(n)*f(x)+a(n)*g(x) and g(4^n*x)=a(n)*f(x)+b(n)*g(x), where b is A007582. - _Luc Rousseau_, Dec 06 2018

%C For n>=1, a(n) is the covering radius of the first order Reed-Muller code RM(1,2n). - _Christof Beierle_, Dec 22 2021

%C a(n) =

%D V. K. Balakrishnan, Theory and problems of Combinatorics, "Schaum's Outline Series", McGraw-Hill, 1995, p. 69.

%D Martin Gardner, Mathematical Carnival, "Pascal's Triangle", p. 201, Alfred A. Knopf NY, 1975.

%D Richard K. Guy, Unsolved problems in number theory, (p 72.) [From _Daniel Forgues_, Nov 10 2009]

%D Ross Honsberger, Mathematical Gems, M.A.A., 1973, p. 113.

%D Clifford A. Pickover, Wonders of Numbers, Chap. 55, Oxford Univ. Press NY 2000.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A006516/b006516.txt">Table of n, a(n) for n=0..200</a>

%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]

%H M. Archibald, A. Blecher, A. Knopfmacher and M. E. Mays, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Archibald/arch3.html">Inversions and Parity in Compositions of Integers</a>, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.

%H William Banks, Ahmet Güloğlu, Wesley Nevans and Filip Saidak, <a href="http://faculty.missouri.edu/~bankswd/papers/2008_Descartes_Final.pdf">Descartes numbers</a>, Anatomy of integers, 167-173, CRM Proc. Lecture Notes, 46, Amer. Math. Soc., Providence, RI, 2008. <a href="http://www.ams.org/mathscinet/pdf/2437973.pdf?arg3=&amp;co4=AND&amp;co5=AND&amp;co6=AND&amp;co7=AND&amp;dr=all&amp;pg4=AUCN&amp;pg5=TI&amp;pg6=PC&amp;pg7=ALLF&amp;pg8=ET&amp;r=1&amp;review_format=html&amp;s4=&amp;s5=descartes%20number&amp;s6=&amp;s7=&amp;s8=All&amp;vfpref=html&amp;yearRangeFirst=&amp;yearRangeSecond=&amp;yrop=eq">MathSciNet review</a> (subscription required).

%H Taylor Brysiewicz, Holger Eble, and Lukas Kühne, <a href="https://arxiv.org/abs/2105.14542">Enumerating chambers of hyperplane arrangements with symmetry</a>, arXiv:2105.14542 [math.CO], 2021.

%H John Elias, <a href="/A006516/a006516.png">Illustration of initial terms: Mersenne-Sierpinski Triangles</a>

%H Farideh Firoozbakht and M. F. Hasler, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Hasler/hasler2.html">Variations on Euclid's formula for Perfect Numbers</a>, JIS 13 (2010) #10.3.1.

%H R. C. Gunning, <a href="http://web.math.princeton.edu/~gunning/theta2/A">Riemann Surfaces and Second-Order Theta Functions, Springer-Verlag, 1976.</a> See page 22.

%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

%H T. Helleseth, T. Klove and J.Mykkeltveit, <a href="https://doi.org/10.1109/TIT.1978.1055928">On the covering radius of binary codes (Corresp.)</a>, IEEE Transactions on Information Theory, Vol. 24 (1978).

%H V. Meally, <a href="/A006516/a006516.pdf">Letter to N. J. A. Sloane, May 1975</a>

%H Axel Muller, Metod Saniga, Alain Giorgetti, Henri de Boutray, and Frédéric Holweck, <a href="https://arxiv.org/abs/2305.10225">New and improved bounds on the contextuality degree of multi-qubit configurations</a>, arXiv:2305.10225 [quant-ph], 2023.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.

%H O. S. Rothaus, <a href="https://doi.org/10.1016/0097-3165(76)90024-8">On "bent" functions</a>, Journal of Combinatorial Theory, Series A, Vol. 20 (1976).

%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>

%H Thomas Wieder, <a href="http://www.math.nthu.edu.tw/~amen/2008/070301.pdf">The number of certain k-combinations of an n-set</a>, Applied Mathematics Electronic Notes, vol. 8 (2008).

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (6,-8).

%F G.f.: x/((1 - 2*x)*(1 - 4*x)).

%F E.g.f. for a(n+1), n>=0: 2*exp(4*x) - exp(2*x).

%F a(n) = 2^(n-1)*StirlingS2(n+1,2), n>=0, with StirlingS2(n,m)=A008277(n,m).

%F Second column of triangle A075497.

%F a(n) = StirlingS2(2^n,2^n-1) = binomial(2^n,2). - _Ross La Haye_, Jan 12 2008

%F a(n+1) = 4*a(n) + 2^n. - _Philippe Deléham_, Feb 20 2004

%F Convolution of 4^n and 2^n. - _Ross La Haye_, Oct 29 2004

%F a(n+1) = Sum_{k=0..n} Sum_{j=0..n} 4^(n-j)*binomial(j,k). - _Paul Barry_, Aug 05 2005

%F a(n+2) = 6*a(n+1) - 8*a(n), a(1) = 1, a(2) = 6. - _Daniele Parisse_, Jul 28 2006 [Typo corrected by _Yosu Yurramendi_, Aug 06 2008]

%F Row sums of triangle A134346. Also, binomial transform of A048473: (1, 5, 17, 53, 161, ...); double bt of A151821: (1, 4, 8, 16, 32, 64, ...) and triple bt of A010684: (1, 3, 1, 3, 1, 3, ...). - _Gary W. Adamson_, Oct 21 2007

%F a(n) = 3*Stirling2(n+1,4) + Stirling2(n+2,3). - _Ross La Haye_, Jun 01 2008

%F a(n) = ((4^n - 2^n)/2 - 2^(n-1))/4, n>=1. - _Zerinvary Lajos_, Jun 05 2009

%F a(n) = A153006(2^n-1). - _Omar E. Pol_, Nov 20 2010

%F Sum_{n>=1} 1/a(n) = 2 * (A065442 - 1) = A211705 - 2. - _Amiram Eldar_, Dec 24 2020

%F a(n) = binomial(2*n+2, n+1) - Catalan(n+2). - _N. J. A. Sloane_, Apr 01 2021

%F a(n) = A171476(n-1), for n >= 1, and a(0) = 0. - _Wolfdieter Lang_, Jul 27 2022

%e G.f. = x + 6*x^2 + 28*x^3 + 120*x^4 + 496*x^5 + 2016*x^6 + 8128*x^7 + 32640*x^8 + ...

%p GBC := proc(n,k,q) local i; mul( (q^(n-i)-1)/(q^(k-i)-1),i=0..k-1); end; # define q-ary Gaussian binomial coefficient [ n,k ]_q

%p [ seq(GBC(n+1,2,2)-GBC(n,2,2), n=0..30) ]; # produces A006516

%p A006516:=1/(4*z-1)/(2*z-1); # _Simon Plouffe_ in his 1992 dissertation

%p seq(binomial(2^n, 2), n=0..19); # _Zerinvary Lajos_, Feb 22 2008

%t Table[2^(n - 1)(2^n - 1), {n, 0, 30}] (* or *) LinearRecurrence[{6, -8}, {0, 1}, 30] (* _Harvey P. Dale_, Jul 15 2011 *)

%o (Sage) [lucas_number1(n,6,8) for n in range(24)] # _Zerinvary Lajos_, Apr 22 2009

%o (Sage) [(4**n - 2**n) / 2 for n in range(24)] # _Zerinvary Lajos_, Jun 05 2009

%o (PARI) a(n)=(1<<n-1)<<(n-1) \\ _Charles R Greathouse IV_, Jun 10 2011

%o (PARI) vector(100, n, n--; 2^(n-1)*(2^n-1)) \\ _Altug Alkan_, Oct 06 2015

%o (Maxima) A006516(n):=2^(n-1)*(2^n - 1)$ makelist(A006516(n),n,0,30); /* _Martin Ettl_, Nov 15 2012 */

%o (Haskell)

%o a006516 n = a006516_list !! n

%o a006516_list = 0 : 1 :

%o zipWith (-) (map (* 6) $ tail a006516_list) (map (* 8) a006516_list)

%o -- _Reinhard Zumkeller_, Oct 25 2013

%o (Magma) [2^(n-1)*(2^n - 1): n in [0..30]]; // _Vincenzo Librandi_, Oct 31 2014

%o (Python) for n in range(0, 30): print(2**(n-1)*(2**n - 1), end=', ') # _Stefano Spezia_, Dec 06 2018

%o (GAP) List([0..25],n->2^(n-1)*(2^n-1)); # _Muniru A Asiru_, Dec 06 2018

%Y Equals A006095(n+1) - A006095(n). In other words, A006095 gives the partial sums.

%Y Cf. A000108, A007582, A010036, A016290, A003462, A079598, A134346, A048473, A151821, A010684.

%Y Cf. A000043, A000396. - _Omar E. Pol_, Aug 30 2008

%Y Cf. A109241, A139251, A153006. - _Omar E. Pol_, Aug 31 2008, May 25 2010, Nov 20 2010

%Y Cf. A002450, A002001. - _Gary W. Adamson_, Oct 26 2010

%Y Cf. A049072, A000384, A201461, A005059 (binomial transform, and special 5-letter words), A065442, A211705.

%Y Cf. A171476.

%K nonn,nice,easy

%O 0,3

%A _N. J. A. Sloane_

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 18 21:02 EDT 2024. Contains 370951 sequences. (Running on oeis4.)