

A006127


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


42



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

For numbers m=n+2^n such that equation x=2^(mx) 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) = nth 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
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 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, VertexInduced Subgraph


FORMULA

Row sums of triangle A135227.  Gary W. Adamson, Nov 23 2007
Partial sums of A094373. G.f.: (1xx^2)/((1x)^2(12x)).  Paul Barry, Aug 05 2004
Binomial transform of [1,2,1,1,1,1,1,...].  Franklin T. AdamsWatters, Nov 29 2006
a(n) = 2*a(n1)  n + 2 (with a(0)=1).  Vincenzo Librandi, Dec 30 2010


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 PA, the subtrees are: 2 singles: P, A; 1 pair: PA; 2+1 = 3 subtrees in total.
a(2) = 6. When n=2, the tree is PA PB, the subtrees are: 3 singles: P, A, B; 2 pairs: PA, PB; 1 triplet: APB (the whole tree); 3+2+1 = 6.
a(3) = 11. For n=3 leaf nodes, the tree is PA PB PC, the subtrees are: 4 singles: P, A, B, C; 3 pairs: PA, PB, PC; 3 triples: APB, APC, BPC; 1 quad: PA PB PC (the whole tree); 4+3+3+1 = 11 in total.
a(4) = 20. For n=4 leaves, the tree is PA PB PC PD, the subtrees are: 5 singles: P, A, B, C, D; 4 pairs: PA, PB, PC, PD; 6 triples: APB, APC, BPC, APD, BPD, CPD; 4 quads: PA PB PC, PA PB PD, PA PC PD, PB PC PD; 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) triplets; (n, 3) quads; ... ; (n, n1) subtrees having (n1) 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, n1) + 1 = (n + (n, 0)) + (n, 1) + (n, 2) + (n, 3) + ... + (n, n1) + (n, n) = n + (sum of all binomial coefficients of size n) = n + (2^n). (End)


MAPLE

A006127:=(1+z+z**2)/(2*z1)/(z1)**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 *)


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


CROSSREFS

Cf. A135227, A000079, A052944; A000051 (first differences).
Cf. A000325.
Sequence in context: A265077 A094989 A052467 * A122106 A007707 A018174
Adjacent sequences: A006124 A006125 A006126 * A006128 A006129 A006130


KEYWORD

nonn,easy,changed


AUTHOR

N. J. A. Sloane


STATUS

approved



