cp's OEIS Frontend

A007018 a(n) = a(n-1)^2 + a(n-1), a(0)=1.

%I A007018 M1713 #229 Mar 01 2025 03:19:02
%S A007018 1,2,6,42,1806,3263442,10650056950806,113423713055421844361000442,
%T A007018 12864938683278671740537145998360961546653259485195806
%N A007018 a(n) = a(n-1)^2 + a(n-1), a(0)=1.
%C A007018 Number of ordered trees having nodes of outdegree 0,1,2 and such that all leaves are at level n. Example: a(2)=6 because, denoting by I a path of length 2 and by Y a Y-shaped tree with 3 edges, we have I, Y, I*I, I*Y, Y*I, Y*Y, where * denotes identification of the roots. - _Emeric Deutsch_, Oct 31 2002
%C A007018 Equivalently, the number of acyclic digraphs (dags) that unravel to a perfect binary tree of height n. - _Nachum Dershowitz_, Jul 03 2022
%C A007018 a(n) has at least n different prime factors. [Saidak]
%C A007018 Subsequence of squarefree numbers (A005117). - _Reinhard Zumkeller_, Nov 15 2004 [This has been questioned, see MathOverflow link. - _Charles R Greathouse IV_, Mar 30 2015]
%C A007018 For prime factors see A007996.
%C A007018 Curtiss shows that if the reciprocal sum of the multiset S = {x_1, x_2, ..., x_n} is 1, then max(S) <= a(n). - _Charles R Greathouse IV_, Feb 28 2007
%C A007018 The number of reduced ZBDDs for Boolean functions of n variables in which there is no zero sink. (ZBDDs are "zero-suppressed binary decision diagrams.") For example, a(2)=6 because of the 2-variable functions whose truth tables are 1000, 1010, 1011, 1100, 1110, 1111. - _Don Knuth_, Jun 04 2007
%C A007018 Using the methods of Aho and Sloane, Fibonacci Quarterly 11 (1973), 429-437, it is easy to show that a(n) is the integer just a tiny bit below the real number theta^{2^n}-1/2, where theta =~ 1.597910218 is the exponential of the rapidly convergent series Sum_{n>=0} log(1+1/a_n)/2^{n+1}. For example, theta^32 - 1/2 =~ 3263442.0000000383. - _Don Knuth_, Jun 04 2007 [Corrected by _Darryl K. Nester_, Jun 19 2017]
%C A007018 The next term has 209 digits. - _Harvey P. Dale_, Sep 07 2011
%C A007018 Urquhart shows that a(n) is the minimum size of a tableau refutation of the clauses of the complete binary tree of depth n, see pp. 432-434. - _Charles R Greathouse IV_, Jan 04 2013
%C A007018 For any positive a(0), the sequence a(n) = a(n-1) * (a(n-1) + 1) gives a constructive proof that there exists integers with at least n distinct prime factors, e.g. a(n). As a corollary, this gives a constructive proof of Euclid's theorem stating that there are an infinity of primes. - _Daniel Forgues_, Mar 03 2017
%C A007018 Lower bound for A100016 (with equality for the first 5 terms), where a(n)+1 is replaced by nextprime(a(n)). - _M. F. Hasler_, May 20 2019
%D A007018 R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 94.
%D A007018 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007018 N. J. A. Sloane, <a href="/A007018/b007018.txt">Table of n, a(n) for n = 0..12</a>
%H A007018 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 A007018 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 A007018 David Adjiashvili, Sandro Bosio and Robert Weismantel, <a href="https://www.semanticscholar.org/paper/Dynamic-Combinatorial-Optimization-%3A-a-complexity-Adjiashvili/547cd465f1ca3d8e6f617b429f6f74a8bf65752a">Dynamic Combinatorial Optimization: a complexity and approximability study</a>, 2012.
%H A007018 Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Jean-Marie Lagniez, and Pierre Marquis, <a href="https://arxiv.org/abs/2108.05266">On the Explanatory Power of Decision Trees</a>, arXiv:2108.05266 [cs.AI], 2021.
%H A007018 Arvind Ayyer, Anne Schilling, Benjamin Steinberg and Nicolas M. Thiéry, <a href="https://doi.org/10.1142/S0218196715400081">Markov chains, R-trivial monoids and representation theory</a>, Int. J. Algebra Comput., Vol. 25 (2015), pp. 169-231, <a href="http://arxiv.org/abs/1401.4250">arXiv preprint</a>, arXiv:1401.4250 [math.CO], 2014.
%H A007018 Umberto Cerruti, <a href="/A146564/a146564.pdf">Percorsi tra i numeri</a> (in Italian), page 5.
%H A007018 A. Yu. Chirkov, D. V. Gribanov and N. Yu. Zolotykh, <a href="https://arxiv.org/abs/2004.08589">On the Proximity of the Optimal Values of the Multi-Dimensional Knapsack Problem with and without the Cardinality Constraint</a>, arXiv:2004.08589 [math.OC], 2020.
%H A007018 D. R. Curtiss, <a href="http://www.jstor.org/stable/2299023">On Kellogg's Diophantine problem</a>, Amer. Math. Monthly, Vol. 29, No. 10 (1922), pp. 380-387.
%H A007018 Christian Elsholtz and Stefan Planitzer, <a href="https://arxiv.org/abs/2012.05984">Sums of four and more unit fractions and approximate parametrizations</a>, arXiv:2012.05984 [math.NT], 2020.
%H A007018 Steven Finch, <a href="https://arxiv.org/abs/2411.16062">Exercises in Iterational Asymptotics</a>, arXiv:2411.16062 [math.NT], 2024. See p. 9.
%H A007018 Samuele Giraudo, <a href="https://arxiv.org/abs/2204.03586">The combinator M and the Mockingbird lattice</a>, arXiv:2204.03586 [math.CO], 2022.
%H A007018 Murray S. Klamkin, ed., <a href="http://dx.doi.org/10.1137/1.9781611971729">Problems in Applied Mathematics: Selections from SIAM Review</a>, SIAM, 1990; see p. 577.
%H A007018 Diana Maimuţ and George Teşeleanu, <a href="https://eprint.iacr.org/2023/844.pdf">Inferring Bivariate Polynomials for Homomorphic Encryption Application</a>, Cryptology ePrint Archive (2023) Art. 844. See p. 16.
%H A007018 MathOverflow, <a href="http://mathoverflow.net/questions/118050/is-oeis-a007018-really-a-subsequence-of-squarefree-numbers?rq=1">Is OEIS A007018 really a subsequence of squarefree numbers?</a>.
%H A007018 Marko R. Riedel, <a href="http://math.stackexchange.com/questions/1285304/">Two-colorings of unordered full binary trees on n levels</a>.
%H A007018 Matthew Roughan, <a href="https://arxiv.org/abs/1810.10373">Surreal Birthdays and Their Arithmetic</a>, arXiv:1810.10373 [math.HO], 2018.
%H A007018 Filip Saidak, <a href="http://www.jstor.org/stable/27642094">A New Proof of Euclid's Theorem</a>, Amer. Math. Monthly, Vol. 113, No. 10 (Dec., 2006), pp. 937-938.
%H A007018 N. J. A. Sloane, <a href="https://www.youtube.com/watch?v=3RAYoaKMckM">A Nasty Surprise in a Sequence and Other OEIS Stories</a>, Experimental Mathematics Seminar, Rutgers University, Oct 10 2024, Youtube video; <a href="https://sites.math.rutgers.edu/~zeilberg/expmath/sloane85BD.pdf">Slides</a> [Mentions this sequence]
%H A007018 Bertrand Teguia Tabuguia, <a href="https://arxiv.org/abs/2412.20630">Computing with D-Algebraic Sequences</a>, arXiv:2412.20630 [math.AG], 2024. See p. 9.
%H A007018 Alasdair Urquhart, <a href="https://doi.org/10.2307/421131">The complexity of propositional proofs</a>, Bull. Symbolic Logic, Vol. 1, No. 4 (1995) pp. 425-467, esp. p. 434.
%H A007018 Zalman Usiskin, <a href="/A007018/a007018.pdf">Letter to N. J. A. Sloane, Oct. 1991</a>.
%H A007018 <a href="/index/Aa#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 + ...</a>.
%F A007018 a(n) = A000058(n)-1 = A000058(n-1)^2 - A000058(n-1) = 1/(1-Sum_{j<n} 1/A000058(j)) where A000058 is Sylvester's sequence. - _Henry Bottomley_, Jul 23 2001
%F A007018 a(n) = floor(c^(2^n)) where c = A077125 = 1.597910218031873178338070118157... - _Benoit Cloitre_, Nov 06 2002
%F A007018 a(1)=1, a(n) = Product_{k=1..n-1} (a(k)+1). - _Benoit Cloitre_, Sep 13 2003
%F A007018 a(n) = A139145(2^(n+1) - 1). - _Reinhard Zumkeller_, Apr 10 2008
%F A007018 If an (additional) initial 1 is inserted, a(n) = Sum_{k<n} a(k)^2. - _Franklin T. Adams-Watters_, Jun 11 2009
%F A007018 a(n+1) = a(n)-th oblong (or promic, pronic, or heteromecic) numbers (A002378). a(n+1) = A002378(a(n)) = A002378(a(n-1)) * (A002378(a(n-1)) + 1). - _Jaroslav Krizek_, Sep 13 2009
%F A007018 a(n) = A053631(n)/2. - _Martin Ettl_, Nov 08 2012
%F A007018 Sum_{n>=0} (-1)^n/a(n) = A118227. - _Amiram Eldar_, Oct 29 2020
%F A007018 Sum_{n>=0} 1/a(n) = A371321. - _Amiram Eldar_, Mar 19 2024
%p A007018 A007018 := proc(n)
%p A007018     option remember;
%p A007018     local aprev;
%p A007018     if n = 0 then
%p A007018         1;
%p A007018     else
%p A007018         aprev := procname(n-1) ;
%p A007018         aprev*(aprev+1) ;
%p A007018     end if;
%p A007018 end proc: # _R. J. Mathar_, May 06 2016
%t A007018 FoldList[#^2 + #1 &, 1, Range@ 8] (* _Robert G. Wilson v_, Jun 16 2011 *)
%t A007018 NestList[#^2 + #&, 1, 10] (* _Harvey P. Dale_, Sep 07 2011 *)
%o A007018 (PARI) a(n)=if(n>0,my(x=a(n-1));x^2+x,1) \\ Edited by _M. F. Hasler_, May 20 2019 and _Jason Yuen_, Mar 01 2025
%o A007018 (Maxima)
%o A007018 a[1]:1$
%o A007018 a[n]:=(a[n-1] + (a[n-1]^2))$
%o A007018 A007018(n):=a[n]$
%o A007018 makelist(A007018(n),n,1,10); /* _Martin Ettl_, Nov 08 2012 */
%o A007018 (Haskell)
%o A007018 a007018 n = a007018_list !! n
%o A007018 a007018_list = iterate a002378 1  -- _Reinhard Zumkeller_, Dec 18 2013
%o A007018 (Magma) [n eq 1 select 1 else Self(n-1)^2 + Self(n-1): n in [1..10]]; // _Vincenzo Librandi_, May 19 2015
%o A007018 (Python)
%o A007018 from itertools import islice
%o A007018 def A007018_gen(): # generator of terms
%o A007018     a = 1
%o A007018     while True:
%o A007018         yield a
%o A007018         a *= a+1
%o A007018 A007018_list = list(islice(A007018_gen(),9)) # _Chai Wah Wu_, Mar 19 2024
%Y A007018 Cf. A000058, A003687, A004168, A011782, A077125, A117805, A118227, A371321.
%Y A007018 Lower bound for A100016.
%Y A007018 Row sums of A122888.
%K A007018 nonn,nice,easy
%O A007018 0,2
%A A007018 _N. J. A. Sloane_