A275153 -id:A275153 - cp's OEIS frontend

A275361 An eventually quasilinear solution to Hofstadter's Q-recurrence.

0, 4, -40, -9, 8, -8, 7, 1, 5, 13, -24, -1, 8, 8, 8, 1, 5, 13, -8, 7, 8, 8, 23, 1, 5, 13, 8, 15, 8, 16, 31, 1, 5, 13, 24, 23, 8, 24, 39, 1, 5, 13, 40, 31, 8, 32, 47, 1, 5, 13, 56, 39, 8, 40, 55, 1, 5, 13, 72, 47, 8, 48, 63, 1, 5, 13, 88, 55, 8, 56, 71

Offset: 1

Nathan Fox, Jul 24 2016

sign

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 first 45 terms as initial conditions.

This is a quasilinear sequence with quasiperiod 8. Four of the component sequences are constant, three have slope 1, and one has slope 2.

Nathan Fox, Table of n, a(n) for n = 1..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, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, -1).

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

Join[{0, 4, -40, -9, 8, -8, 7, 1, 5, 13, -24, -1, 8, 8, 8}, LinearRecurrence[ {0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, -1}, {1, 5, 13, -8, 7, 8, 8, 23, 1, 5, 13, 8, 15, 8, 16, 31}, 100]] (* Jean-François Alcover, Dec 12 2018 *)

a(1) = 0, a(2) = 4, a(14) = 8, a(15) = 8; otherwise:
a(8n) = 1, a(8n+1) = 5, a(8n+2) = 13, a(8n+3) = 16n-40, a(8n+4) = 8n-9, a(8n+5) = 8, a(8n+6) = 8n-8, a(8n+7) = 8n+7.
a(n) = 2*a(n-8) - a(n-16) for n>31.
G.f.: -(7*x^30 -8*x^29 -14*x^22 +16*x^21 +9*x^17 +5*x^16 +x^15 +6*x^14 -24*x^13 +8*x^12 -17*x^11 -56*x^10 -5*x^9 -5*x^8 -x^7 -7*x^6 +8*x^5 -8*x^4 +9*x^3 +40*x^2 -4*x)/((x-1)^2*(x+1)^2*(x^2+1)^2*(x^4+1)^2).

A275362 An eventually quasilinear solution to Hofstadter's Q recurrence.

Original entry on oeis.org

-9, 2, 9, 2, 0, 7, 9, 10, 3, 0, 2, 9, 2, 9, 9, 9, 20, 3, 9, 22, 9, 2, 18, 9, 18, 30, 3, 18, 32, 9, 2, 27, 9, 27, 40, 3, 27, 42, 9, 2, 36, 9, 36, 50, 3, 36, 52, 9, 2, 45, 9, 45, 60, 3, 45, 62, 9, 2, 54, 9, 54, 70, 3, 54, 72, 9, 2, 63, 9, 63, 80, 3, 63, 82

Offset: 1

Nathan Fox, Jul 24 2016

sign

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) = -9, a(2) = 2, a(3) = 9, a(4) = 2, a(5) = 0, a(6) = 7, a(7) = 9, a(8) = 10, a(9) = 3, a(10) = 0, a(11) = 2, a(12) = 9, a(13) = 2, a(14) = 9, a(15) = 9, a(16) = 9.

This is a quasilinear sequence with quasiperiod 9. Four of the component sequences are constant, three have slope 1, and two have slope 10/9.

Nathan Fox, Table of n, a(n) for n = 1..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, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, -1).

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

Join[{-9, 2, 9, 2, 0, 7, 9, 10, 3, 0, 2}, LinearRecurrence[{0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, -1}, {9, 2, 9, 9, 9, 20, 3, 9, 22, 9, 2, 18, 9, 18, 30, 3, 18, 32}, 100]] (* Jean-François Alcover, Dec 13 2018 *)

a(6) = 7, a(7) = 9, a(11) = 2; otherwise:
a(9n) = 3, a(9n+1) = 9n-9, a(9n+2) = 10n+2, a(9n+3) = 9, a(9n+4) = 2, a(9n+5) = 9n, a(9n+6) = 9, a(9n+7) = 9n, a(9n+8) = 10n+10.
a(n) = 2*a(n-9) - a(n-18) for n>29.
G.f.: -(10*x^28 -9*x^24 +2*x^23 -20*x^19 +3*x^17 +9*x^15 +5*x^14 -9*x^13 +2*x^12 +9*x^11 +2*x^10 -18*x^9 -3*x^8 -10*x^7 -9*x^6 -7*x^5 -2*x^3 -9*x^2 -2*x+9)/((x-1)^2*(x^2+x+1)^2*(x^6+x^3+1)^2).

A283880 A linear-recurrent solution to Hofstadter's Q recurrence.

Original entry on oeis.org

