A034803 Consider the sequence of 4-tuples {0,a,b,c} (c>=a+b; a,b,c>0) which have the smallest integer 'c' required to reach {k,k,k,k} in n steps under map {r,s,t,u}->{|r-s|,|s-t|,|t-u|,|u-r|}. This sequence gives the second term 'a' of these quadruples.

1, 0, 0, 1, 0, 1, 1, 2, 2, 5, 6, 7, 17, 20, 24, 57, 68, 81, 193, 230, 274, 653, 778, 927, 2209, 2632, 3136, 7473, 8904, 10609, 25281, 30122, 35890, 85525, 101902, 121415, 289329, 344732, 410744, 978793, 1166220, 1389537, 3311233, 3945294, 4700770

Offset

1,8

Links

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (0,0,3,0,0,1,0,0,1).

Formula

a(n)= Trib(2*q-3)+Trib(2*q-1) if r=0; Trib(2*q-2)+Trib(2*q-1) if r=1; Trib(2*q) if r=2 where q=[(n-1)/3], r=n-1 (mod 3) and Trib is the tribonacci sequence (A000073) with Trib(-3)=0, Trib(-2)=-1, Trib(-1)=1. G.f.: (x^8-2*x^7+3*x^6-x^5+2*x^3-1)/(x^9+x^6+3*x^3-1). Recurrence: a(n)=3*a(n-3)+a(n-6)+a(n-9), n >= 10.

Example

a(10)=5 because {0, 5, 14, 31}->{5, 9, 17, 31}->{4, 8, 14, 26}->{4, 6, 12, 22}->{2, 6, 10, 18}->{4, 4, 8, 16}->{0, 4, 8, 12}->{4, 4, 4, 12}->{0, 0, 8, 8}->{0, 8, 0, 8}->{8, 8, 8, 8} ('a'=5 in the first 4-tuple and there is no quadruple with a+b<=c <= 31 and 10 steps).

Mathematica

LinearRecurrence[{0, 0, 3, 0, 0, 1, 0, 0, 1}, {1, 0, 0, 1, 0, 1, 1, 2, 2}, 60] (* Harvey P. Dale, Jun 13 2017 *)

Crossrefs

A034804, A045794 (or A065678) give the terms 'b' and 'c' respectively.

Sequence in context: A063177 A249521 A355345 * A205885 A360690 A239262

Adjacent sequences: A034800 A034801 A034802 * A034804 A034805 A034806

Keyword

nonn

Author

N. J. A. Sloane

Extensions

Better description, more terms, formula, etc. from Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jun 24 2001

Minor edits from Michael B. Porter, Feb 03 2010

Status

approved