login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A296518 a(1) = 3, a(2) = a(5) = 1, a(3) = a(4) = a(6) = 2; a(n) = a(n-a(n-1)) + a(n-a(n-2)) + a(n-a(n-3)) for n > 6. 7
3, 1, 2, 2, 1, 2, 4, 8, 8, 4, 8, 12, 12, 4, 12, 16, 16, 4, 16, 20, 20, 4, 20, 24, 24, 4, 24, 28, 28, 4, 28, 32, 32, 4, 32, 36, 36, 4, 36, 40, 40, 4, 40, 44, 44, 4, 44, 48, 48, 4, 48, 52, 52, 4, 52, 56, 56, 4, 56, 60, 60, 4, 60, 64, 64, 4, 64, 68, 68, 4, 68, 72, 72, 4, 72, 76, 76, 4, 76, 80, 80, 4, 80, 84, 84, 4, 84, 88, 88, 4 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

A quasi-periodic solution to the three-term Hofstadter recurrence a(n) = a(n-a(n-1)) + a(n-a(n-2)) + a(n-a(n-3)). For a quasi-quadratic solution, see also A268368 that uses the convention that evaluating at a nonpositive index gives zero (this sequence and A244477 do not use this convention). See page 119 at the Fox reference for the detailed analysis of solutions with initial conditions with 1 through N. The three-term Hofstadter recurrence also has a slow solution (A278055) and chaotic solutions such as A292351, A296413 and A296440. So the recurrence a(n) = a(n-a(n-1)) + a(n-a(n-2)) + a(n-a(n-3)) has all known types of behaviors that are mentioned on page 7 of the Tanny reference in the Links section.

LINKS

Colin Barker, Table of n, a(n) for n = 1..1000

Altug Alkan, On a conjecture about generalized Q-recurrence, Open Mathematics (2018) Vol. 16, Issue 1, 1490-1500.

Nathan Fox, An exploration of nested recurrences using experimental mathematics, Ph.D. thesis, 2017 (19 MB).

Steve Tanny, An Invitation to Nested Recurrence Relations, Slides of talk presented at CanaDAM 2013.

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

FORMULA

a(4*k) = a(4*k+1) = a(4*k+3) = 4*k, a(4*k+2) = 4 for k > 1.

From Colin Barker, Dec 14 2017: (Start)

G.f.: x*(3 + x + 2*x^2 + 2*x^3 - 5*x^4 + 4*x^7 + 9*x^8 + x^9 + 2*x^10 - 2*x^11 - 3*x^12 - 2*x^13) / ((1 - x)^2*(1 + x)^2*(1 + x^2)^2).

a(n) = 2*a(n-4) - a(n-8) for n > 14.

(End)

MAPLE

a:= proc(n) option remember; procname(n-procname(n-1))+procname(n-procname(n-2))+procname(n-procname(n-3)) end proc:

a(1):= 3: a(2):= 1: a(3):= 2: a(4):= 2: a(5):= 1: a(6):= 2:

map(a, [$1..100]); # after Robert Israel at A296440

MATHEMATICA

Fold[Append[#1, #1[[#2 - #1[[#2 - 1]] ]] + #1[[#2 - #1[[#2 - 2]] ]] + #1[[#2 - #1[[#2 - 3]] ]] ] &, {3, 1, 2, 2, 1, 2}, Range[7, 90]] (* or *)

Rest@ CoefficientList[Series[x (3 + x + 2 x^2 + 2 x^3 - 5 x^4 + 4 x^7 + 9 x^8 + x^9 + 2 x^10 - 2 x^11 - 3 x^12 - 2 x^13)/((1 - x)^2*(1 + x)^2*(1 + x^2)^2), {x, 0, 90}], x] (* Michael De Vlieger, Dec 14 2017 *)

LinearRecurrence[{0, 0, 0, 2, 0, 0, 0, -1}, {3, 1, 2, 2, 1, 2, 4, 8, 8, 4, 8, 12, 12, 4}, 100] (* Harvey P. Dale, May 30 2018 *)

PROG

(PARI) q=vector(10^5); q[1]=3; q[2]=1; q[3]=2; q[4]=2; q[5]=1; q[6]=2; for(n=7, #q, q[n] = q[n-q[n-1]]+q[n-q[n-2]]+q[n-q[n-3]]); q

(PARI) Vec(x*(3 + x + 2*x^2 + 2*x^3 - 5*x^4 + 4*x^7 + 9*x^8 + x^9 + 2*x^10 - 2*x^11 - 3*x^12 - 2*x^13) / ((1 - x)^2*(1 + x)^2*(1 + x^2)^2) + O(x^100)) \\ Colin Barker, Dec 14 2017

(Scheme, with memoization-macro definec) (definec (A296518 n) (cond ((= 1 n) 3) ((or (= 2 n) (= 5 n)) 1) ((<= n 6) 2) (else (+ (A296518 (- n (A296518 (- n 1)))) (A296518 (- n (A296518 (- n 2)))) (A296518 (- n (A296518 (- n 3)))))))) ;; Antti Karttunen, Dec 16 2017

CROSSREFS

Cf. A005185, A244477, A268368, A278055, A296413, A296440.

Sequence in context: A105973 A088429 A134658 * A111951 A222593 A107033

Adjacent sequences:  A296515 A296516 A296517 * A296519 A296520 A296521

KEYWORD

nonn,easy

AUTHOR

Altug Alkan, Dec 14 2017

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 10 04:08 EDT 2021. Contains 343748 sequences. (Running on oeis4.)