|
|
A003095
|
|
a(n) = a(n-1)^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 [Berger-Hill, 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 10-adic 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 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).
|
|
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), 237-253.
Damiano Zanardini, Computational Logic, UPM European Master in Computational Logic (EMCL) School of Computer Science Technical University of Madrid.
|
|
FORMULA
|
a(n) = B_{n-1}(1) where B_n(x) = 1 + x*B_{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(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(n-1)^2+1) end:
|
|
MATHEMATICA
|
|
|
PROG
|
(PARI) {a(n) = if( n<1, 0, 1 + a(n-1)^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
|
|
|
|