A275365 a(1)=2, a(2)=2; thereafter a(n) = a(n-a(n-1)) + a(n-a(n-2)).

0, 2, 2, 4, 2, 6, 2, 8, 2, 10, 2, 12, 2, 14, 2, 16, 2, 18, 2, 20, 2, 22, 2, 24, 2, 26, 2, 28, 2, 30, 2, 32, 2, 34, 2, 36, 2, 38, 2, 40, 2, 42, 2, 44, 2, 46, 2, 48, 2, 50, 2, 52, 2, 54, 2, 56, 2, 58, 2, 60, 2, 62, 2, 64, 2, 66, 2, 68, 2, 70, 2, 72, 2, 74

Offset: 0

Author

Nathan Fox, Jul 24 2016

Keywords

• easy
• nonn

Comments

a(n) is the solution to the recurrence relation a(n) = a(n-a(n-1)) + a(n-a(n-2)) [Hofstadter's Q recurrence], with the initial conditions: a(n) = 0 if n <= 0; a(1) = 2, a(2) = 2.

Starting with n=1, a(n) is A005843 interleaved with A007395.

This sequence is the same as A133265 with the leading 2 changed to a 0.

Links

• Nathan Fox, Table of n, a(n) for n = 0..1000
• Nathan Fox, Finding Linear-Recurrent Solutions to Hofstadter-Like Recurrences Using Symbolic Computation, arXiv:1609.06342 [math.NT], 2016.
• Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1).

Crossrefs

Cf. A005185, A133265, A188670, A244477, A264756, A264757, A264758, A268368, A275153, A275361, A275362.

Programs

Mathematica

Join[{0}, LinearRecurrence[{0, 2, 0, -1}, {2, 2, 4, 2}, 73]] (* Jean-François Alcover, Feb 19 2019 *)

Formula

a(0) = 0; thereafter, a(2n) = 2, a(2n+1) = 2n+2.

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

G.f.: -(2*x^3 -2*x -2)/((x-1)^2*(x+1)^2).