login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007018 a(n) = a(n-1)^2 + a(n-1), a(0)=1.
(Formerly M1713)
36
1, 2, 6, 42, 1806, 3263442, 10650056950806, 113423713055421844361000442, 12864938683278671740537145998360961546653259485195806 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

a(n) has at least n different prime factors. [Saidak]

Subsequence of squarefree numbers (A005117). - Reinhard Zumkeller, Nov 15 2004 [This has been questioned, see MathOverflow link. - Charles R Greathouse IV, Mar 30 2015]

For prime factors see A007996.

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

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

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]

The next term has 209 digits. - Harvey P. Dale, Sep 07 2011

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

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

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

REFERENCES

R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 94.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..12

A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437, alternative link.

David Adjiashvili, Sandro Bosio and Robert Weismantel, Dynamic Combinatorial Optimization: a complexity and approximability study, 2012.

Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Jean-Marie Lagniez, and Pierre Marquis, On the Explanatory Power of Decision Trees, arXiv:2108.05266 [cs.AI], 2021.

Arvind Ayyer, Anne Schilling, Benjamin Steinberg and Nicolas M. Thiéry, Markov chains, R-trivial monoids and representation theory, Int. J. Algebra Comput., Vol. 25 (2015), pp. 169-231, arXiv preprint, arXiv:1401.4250 [math.CO], 2014.

Umberto Cerruti, Percorsi tra i numeri (in Italian), page 5.

A. Yu. Chirkov, D. V. Gribanov and N. Yu. Zolotykh, On the Proximity of the Optimal Values of the Multi-Dimensional Knapsack Problem with and without the Cardinality Constraint, arXiv:2004.08589 [math.OC], 2020.

D. R. Curtiss, On Kellogg's Diophantine problem, Amer. Math. Monthly, Vol. 29, No. 10 (1922), pp. 380-387.

Christian Elsholtz and Stefan Planitzer, Sums of four and more unit fractions and approximate parametrizations, arXiv:2012.05984 [math.NT], 2020.

Samuele Giraudo, The combinator M and the Mockingbird lattice, arXiv:2204.03586 [math.CO], 2022.

Murray S. Klamkin, ed., Problems in Applied Mathematics: Selections from SIAM Review, SIAM, 1990; see p. 577.

MathOverflow, Is OEIS A007018 really a subsequence of squarefree numbers?

Marko R. Riedel, Two-colorings of unordered full binary trees on n levels.

Matthew Roughan, Surreal Birthdays and Their Arithmetic, arXiv:1810.10373 [math.HO], 2018.

Filip Saidak, A New Proof of Euclid's Theorem, Amer. Math. Monthly, Vol. 113, No. 10 (Dec., 2006), pp. 937-938.

Alasdair Urquhart, The complexity of propositional proofs, Bull. Symbolic Logic, Vol. 1, No. 4 (1995) pp. 425-467, esp. p. 434.

Zalman Usiskin, Letter to N. J. A. Sloane, Oct. 1991

Index entries for sequences of form a(n+1)=a(n)^2 + ...

FORMULA

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

a(n) = floor(c^(2^n)) where c = A077125 = 1.597910218031873178338070118157... - Benoit Cloitre, Nov 06 2002

a(1)=1, a(n) = Product_{k=1..n-1} (a(k)+1). - Benoit Cloitre, Sep 13 2003

a(n) = A139145(2^(n+1) - 1). - Reinhard Zumkeller, Apr 10 2008

If an (additional) initial 1 is inserted, a(n) = Sum_{k<n} a(k)^2. - Franklin T. Adams-Watters, Jun 11 2009

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

a(n) = A053631(n)/2. - Martin Ettl, Nov 08 2012

Sum_{n>=0} (-1)^n/a(n) = A118227. - Amiram Eldar, Oct 29 2020

MAPLE

A007018 := proc(n)

    option remember;

    local aprev;

    if n = 0 then

        1;

    else

        aprev := procname(n-1) ;

        aprev*(aprev+1) ;

    end if;

end proc: # R. J. Mathar, May 06 2016

MATHEMATICA

a=1; lst={}; Do[a=a^2+a; AppendTo[lst, a], {n, 0, 9}]; lst (* Vladimir Joseph Stephan Orlovsky, Oct 20 2009 *)

FoldList[#^2 + #1 &, 1, Range@ 8] (* Robert G. Wilson v, Jun 16 2011 *)

NestList[#^2+#&, 1, 10] (* Harvey P. Dale, Sep 07 2011 *)

PROG

(PARI) a(n)=if(n>1, a(n-1)+a(n-1)^2, n) \\ Edited by M. F. Hasler, May 20 2019

(Maxima)

a[1]:1$

a[n]:=(a[n-1] + (a[n-1]^2))$

A007018(n):=a[n]$

makelist(A007018(n), n, 1, 10); /* Martin Ettl, Nov 08 2012 */

(Haskell)

a007018 n = a007018_list !! n

a007018_list = iterate a002378 1  -- Reinhard Zumkeller, Dec 18 2013

(MAGMA) [n eq 1 select 1 else Self(n-1)^2 + Self(n-1): n in [1..10]]; // Vincenzo Librandi, May 19 2015

CROSSREFS

Cf. A000058, A003687, A004168, A011782, A077125, A117805, A118227.

Lower bound for A100016.

Sequence in context: A349193 A230311 A276416 * A100016 A344562 A000610

Adjacent sequences:  A007015 A007016 A007017 * A007019 A007020 A007021

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 25 10:05 EDT 2022. Contains 354066 sequences. (Running on oeis4.)