A006127 a(n) = 2^n + n. (Formerly M2547)

1, 3, 6, 11, 20, 37, 70, 135, 264, 521, 1034, 2059, 4108, 8205, 16398, 32783, 65552, 131089, 262162, 524307, 1048596, 2097173, 4194326, 8388631, 16777240, 33554457, 67108890, 134217755, 268435484, 536870941, 1073741854, 2147483679, 4294967328, 8589934625

Offset

0,2

Comments

For numbers m=n+2^n such that equation x=2^(m-x) has solution x=2^n, see A103354. - Zak Seidov, Mar 23 2005

Primes of the form x^x+1 must be of the form 2^2^(a(n))+1, that is, Fermat number F_(a(n)) (Sierpiński 1958). - David W. Wilson, May 08 2005

a(n) = n-th Mersenne number + n + 1 = A000225(n) + n + 1. Partial sums of a(n) are A132925(n+1). - Jaroslav Krizek, Oct 16 2009

Intersection of A188916 and A188917: A188915(a(n)) = (2^n)^2 = 2^(2*n) = A000302(n). - Reinhard Zumkeller, Apr 14 2011

a(n) is also the number of all connected subtrees of a star tree, having n leaves. The star tree is a tree, where all n leaves are connected to one parent P. - Viktar Karatchenia, Feb 29 2016

References

John H. Conway, R. K. Guy, The Book of Numbers, Copernicus Press, p. 84.

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

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..100

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 435

C. L. Mallows & N. J. A. Sloane, Emails, May 1991

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

Eric Weisstein's World of Mathematics, Sierpiński Number of the First Kind

Eric Weisstein's World of Mathematics, Star Graph

Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Formula

Row sums of triangle A135227. - Gary W. Adamson, Nov 23 2007

Partial sums of A094373. G.f.: (1-x-x^2)/((1-x)^2(1-2x)). - Paul Barry, Aug 05 2004

Binomial transform of [1,2,1,1,1,1,1,...]. - Franklin T. Adams-Watters, Nov 29 2006

a(n) = 2*a(n-1) - n + 2 (with a(0)=1). - Vincenzo Librandi, Dec 30 2010

E.g.f.: exp(x)*(exp(x) + x). - Stefano Spezia, Dec 10 2021

Example

From Viktar Karatchenia, Feb 29 2016: (Start)
a(0) = 1. There are n=0 leaves, it is a trivial tree consisting of a single parent node P.
a(1) = 3. There is n=1 leaf, the tree is P-A, the subtrees are: 2 singles: P, A; 1 pair: P-A; 2+1 = 3 subtrees in total.
a(2) = 6. When n=2, the tree is P-A P-B, the subtrees are: 3 singles: P, A, B; 2 pairs: P-A, P-B; 1 triple: A-P-B (the whole tree); 3+2+1 = 6.
a(3) = 11. For n=3 leaf nodes, the tree is P-A P-B P-C, the subtrees are: 4 singles: P, A, B, C; 3 pairs: P-A, P-B, P-C; 3 triples: A-P-B, A-P-C, B-P-C; 1 quad: P-A P-B P-C (the whole tree); 4+3+3+1 = 11 in total.
a(4) = 20. For n=4 leaves, the tree is P-A P-B P-C P-D, the subtrees are: 5 singles: P, A, B, C, D; 4 pairs: P-A, P-B, P-C, P-D; 6 triples: A-P-B, A-P-C, B-P-C, A-P-D, B-P-D, C-P-D; 4 quads: P-A P-B P-C, P-A P-B P-D, P-A P-C P-D, P-B P-C P-D; the whole tree counts as 1; 5+4+6+4+1 = 20.
In general, for n leaves, connected to the parent node P, there will be: (n+1) singles; (n, 1) pairs; (n, 2) triples; (n, 3) quads; ... ; (n, n-1) subtrees having (n-1) edges; 1 whole tree, having all n edges. Thus, the total number of all distinct subtrees is: (n+1) + (n, 1) + (n, 2) + (n, 3) + ... + (n, n-1) + 1 = (n + (n, 0)) + (n, 1) + (n, 2) + (n, 3) + ... + (n, n-1) + (n, n) = n + (sum of all binomial coefficients of size n) = n + (2^n). (End)

Maple

A006127:=(-1+z+z**2)/(2*z-1)/(z-1)**2; # conjectured by Simon Plouffe in his 1992 dissertation

Mathematica

Table[2^n + n, {n, 0, 50}] (* Vladimir Joseph Stephan Orlovsky, May 19 2011 *)
Table[BitXOr(i, 2^i), {i, 1, 100}] (* Peter Luschny, Jun 01 2011 *)
LinearRecurrence[{4, -5, 2}, {1, 3, 6}, 40] (* Harvey P. Dale, Feb 08 2023 *)

Prog

(Haskell)
a006127 n = a000079 n + n
a006127_list = s [1] where
   s xs = last xs : (s $ zipWith (+) [1..] (xs ++ reverse xs))
Reinhard Zumkeller, May 19 2015, Feb 05 2011
(PARI) a(n)=1<<n+n \\ Charles R Greathouse IV, Jul 19 2011
(Python) print([2**n + n for n in range(34)]) # Karl V. Keller, Jr., Aug 18 2020
(Python)
def A006127(n): return (1<<n)+n # Chai Wah Wu, Jan 11 2023

Crossrefs

Cf. A135227, A000079, A052944; A000051 (first differences).

Cf. A000325.

Sequence in context: A265077 A094989 A052467 * A122106 A007707 A298798

Adjacent sequences: A006124 A006125 A006126 * A006128 A006129 A006130

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved