

A003095


a(n) = a(n1)^2 + 1 for n >= 1, with a(0) = 0.
(Formerly M1544)


62



0, 1, 2, 5, 26, 677, 458330, 210066388901, 44127887745906175987802, 1947270476915296449559703445493848930452791205, 3791862310265926082868235028027893277370233152247388584761734150717768254410341175325352026
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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,...).  Jonathan Vos Post, Jul 21 2005
Sum_{n>=1} 1/a(n) = 1.739940825174794649210636285335916041018367182486941... .  Vaclav Kotesovec, Jan 30 2015
Forming Herbrand's domains of formula: (∃x)(∀y)(∀z)(∃k)(P(x)∨Q(y)∧R(k))
where: x>a
k>f(y,z)
we get:
H0 = {a}
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.
(End)
It is an open question whether or not this sequence satisfies Benford's law [BergerHill, 2017]  N. J. A. Sloane, Feb 07 2017
Let k be a positive integer. Clearly, the sequence obtained by reducing a(n) modulo k is eventually periodic. Conjectures:
1) The sequence obtained by reducing a(n) modulo 2^k is eventually periodic with period 2.
2) The sequence obtained by reducing a(n) modulo 10^k is eventually periodic with period 6 (the case k = 1 is noted above).
3) The sequence obtained by reducing a(n) modulo 20^k is eventually periodic with period 6.
4) For n >= floor(k/2) and for 1 <= i <= 6, the value of a(6*n+i) mod 10^k is a constant independent of n. The digits of these 6 constant integers, when read from right to left, are the first k digits of the 10adic numbers A318135 (i = 1), A318136 (i = 2), A318137 (i = 3), A318138 (i = 4), A318139 (i = 5) and A318140 (i = 6), respectively. An example is given below. (End)


REFERENCES

Mordechai BenAri, Mathematical Logic for Computer Science, Third edition, 173203.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 443448.
R. K. Guy, How to factor a number, Proc. 5th Manitoba Conf. Numerical Math., Congress. Num. 16 (1975), 4989.
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).


LINKS

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), 237253.
Damiano Zanardini, Computational Logic, UPM European Master in Computational Logic (EMCL) School of Computer Science Technical University of Madrid.


FORMULA

a(n) = B_{n1}(1) where B_n(x) = 1 + x*B_{n1}(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*k1).  Gerald McGarvey, Nov 17 2007
a(2n) mod 2 = 0 ; a(2n+1) mod 2 = 1.  Altug Alkan, Oct 04 2015
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


EXAMPLE

G.f. = x + 2*x^2 + 5*x^3 + 26*x^4 + 677*x^5 + 458330*x^6 + 210066388901*x^7 + ...
n a(6*n+1) mod 10^11
1 10066388901
2 72084948901
3 67988948901
4 61588948901
5 01588948901
6 01588948901
7 01588948901
... ...
A318135 begins 1, 0, 9, 8, 4, 9, 8, 8, 5, 1, 0, 2, .... (End)


MAPLE

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


MATHEMATICA



PROG

(PARI) {a(n) = if( n<1, 0, 1 + a(n1)^2)}; /* Michael Somos, Jan 01 2013 */
(Magma)
if n eq 0 then return 0;
end function;
(SageMath)


CROSSREFS

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


KEYWORD

nonn,easy,nice


AUTHOR



EXTENSIONS



STATUS

approved



