

A006127


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


52



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) 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



FORMULA



EXAMPLE

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 triple: 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) triples; (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



MATHEMATICA

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))
(Python)


CROSSREFS



KEYWORD

nonn,easy


AUTHOR



STATUS

approved



