%I #82 Jun 28 2023 22:20:00
%S 1,1,1,1,2,3,5,13,22,41,111,191,361,982,1693,3205,8723,15042,28481,
%T 77521,133681,253121,688962,1188083,2249605,6123133,10559062,19993321,
%U 54419231,93843471,177690281,483649942,834032173,1579219205,4298430243,7412446082,14035282561,38202222241,65877982561
%N Dana Scott's sequence: a(n) = (a(n-2) + a(n-1) * a(n-3)) / a(n-4), a(0) = a(1) = a(2) = a(3) = 1.
%C The recursion has the Laurent property. If a(0), a(1), a(2), a(3) are variables, then a(n) is a Laurent polynomial (a rational function with a monic monomial denominator). - _Michael Somos_, Feb 05 2012
%C A generalization is if the recursion is modified to a(n) = (a(n-2) + a(n-1) * b*a(n-3)) / a(n-4) where b is a constant, and with arbitrary nonzero initial values, (a(0), a(1), a(2), a(3)), then a(n) = c*(a(n-3) - a(n-6)) + a(n-9) for all n in Z where c is another constant. - _Michael Somos_, Oct 28 2021
%H Seiichi Manyama, <a href="/A048736/b048736.txt">Table of n, a(n) for n = 0..3165</a> (first 501 terms from T. D. Noe)
%H Joshua Alman, Cesar Cuenca, and Jiaoyang Huang, <a href="https://doi.org/10.1007/s10801-015-0647-5">Laurent phenomenon sequences</a>, Journal of Algebraic Combinatorics 43(3) (2015), 589-633.
%H Hal Canary, <a href="http://halcanary.org/SSL/writeups/dana_scott.pdf">The Dana Scott Recurrence</a> [From _Jaume Oliver Lafont_, Sep 25 2009]
%H S. Fomin and A. Zelevinsky, <a href="http://arxiv.org/abs/math/0104241">The Laurent phenomenon</a>, arXiv:math/0104241 [math.CO], 2001.
%H S. Fomin and A. Zelevinsky, <a href="http://dx.doi.org/10.1006/aama.2001.0770">The Laurent Phenomenon</a>, Advances in Applied Mathematics, 28 (2002), 119-144.
%H David Gale, <a href="http://dx.doi.org/10.1007/BF03024070">The strange and surprising saga of the Somos sequences</a>, Math. Intelligencer 13(1) (1991), pp. 40-42.
%H D. Gale, <a href="http://dx.doi.org/10.1007/978-1-4612-2192-0">Tracking the Automatic Ant And Other Mathematical Explorations</a>, A Collection of Mathematical Entertainments Columns from The Mathematical Intelligencer, Springer, 1998, p. 4.
%H Matthew Christopher Russell, <a href="https://rucore.libraries.rutgers.edu/rutgers-lib/50145/">Using experimental mathematics to conjecture and prove theorems in the theory of partitions and commutative and non-commutative recurrences</a>, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LaurentPolynomial.html">Laurent Polynomial</a>
%H <a href="/index/Tu#2wis">Index entries for two-way infinite sequences</a>
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,10,0,0,-10,0,0,1)
%F a(n) = 9*a(n-3) - a(n-6) - 3 - ( ceiling(n/3) - floor(n/3) ), with a(0) = a(1) = a(2) = a(3) = 1, a(4) = 2, a(5) = 3. - _Michael Somos_
%F From _Jaume Oliver Lafont_, Sep 17 2009: (Start)
%F a(n) = 10*a(n-3) - 10*a(n-6) + a(n-9).
%F G.f.: (1 + x + x^2 - 9*x^3 - 8*x^4 - 7*x^5 + 5*x^6 + 3*x^7 + 2*x^8)/(1 - 10*x^3 + 10*x^6 - x^9). (End)
%F a(n) = a(3-n) for all n in Z. - _Michael Somos_, Feb 05 2012
%e G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 13*x^6 + 22*x^7 + 41*x^8 + 111*x^9 + ...
%t RecurrenceTable[{a[0] == a[1] == a[2] == a[3] == 1, a[n] == (a[n - 2] + a[n - 1]a[n - 3])/a[n - 4]}, a[n], {n, 40}] (* or *) LinearRecurrence[{0, 0, 10, 0, 0, -10, 0, 0, 1}, {1, 1, 1, 1, 2, 3, 5, 13, 22}, 41] (* _Harvey P. Dale_, Oct 22 2011 *)
%o (Haskell)
%o a048736 n = a048736_list !! n
%o a048736_list = 1 : 1 : 1 : 1 :
%o zipWith div
%o (zipWith (+)
%o (zipWith (*) (drop 3 a048736_list)
%o (drop 1 a048736_list))
%o (drop 2 a048736_list))
%o a048736_list
%o -- _Reinhard Zumkeller_, Jun 26 2011
%o (PARI) Vec((1+x+x^2-9*x^3-8*x^4-7*x^5+5*x^6+3*x^7+2*x^8) / (1-10*x^3+10*x^6-x^9)+O(x^99)) \\ _Charles R Greathouse IV_, Jul 01 2011
%o (Magma) I:=[1,1,1,1]; [n le 4 select I[n] else (Self(n-2) + Self(n-1)*Self(n-3)) / Self(n-4): n in [1..30]]; // _G. C. Greubel_, Feb 20 2018
%Y Cf. A006720, A006721, A006722, A006723, A092420, A072881.
%Y Cf. A192241, A192242 (primes and where they occur).
%Y Cf. A276531.
%K nonn,easy,nice
%O 0,5
%A _David Johnson-Davies_
%E More terms from _Michael Somos_