The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003095 a(n) = a(n-1)^2 + 1 for n >= 1, with a(0) = 0.
(Formerly M1544)
0, 1, 2, 5, 26, 677, 458330, 210066388901, 44127887745906175987802, 1947270476915296449559703445493848930452791205, 3791862310265926082868235028027893277370233152247388584761734150717768254410341175325352026 (list; graph; refs; listen; history; text; internal format)



Number of binary trees of height less than or equal to n. [Corrected by Orson R. L. Peters, Jan 03 2020]

The rightmost digits cycle (0,1,2,5,6,7,0,1,2,5,6,7,...). a(n) is prime for n = 2, 3, 5, ... a(n) is semiprime for n = 4, ... - Jonathan Vos Post, Jul 21 2005

Apart from the initial term, a subsequence of A008318. - Reinhard Zumkeller, Jan 17 2008

Partial sums of A001699. - Jonathan Vos Post, Feb 17 2010

Corresponds to the second and second last diagonals of A119687. - John M. Campbell, Jul 25 2011

This is a divisibility sequence. - Michael Somos, Jan 01 2013

Sum_{n>=1} 1/a(n) = 1.739940825174794649210636285335916041018367182486941... . - Vaclav Kotesovec, Jan 30 2015

From Vladimir Vesic, Oct 03 2015: (Start)

Forming Herbrand's domains of formula: (∃x)(∀y)(∀z)(∃k)(P(x)∨Q(y)∧R(k))

where: x->a


we get:


H1={a, f(a,a)}

H2={a, f(a,a), f(a,f(a,a)), f(f(a,a),a), f(f(a,a),f(a,a))}


The number of elements in each domain follows this sequence.


It is an open question whether or not this sequence satisfies Benford's law [Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017

This is a strong divisibility sequence; see A329429. - Clark Kimberling, Nov 13 2019


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

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 443-448.

R. K. Guy, How to factor a number, Proc. 5th Manitoba Conf. Numerical Math., Congress. Num. 16 (1975), 49-89.

R. Penrose, The Emperor's New Mind, Oxford, 1989, p. 122

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


Alois P. Heinz, Table of n, a(n) for n = 0..13

A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fib. Quart., 11 (1973), 429-437.

A. Berger and T. P. Hill, What is Benford's Law?, Notices, Amer. Math. Soc., 64:2 (2017), 132-134.

P. Flajolet and A. M. Odlyzko, Limit distributions of coefficients of iterates of polynomials with applications to combinatorial enumerations, Math. Proc. Camb. Phil. Soc., 96 (1984), 237-253.

Claudio Gentile, Fabio Vitale, Anand Rajagopalan, Flattening a Hierarchical Clustering through Active Learning, arXiv:1906.09458 [cs.LG], 2019.

Spencer Hamblen, Rafe Jones, and Kalyani Madhu, The density of primes in orbits of z^d + c, arXiv:1303.6513 [math.NT], 2013; to appear, Int. Math. Res. Not., c. 2015.

Dimitur Krustev, Simple Programs on Binary Trees Testing and Decidable Equivalence, 2016.

Robin Lamarche-Perrin, An Information-theoretic Framework for the Lossy Compression of Link Streams, arXiv:1807.06874 [cs.DS], 2018.

R. Lamarche-Perrin, Y. Demazeau, J.-M. Vincent, A Generic Algorithmic Framework to Solve Special Versions of the Set Partitioning Problem, Preprint 105, Max-Planck-Institut fur Mathematik in den Naturwissenschaften, Leipzig, 2014.

C. Lenormand, Arbres et permutations II, see p. 6.

Saad Mneimneh, Simple Variations on the Tower of Hanoi to Guide the Study of Recurrences and Proofs by Induction, Department of Computer Science, Hunter College, CUNY, 2019.

R. P. Stanley, Letter to N. J. A. Sloane, c. 1991

M. Tainiter, Algebraic approach to stopping variable problems: Representation theory and applications, J. Combinatorial Theory 9 1970 148-161.

P. Tarau, A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations, arXiv preprint arXiv:1507.06944 [cs.LO], 2015.

Stephan Wagner, Volker Ziegler, Irrationality of growth constants associated with polynomial recursions, arXiv:2004.09353 [math.NT], 2020.

Wikipedia, Herbrand Structure

Damiano Zanardini, Computational Logic, UPM European Master in Computational Logic (EMCL) School of Computer Science Technical University of Madrid.

Index entries for sequences of form a(n+1)=a(n)^2 + ...

Index to divisibility sequences

Index entries for sequences related to Benford's law


a_n=B_{n-1}(1) where B_n(x)=1+xB_{n-1}(x)^2 is the generating function of trees of height <= n.

a(n) is asymptotic to c^(2^n) where c=1.2259024435287485386279474959130085213... (see A076949). - Benoit Cloitre, Nov 27 2002

c = b^(1/4) where b is the constant in Bottomley's formula in A004019. a(n) appears very asymptotic to c^(2^n) - Sum_{k>=1} A088674(k)/(2*c^(2^n))^(2*k-1). - Gerald McGarvey, Nov 17 2007

a(n) = Sum_{i=1..n} A001699(i). - Jonathan Vos Post, Feb 17 2010

a(2n) mod 2 = 0 ; a(2n+1) mod 2 = 1. - Altug Alkan, Oct 04 2015

a(n) + a(n-1) = A213437(n). - Peter Bala, Feb 03 2017

0 = a(n)^2*(+a(n+1) + a(n+2)) + a(n+1)^2*(-a(n+1) - a(n+2) - a(n+3)) + a(n+2)^3 for all n>=0. - Michael Somos, Feb 10 2017

a(n) = A091980(2^(n-1)) for n > 0. - Alois P. Heinz, Jul 11 2019


G.f. = x + 2*x^2 + 5*x^3 + 26*x^4 + 677*x^5 + 458330*x^6 + 210066388901*x^7 + ...


a:= proc(n) option remember; `if`(n=0, 0, a(n-1)^2+1) end:

seq(a(n), n=0..10);  # Alois P. Heinz, Jul 11 2019


NestList[#^2+1&, 0, 10] (* Harvey P. Dale, Dec 17 2010 *)


(PARI) {a(n) = if( n<1, 0, 1 + a(n-1)^2)}; /* Michael Somos, Jan 01 2013 */


Cf. A038044, A001699, A056207, A004019, A143848, A143849.

Cf. A137560, which enumerates binary trees of height less than n and exactly j leaf nodes. - Robert Munafo, Nov 03 2009

Cf. A076949, A077496.

Cf. A247981, A248218, A248219, A213437.

Cf. A091980.

Sequence in context: A322705 A167007 A064006 * A023362 A138613 A299104

Adjacent sequences:  A003092 A003093 A003094 * A003096 A003097 A003098




N. J. A. Sloane and Richard Stanley


Additional comments from Cyril Banderier, Jun 05 2000

Minor edits by Vaclav Kotesovec, Oct 04 2014

Initial term clarified by Clark Kimberling, Nov 13 2019



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 24 01:49 EST 2020. Contains 338603 sequences. (Running on oeis4.)