|
%I M1544 #186 Nov 30 2022 07:19:58
%S 0,1,2,5,26,677,458330,210066388901,44127887745906175987802,
%T 1947270476915296449559703445493848930452791205,
%U 3791862310265926082868235028027893277370233152247388584761734150717768254410341175325352026
%N a(n) = a(n-1)^2 + 1 for n >= 1, with a(0) = 0.
%C Number of binary trees of height less than or equal to n. [Corrected by _Orson R. L. Peters_, Jan 03 2020]
%C The rightmost digits cycle (0,1,2,5,6,7,0,1,2,5,6,7,...). - _Jonathan Vos Post_, Jul 21 2005
%C Apart from the initial term, a subsequence of A008318. - _Reinhard Zumkeller_, Jan 17 2008
%C Partial sums of A001699. - _Jonathan Vos Post_, Feb 17 2010
%C Corresponds to the second and second last diagonals of A119687. - _John M. Campbell_, Jul 25 2011
%C This is a divisibility sequence. - _Michael Somos_, Jan 01 2013
%C Sum_{n>=1} 1/a(n) = 1.739940825174794649210636285335916041018367182486941... . - _Vaclav Kotesovec_, Jan 30 2015
%C From _Vladimir Vesic_, Oct 03 2015: (Start)
%C Forming Herbrand's domains of formula: (∃x)(∀y)(∀z)(∃k)(P(x)∨Q(y)∧R(k))
%C where: x->a
%C k->f(y,z)
%C we get:
%C H0 = {a}
%C H1 = {a, f(a,a)}
%C H2 = {a, f(a,a), f(a,f(a,a)), f(f(a,a),a), f(f(a,a),f(a,a))}
%C ...
%C The number of elements in each domain follows this sequence.
%C (End)
%C It is an open question whether or not this sequence satisfies Benford's law [Berger-Hill, 2017] - _N. J. A. Sloane_, Feb 07 2017
%C This is a strong divisibility sequence; see A329429. - _Clark Kimberling_, Nov 13 2019
%C From _Peter Bala_, Oct 31 2022: (Start)
%C Let k be a positive integer. Clearly, the sequence obtained by reducing a(n) modulo k is eventually periodic. Conjectures:
%C 1) The sequence obtained by reducing a(n) modulo 2^k is eventually periodic with period 2.
%C 2) The sequence obtained by reducing a(n) modulo 10^k is eventually periodic with period 6 (the case k = 1 is noted above).
%C 3) The sequence obtained by reducing a(n) modulo 20^k is eventually periodic with period 6.
%C 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)
%D Mordechai Ben-Ari, Mathematical Logic for Computer Science, Third edition, 173-203.
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 443-448.
%D R. K. Guy, How to factor a number, Proc. 5th Manitoba Conf. Numerical Math., Congress. Num. 16 (1975), 49-89.
%D R. Penrose, The Emperor's New Mind, Oxford, 1989, p. 122.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A003095/b003095.txt">Table of n, a(n) for n = 0..13</a>
%H A. V. Aho and N. J. A. Sloane, <a href="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, <a href="http://neilsloane.com/doc/doubly.html">alternative link</a>.
%H A. Berger and T. P. Hill, <a href="http://www.ams.org/publications/journals/notices/201702/rnoti-p132.pdf">What is Benford's Law?</a>, Notices, Amer. Math. Soc., 64:2 (2017), 132-134.
%H Neil J. Calkin, Eunice Y. S. Chan, and Robert M. Corless, <a href="https://ojs.lib.uwo.ca/index.php/maple/article/view/14037">Some Facts and Conjectures about Mandelbrot Polynomials</a>, Maple Transactions (2021) Vol. 1, No. 1, Article 1.
%H P. Flajolet and A. M. Odlyzko, <a href="http://algo.inria.fr/flajolet/Publications/publist.html">Limit distributions</a> of coefficients of iterates of polynomials with applications to combinatorial enumerations, Math. Proc. Camb. Phil. Soc., 96 (1984), 237-253.
%H Claudio Gentile, Fabio Vitale, and Anand Rajagopalan, <a href="https://arxiv.org/abs/1906.09458">Flattening a Hierarchical Clustering through Active Learning</a>, arXiv:1906.09458 [cs.LG], 2019.
%H Spencer Hamblen, Rafe Jones, and Kalyani Madhu, <a href="http://arxiv.org/abs/1303.6513">The density of primes in orbits of z^d + c</a>, arXiv:1303.6513 [math.NT], 2013; to appear, Int. Math. Res. Not., c. 2015.
%H Dimitur Krustev, <a href="http://meta2016.pereslavl.ru/papers/2016_Krustev__Simple_Programs_on_Binary_Trees__Testing_and_Decidable_Equivalence.pdf">Simple Programs on Binary Trees Testing and Decidable Equivalence</a>, 2016.
%H Robin Lamarche-Perrin, <a href="https://arxiv.org/abs/1807.06874">An Information-theoretic Framework for the Lossy Compression of Link Streams</a>, arXiv:1807.06874 [cs.DS], 2018.
%H R. Lamarche-Perrin, Y. Demazeau, and J.-M. Vincent, <a href="http://www.mis.mpg.de/preprints/2014/preprint2014_105.pdf">A Generic Algorithmic Framework to Solve Special Versions of the Set Partitioning Problem</a>, Preprint 105, Max-Planck-Institut fur Mathematik in den Naturwissenschaften, Leipzig, 2014.
%H C. Lenormand, <a href="/A003095/a003095.pdf">Arbres et permutations II</a>, see p. 6.
%H Saad Mneimneh, <a href="http://www.cs.hunter.cuny.edu/~saad/teaching/ToH.pdf">Simple Variations on the Tower of Hanoi to Guide the Study of Recurrences and Proofs by Induction</a>, Department of Computer Science, Hunter College, CUNY, 2019.
%H Michael Penn, <a href="https://www.youtube.com/watch?v=I7DDtwC0iB0">a stylish proof that...</a>, YouTube video, 2021.
%H R. P. Stanley, <a href="/A003277/a003277.pdf">Letter to N. J. A. Sloane, c. 1991</a>
%H M. Tainiter, <a href="https://doi.org/10.1016/S0021-9800(70)80022-9">Algebraic approach to stopping variable problems: Representation theory and applications</a>, J. Combinatorial Theory 9 1970 148-161.
%H P. Tarau, <a href="http://arxiv.org/abs/1507.06944">A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations</a>, arXiv preprint arXiv:1507.06944 [cs.LO], 2015.
%H Stephan Wagner and Volker Ziegler, <a href="https://arxiv.org/abs/2004.09353">Irrationality of growth constants associated with polynomial recursions</a>, arXiv:2004.09353 [math.NT], 2020.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Herbrand_structure">Herbrand Structure</a>
%H Damiano Zanardini, <a href="http://ocw.upm.es/ciencia-de-la-computacion-e-inteligencia-artificial/computational-logic/contenidos/04interpretation.pdf">Computational Logic</a>, UPM European Master in Computational Logic (EMCL) School of Computer Science Technical University of Madrid.
%H <a href="/index/Aa#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 + ...</a>
%H <a href="/index/Di#divseq">Index to divisibility sequences</a>
%H <a href="/index/Be#Benford">Index entries for sequences related to Benford's law</a>
%F 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.
%F a(n) is asymptotic to c^(2^n) where c=1.2259024435287485386279474959130085213... (see A076949). - _Benoit Cloitre_, Nov 27 2002
%F 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
%F a(n) = Sum_{i=1..n} A001699(i). - _Jonathan Vos Post_, Feb 17 2010
%F a(2n) mod 2 = 0 ; a(2n+1) mod 2 = 1. - _Altug Alkan_, Oct 04 2015
%F a(n) + a(n-1) = A213437(n). - _Peter Bala_, Feb 03 2017
%F 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
%F a(n) = A091980(2^(n-1)) for n > 0. - _Alois P. Heinz_, Jul 11 2019
%e G.f. = x + 2*x^2 + 5*x^3 + 26*x^4 + 677*x^5 + 458330*x^6 + 210066388901*x^7 + ...
%e From _Peter Bala_, Oct 31 2022: (Start)
%e n a(6*n+1) mod 10^11
%e 1 10066388901
%e 2 72084948901
%e 3 67988948901
%e 4 61588948901
%e 5 01588948901
%e 6 01588948901
%e 7 01588948901
%e ... ...
%e A318135 begins 1, 0, 9, 8, 4, 9, 8, 8, 5, 1, 0, 2, .... (End)
%p a:= proc(n) option remember; `if`(n=0, 0, a(n-1)^2+1) end:
%p seq(a(n), n=0..10); # _Alois P. Heinz_, Jul 11 2019
%t NestList[#^2+1&,0,10] (* _Harvey P. Dale_, Dec 17 2010 *)
%o (PARI) {a(n) = if( n<1, 0, 1 + a(n-1)^2)}; /* _Michael Somos_, Jan 01 2013 */
%o (Magma)
%o function A003095(n)
%o if n eq 0 then return 0;
%o else return 1 + A003095(n-1)^2;
%o end if; return A003095;
%o end function;
%o [A003095(n): n in [0..12]]; // _G. C. Greubel_, Nov 29 2022
%o (SageMath)
%o def A003095(n): return 0 if (n==0) else 1 + A003095(n-1)^2
%o [A003095(n) for n in range(13)] # _G. C. Greubel_, Nov 29 2022
%Y Cf. A001699, A004019, A038044, A056207, A076949, A077496, A091980, A143848.
%Y Cf. A143849, A213437, A247981, A248218, A248219, A318135, A318136, A318137.
%Y Cf. A318138, A318139, A318140, A355108.
%Y Cf. A137560, which enumerates binary trees of height less than n and exactly j leaf nodes. - _Robert Munafo_, Nov 03 2009
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_ and _Richard Stanley_
%E Additional comments from _Cyril Banderier_, Jun 05 2000
%E Minor edits by _Vaclav Kotesovec_, Oct 04 2014
%E Initial term clarified by _Clark Kimberling_, Nov 13 2019
| 