|
%I M1713 #212 Mar 19 2024 11:49:03
%S 1,2,6,42,1806,3263442,10650056950806,113423713055421844361000442,
%T 12864938683278671740537145998360961546653259485195806
%N a(n) = a(n-1)^2 + a(n-1), a(0)=1.
%C 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 Equivalently, the number of acyclic digraphs (dags) that unravel to a perfect binary tree of height n. - _Nachum Dershowitz_, Jul 03 2022
%C a(n) has at least n different prime factors. [Saidak]
%C 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 For prime factors see A007996.
%C 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 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 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 The next term has 209 digits. - _Harvey P. Dale_, Sep 07 2011
%C 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 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 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 R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 94.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H N. J. A. Sloane, <a href="/A007018/b007018.txt">Table of n, a(n) for n = 0..12</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 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 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 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 Umberto Cerruti, <a href="/A146564/a146564.pdf">Percorsi tra i numeri</a> (in Italian), page 5.
%H 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 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 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 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 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 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 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 Marko R. Riedel, <a href="http://math.stackexchange.com/questions/1285304/">Two-colorings of unordered full binary trees on n levels</a>.
%H Matthew Roughan, <a href="https://arxiv.org/abs/1810.10373">Surreal Birthdays and Their Arithmetic</a>, arXiv:1810.10373 [math.HO], 2018.
%H 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 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 Zalman Usiskin, <a href="/A007018/a007018.pdf">Letter to N. J. A. Sloane, Oct. 1991</a>.
%H <a href="/index/Aa#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 + ...</a>.
%F 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 a(n) = floor(c^(2^n)) where c = A077125 = 1.597910218031873178338070118157... - _Benoit Cloitre_, Nov 06 2002
%F a(1)=1, a(n) = Product_{k=1..n-1} (a(k)+1). - _Benoit Cloitre_, Sep 13 2003
%F a(n) = A139145(2^(n+1) - 1). - _Reinhard Zumkeller_, Apr 10 2008
%F If an (additional) initial 1 is inserted, a(n) = Sum_{k<n} a(k)^2. - _Franklin T. Adams-Watters_, Jun 11 2009
%F 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 a(n) = A053631(n)/2. - _Martin Ettl_, Nov 08 2012
%F Sum_{n>=0} (-1)^n/a(n) = A118227. - _Amiram Eldar_, Oct 29 2020
%F Sum_{n>=0} 1/a(n) = A371321. - _Amiram Eldar_, Mar 19 2024
%p A007018 := proc(n)
%p option remember;
%p local aprev;
%p if n = 0 then
%p 1;
%p else
%p aprev := procname(n-1) ;
%p aprev*(aprev+1) ;
%p end if;
%p end proc: # _R. J. Mathar_, May 06 2016
%t FoldList[#^2 + #1 &, 1, Range@ 8] (* _Robert G. Wilson v_, Jun 16 2011 *)
%t NestList[#^2 + #&, 1, 10] (* _Harvey P. Dale_, Sep 07 2011 *)
%o (PARI) a(n)=if(n>1,a(n-1)+a(n-1)^2,n) \\ Edited by _M. F. Hasler_, May 20 2019
%o (Maxima)
%o a[1]:1$
%o a[n]:=(a[n-1] + (a[n-1]^2))$
%o A007018(n):=a[n]$
%o makelist(A007018(n),n,1,10); /* _Martin Ettl_, Nov 08 2012 */
%o (Haskell)
%o a007018 n = a007018_list !! n
%o a007018_list = iterate a002378 1 -- _Reinhard Zumkeller_, Dec 18 2013
%o (Magma) [n eq 1 select 1 else Self(n-1)^2 + Self(n-1): n in [1..10]]; // _Vincenzo Librandi_, May 19 2015
%o (Python)
%o from itertools import islice
%o def A007018_gen(): # generator of terms
%o a = 1
%o while True:
%o yield a
%o a *= a+1
%o A007018_list = list(islice(A007018_gen(),9)) # _Chai Wah Wu_, Mar 19 2024
%Y Cf. A000058, A003687, A004168, A011782, A077125, A117805, A118227, A371321.
%Y Lower bound for A100016.
%Y Row sums of A122888.
%K nonn,nice,easy
%O 0,2
%A _N. J. A. Sloane_
| 