A048736 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.

1, 1, 1, 1, 2, 3, 5, 13, 22, 41, 111, 191, 361, 982, 1693, 3205, 8723, 15042, 28481, 77521, 133681, 253121, 688962, 1188083, 2249605, 6123133, 10559062, 19993321, 54419231, 93843471, 177690281, 483649942, 834032173, 1579219205, 4298430243, 7412446082, 14035282561, 38202222241, 65877982561

Offset

0,5

Comments

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

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

Links

Seiichi Manyama, Table of n, a(n) for n = 0..3165 (first 501 terms from T. D. Noe)

Joshua Alman, Cesar Cuenca, and Jiaoyang Huang, Laurent phenomenon sequences, Journal of Algebraic Combinatorics 43(3) (2015), 589-633.

Hal Canary, The Dana Scott Recurrence [From Jaume Oliver Lafont, Sep 25 2009]

S. Fomin and A. Zelevinsky, The Laurent phenomenon, arXiv:math/0104241 [math.CO], 2001.

S. Fomin and A. Zelevinsky, The Laurent Phenomenon, Advances in Applied Mathematics, 28 (2002), 119-144.

David Gale, The strange and surprising saga of the Somos sequences, Math. Intelligencer 13(1) (1991), pp. 40-42.

D. Gale, Tracking the Automatic Ant And Other Mathematical Explorations, A Collection of Mathematical Entertainments Columns from The Mathematical Intelligencer, Springer, 1998, p. 4.

Matthew Christopher Russell, Using experimental mathematics to conjecture and prove theorems in the theory of partitions and commutative and non-commutative recurrences, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.

Eric Weisstein's World of Mathematics, Laurent Polynomial

Index entries for two-way infinite sequences

Index entries for linear recurrences with constant coefficients, signature (0,0,10,0,0,-10,0,0,1)

Formula

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

From Jaume Oliver Lafont, Sep 17 2009: (Start)

a(n) = 10*a(n-3) - 10*a(n-6) + a(n-9).

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)

a(n) = a(3-n) for all n in Z. - Michael Somos, Feb 05 2012

Example

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 + ...

Mathematica

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 *)

Prog

(Haskell)
a048736 n = a048736_list !! n
a048736_list = 1 : 1 : 1 : 1 :
   zipWith div
     (zipWith (+)
       (zipWith (*) (drop 3 a048736_list)
                    (drop 1 a048736_list))
       (drop 2 a048736_list))
     a048736_list
-- Reinhard Zumkeller, Jun 26 2011
(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
(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

Crossrefs

Cf. A006720, A006721, A006722, A006723, A092420, A072881.

Cf. A192241, A192242 (primes and where they occur).

Cf. A276531.

Sequence in context: A177374 A142881 A163159 * A235621 A193300 A215310

Adjacent sequences: A048733 A048734 A048735 * A048737 A048738 A048739

Keyword

nonn,easy,nice

Author

David Johnson-Davies

Extensions

More terms from Michael Somos

Status

approved