12, 6, 4, 6, 1, 6, 12, 10, 4, 6, 13, 6, 12, 16, 4, 6, 25, 6, 12, 26, 4, 6, 37, 6, 12, 42, 4, 6, 49, 6, 12, 68, 4, 6, 61, 6, 12, 110, 4, 6, 73, 6, 12, 178, 4, 6, 85, 6, 12, 288, 4, 6, 97, 6, 12, 466, 4, 6, 109, 6, 12, 754, 4, 6, 121, 6, 12, 1220, 4, 6, 133, 6, 12, 1974, 4

Offset: 1

Nathan Fox, Mar 19 2017

nonn

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) = 12, a(2) = 6, a(3) = 4, a(4) = 6, a(5) = 1, a(6) = 6, a(7) = 12, a(8) = 10, a(9) = 4.

This sequence is an interleaving of six simpler sequences. Four are constant, one is a linear polynomial, and one is a Fibonacci-like sequence.

Nathan Fox, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1).

Cf. A005185, A188670, A244477, A269328, A275153, A283881.

A283880:=proc(n) option remember: if n <= 0 then 0: elif n = 1 then 12: elif n = 2 then 6: elif n = 3 then 4: elif n = 4 then 6: elif n = 5 then 1: elif n = 6 then 6: elif n = 7 then 12: elif n = 8 then 10: elif n = 9 then 4: else A283880(n-A283880(n-1)) + A283880(n-A283880(n-2)): fi: end:

from functools import cache
@cache
def a(n):
    if n <= 0: return 0
    if n <= 9: return [12, 6, 4, 6, 1, 6, 12, 10, 4][n-1]
    return a(n - a(n-1)) + a(n - a(n-2))
print([a(n) for n in range(1, 76)]) # Michael S. Branicky, Dec 06 2021

a(6n) = 6, a(6n+1) = 12, a(6n+2) = 2*F(n+4), a(6n+3) = 4, a(6n+4) = 6, a(6n+5) = 12n+1.
G.f.: (-6*x^23+11*x^22-6*x^21-4*x^20-4*x^19-12*x^18+12*x^16+2*x^13 +12*x^11 -10*x^10 +12*x^9+8*x^8 +8*x^7+24*x^6-6*x^5-x^4-6*x^3-4*x^2 -6*x-12) / ((-1+x^6+x^12) *(-1+x)^2*(1+x)^2*(1+x+x^2)^2*(1-x+x^2)^2).
a(n) = 3*a(n-6) - 2*a(n-12) - a(n-18) + a(n-24) for n > 24.

A283881 A linear-recurrent solution to Hofstadter's Q recurrence.

Original entry on oeis.org

7, 0, 8, 7, 7, 8, 4, 7, 7, 16, 7, 7, 16, 4, 7, 14, 24, 7, 7, 32, 4, 7, 21, 32, 7, 7, 64, 4, 7, 28, 40, 7, 7, 128, 4, 7, 35, 48, 7, 7, 256, 4, 7, 42, 56, 7, 7, 512, 4, 7, 49, 64, 7, 7, 1024, 4, 7, 56, 72, 7, 7, 2048, 4, 7, 63, 80, 7, 7, 4096, 4, 7, 70, 88, 7, 7

Offset: 1

Nathan Fox, Mar 19 2017

nonn

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) = 7, a(2) = 0, a(3) = 8, a(4) = 7, a(5) = 7, a(6) = 8, a(7) = 4.

This sequence is an interleaving of seven simpler sequences. Four are constant, two are linear polynomials, and one is a geometric sequence.

Nathan Fox, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, -5, 0, 0, 0, 0, 0, 0, 2).

Cf. A005185, A188670, A244477, A269328, A275153, A283880.

A283881:=proc(n) option remember: if n <= 0 then 0: elif n = 1 then 7: elif n = 2 then 0: elif n = 3 then 8: elif n = 4 then 7: elif n = 5 then 7: elif n = 6 then 8: elif n = 7 then 4: else A283881(n-A283881(n-1)) + A283881(n-A283881(n-2)): fi: end:

a(7n) = 4, a(7n+1) = 7, a(7n+2) = 7n, a(7n+3) = 8n+8, a(7n+4) = 7, a(7n+5) = 7, a(7n+6) = 2^(n+3).
G.f.: (-8*x^20-8*x^19-14*x^18-14*x^17+14*x^15-14*x^14+12*x^13 +16*x^12 +21*x^11 +21*x^10+16*x^9-7*x^8+21*x^7-4*x^6-8*x^5-7*x^4-7*x^3 -8*x^2-7) / ((-1+2*x^7)*(-1+x)^2*(1+x+x^2+x^3+x^4+x^5+x^6)^2).
a(n) = 4*a(n-7) - 5*a(n-14) + 2*a(n-21) for n > 21.

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

Original entry on oeis.org

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

Nathan Fox, Jul 24 2016

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.

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

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

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

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

cp's OEIS Frontend

A275361 An eventually quasilinear solution to Hofstadter's Q-recurrence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A275362 An eventually quasilinear solution to Hofstadter's Q recurrence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A283880 A linear-recurrent solution to Hofstadter's Q recurrence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Python

Formula

A283881 A linear-recurrent solution to Hofstadter's Q recurrence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula