A002065 a(n+1) = a(n)^2 + a(n) + 1.

0, 1, 3, 13, 183, 33673, 1133904603, 1285739649838492213, 1653126447166808570252515315100129583, 2732827050322355127169206170438813672515557678636778921646668538491883473

Offset: 0

Author

N. J. A. Sloane

Keywords

• easy
• nice
• nonn

Comments

a(n) is the number of trees of height <= n, generated by unary and binary composition: S = x + (S) + (S,S) = x + (x) + (x,x) + (x,(x)) + ((x),x) + ((x)) + ((x),(x)) + (x,(x,x)) + ((x,x),x) + ((x),(x,x)) + ((x,x),(x)) + ((x,x)) + ((x,x),(x,x)) + ... (x is of height 1); the first difference sequence (beginning with 1), 1 2 10 170 33490 1133870930..., gives the number h(n) of these trees whose height is n, h(n + 1) = h(n) + h(n)*h(n) + 2h(n)*a(n-1), h(1) = 1; as h(n + 1)/h(n) = 1 + a(n) + a(n-1) gives sequence 1, 2, 10 (2*5), 170 (2*5*17), 33490 (2*5*17*197), 1133870930 (2*5*17*197*33877), ... - Claude Lenormand (claude.lenormand(AT)free.fr), Sep 05 2001

This is a divisibility sequence, that is, if n divides m, then a(n) divides a(m). This is a particular case of the result: if p(x) is an integral polynomial then the sequence of n-th iterates p^n(x) (:= p(p^(n-1)(x)) with p^1(x) := p(x)), n = 1,2,..., of p(x) evaluated at x = 0 is a divisibility sequence. In this case p(x) = 1 + x + x^2. - Peter Bala, Mar 28 2018

References

• Mordechai Ben-Ari, Mathematical Logic for Computer Science, Third edition, 173-203.
• Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 433-434.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• John Cerkan, Table of n, a(n) for n = 0..12
• A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.
• A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
• Steven R. Finch, Lehmer's Constant [Broken link]
• Steven R. Finch, Lehmer's Constant [From the Wayback machine]
• Stan C. Kalman and Barry L. Kwasny, Tail-recursive distributed representations and simple recurrent networks, Connection Science, 7 (1995), 61-80.
• D. H. Lehmer, A cotangent analogue of continued fractions, Duke Math. J., 4 (1935), 323-340.
• D. H. Lehmer, A cotangent analogue of continued fractions, Duke Math. J., 4 (1935), 323-340. [Annotated scanned copy]
• H. P. Robinson, Letter to N. J. A. Sloane, Jul 12 1971
• Eric Weisstein's World of Mathematics, Lehmer's Constant
• Eric Weisstein's World of Mathematics, Lehmer Cotangent Expansion
• Wikipedia, Herbrand Structure
• J. W. Wrench, Jr., Letters to N. J. A. Sloane, Feb 1974
• Index entries for sequences of form a(n+1)=a(n)^2 + ...

Crossrefs

Cf. A002665, A002794, A002795, A030125, A063573, A232806.

Programs

Magma

[n le 1 select 0 else Self(n-1)^2 + Self(n-1) + 1: n in [1..15]]; // Vincenzo Librandi, Oct 05 2015

Mathematica

f[x_] := 1 + x + x^2 ; NestList[f, 1, 7] (* Geoffrey Critzer, May 04 2010 *)

Maxima

a(n) := if n = 0 then 1 else a(n-1)^2+a(n-1)+1 $
makelist(a(n),n,0,8); /* Emanuele Munarini, Mar 23 2017 */

PARI

a(n)=if(n<1,0,a(n-1)^2+a(n-1)+1)

Formula

a(n) = floor(c^(2^n)) for n > 0, where c = 1.385089248334672909882206535871311526236739234374149506334120193387331772... - Benoit Cloitre, Nov 29 2002

a(n) = (A232806(n) - 1)/2 = (A232806(n-1)^2 + 3)/4. - Peter Bala, Mar 28 2018