%I M3789 N1544

%S 1,5,9,49,2209,4870849,23725150497409,562882766124611619513723649,

%T 316837008400094222150776738483768236006420971486980609

%N A nonlinear recurrence: a(n) = a(n-1)^2 - 4*a(n-1) + 4 (for n>1).

%C An infinite coprime sequence defined by recursion. - _Michael Somos_, Mar 14 2004

%C This is the special case k=4 of sequences with exact mutual k-residues. In general, a(1)=k+1 and a(n)=min{m | m>a(n-1), mod(m,a(i))=k, i=1,...,n-1}. k=1 gives Sylvester's sequence A000058 and k=2 Fermat sequence A000215. - _Seppo Mustonen_, Sep 04 2005

%C A000058, A000215, A000289 and this sequence here can be represented as values of polynomials defined via P_0(z)= 1+z, P_{n+1}(z) = z+ prod_{i=0..n} P_i(z), with recurrences P_{n+1}(z) = (P_n(z))^2 -z*P_n(z) +z, n>=0. - _Vladimir Shevelev_, Dec 08 2010

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H T. D. Noe, <a href="/A000324/b000324.txt">Table of n, a(n) for n = 0..12</a>

%H A. V. Aho and N. J. A. Sloane, <a href="http://neilsloane.com/doc/doubly.html">Some doubly exponential sequences</a>, Fib. Quart., 11 (1973), 429-437.

%H S. W. Golomb, <a href="http://www.jstor.org/stable/2311857">On certain nonlinear recurring sequences</a>, Amer. Math. Monthly 70 (1963), 403-405.

%H R. Mestrovic, <a href="http://arxiv.org/abs/1202.3670">Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof</a>, arXiv preprint arXiv:1202.3670 [math.HO], 2012. - _N. J. A. Sloane_, Jun 13 2012

%H S. Mustonen, <a href="http://www.survo.fi/papers/resseq.pdf">On integer sequences with mutual k-residues</a>

%H <a href="/index/Aa#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 + ...</a>

%F a(n) = L(2^n)+2, if n>0 where L() is Lucas sequence.

%F For n>=1, a(n) = 4+Prod{i=0,...,n-1} a(i). - _Vladimir Shevelev_, Dec 08 2010

%t t = {1, 5}; Do[AppendTo[t, t[[-1]]^2 - 4*t[[-1]] + 4], {n, 11}] (* _T. D. Noe_, Jun 19 2012 *)

%t Join[{1}, RecurrenceTable[{a[n] == a[n-1]^2 - 4*a[n-1] + 4, a[1] == 5}, a, {n, 1, 8}]] (* _Jean-François Alcover_, Feb 07 2016 *)

%o (PARI) a(n)=if(n<2,max(0,1+4*n),a(n-1)^2-4*a(n-1)+4)

%o (PARI) a(n)=if(n<1,n==0,n=2^n;fibonacci(n+1)+fibonacci(n-1)+2)

%Y a(n) = A001566(n-1)+2 (for n>0).

%Y Cf. A000058.

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_