A002065 - OEIS

%I M2961 N1197 #110 Jan 09 2025 08:25:11

%S 0,1,3,13,183,33673,1133904603,1285739649838492213,

%T 1653126447166808570252515315100129583,

%U 2732827050322355127169206170438813672515557678636778921646668538491883473

%N a(n+1) = a(n)^2 + a(n) + 1.

%C 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

%C 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

%D Mordechai Ben-Ari, Mathematical Logic for Computer Science, Third edition, 173-203.

%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 433-434.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H John Cerkan, <a href="/A002065/b002065.txt">Table of n, a(n) for n = 0..12</a>

%H A. V. Aho and N. J. A. Sloane, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/11-4/aho-a.pdf">Some doubly exponential sequences</a>, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.

%H A. V. Aho and N. J. A. Sloane, <a href="/A000058/a000058.pdf">Some doubly exponential sequences</a>, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)

%H Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/lehmer/lehmer.html">Lehmer's Constant</a> [Broken link]

%H Steven R. Finch, <a href="http://web.archive.org/web/20010603070928/http://www.mathsoft.com/asolve/constant/lehmer/lehmer.html">Lehmer's Constant</a> [From the Wayback machine]

%H Stan C. Kalman and Barry L. Kwasny, <a href="https://doi.org/10.1080/09540099508915657">Tail-recursive distributed representations and simple recurrent networks</a>, Connection Science, 7 (1995), 61-80.

%H D. H. Lehmer, <a href="http://projecteuclid.org/euclid.dmj/1077490638">A cotangent analogue of continued fractions</a>, Duke Math. J., 4 (1935), 323-340.

%H D. H. Lehmer, <a href="/A002065/a002065_1.pdf">A cotangent analogue of continued fractions</a>, Duke Math. J., 4 (1935), 323-340. [Annotated scanned copy]

%H H. P. Robinson, <a href="/A002065/a002065.pdf">Letter to N. J. A. Sloane, Jul 12 1971</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LehmersConstant.html">Lehmer's Constant</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LehmerCotangentExpansion.html">Lehmer Cotangent Expansion</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Herbrand_structure">Herbrand Structure</a>

%H J. W. Wrench, Jr., <a href="/A002065/a002065_2.pdf">Letters to N. J. A. Sloane, Feb 1974</a>

%H <a href="/index/Aa#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 + ...</a>

%F a(n) = floor(c^(2^n)) for n > 0, where c = 1.385089248334672909882206535871311526236739234374149506334120193387331772... - _Benoit Cloitre_, Nov 29 2002

%F a(n) = (A232806(n) - 1)/2 = (A232806(n-1)^2 + 3)/4. - _Peter Bala_, Mar 28 2018

%t f[x_] := 1 + x + x^2 ; NestList[f, 1, 7] (* _Geoffrey Critzer_, May 04 2010 *)

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

%o (Magma) [n le 1 select 0 else Self(n-1)^2 + Self(n-1) + 1: n in [1..15]]; // _Vincenzo Librandi_, Oct 05 2015

%o (Maxima) a(n) := if n = 0 then 1 else a(n-1)^2+a(n-1)+1 $

%o makelist(a(n),n,0,8); /* _Emanuele Munarini_, Mar 23 2017 */

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

%K easy,nice,nonn

%O 0,3

%A _N. J. A. Sloane_