login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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^(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

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

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

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 triplet: 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) triplets; (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 *)

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

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 22 19:31 EDT 2017. Contains 286885 sequences.