A063892 -id:A063892 - cp's OEIS frontend

A064714 Define q(0)=1, q(1)=1, q(2)=1, q(n)=q(abs(n-q(n-2)))+q(abs(n-q(n-3))) (A063892); then a(0) = 1, a(n)=a(n-1)+2*(q(n)-n/2), n > 0.

1, 2, 2, 3, 7, 14, 18, 17, 15, 24, 26, 23, 25, 36, 40, 35, 33, 36, 50, 63, 63, 66, 68, 77, 81, 98, 98, 105, 93, 92, 110, 131, 137, 128, 110, 121, 129, 138, 124, 119, 115, 130, 158, 167, 155, 154, 176, 223, 219, 182, 152, 173, 259, 278, 266, 261, 271, 296, 304, 303

Offset: 0

Robert G. Wilson v, Oct 13 2001

Cf. A063892, A064552.

a[0] = q[0] = q[1] = q[2] = 1; q[n_] := q[n] = q[Abs[n - q[n - 2]]] + q[Abs[n - q[n - 3]]]; a[n_] := a[n] = a[n - 1] + 2*(q[n] - n/2); Table[a[n], {n, 0, 70} ]

A063882 a(n) = a(n - a(n - 1)) + a(n - a(n - 4)), with a(1) = ... = a(4) = 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, 12, 12, 13, 14, 14, 15, 15, 16, 17, 17, 17, 18, 18, 19, 20, 20, 21, 21, 22, 22, 22, 23, 23, 24, 25, 25, 26, 26, 27, 27, 28, 29, 29, 29, 30, 30, 31, 32, 32, 33, 33, 34, 34, 34, 35, 35, 36, 37, 37, 38, 38, 39, 39, 40

Offset: 1

Theodor Schlickmann (Theodor.Schlickmann(AT)cec.eu.int), Aug 28 2001

A captivating recursive function. A meta-Fibonacci recursion.
This has been completely analyzed by Balamohan et al. They prove that the sequence a(n) is monotonic, with successive terms increasing by 0 or 1, so the sequence hits every positive integer.
They demonstrate certain special structural properties and periodicities of the associated frequency sequence (the number of times a(n) hits each positive integer) that make possible an iterative computation of a(n) for any value of n.
Further, they derive a natural partition of the a-sequence into blocks of consecutive terms ("generations") with the property that terms in one block determine the terms in the next.
a(A202014(n)) = n and a(m) < n for m < A202014(n). [Reinhard Zumkeller, Dec 08 2011]

T. D. Noe and N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Altug Alkan, On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures, Complexity (2018) Article ID 8517125.
B. Balamohan, A. Kuznetsov, and S. Tanny, On the behavior of a variant of Hofstadter's Q-sequence, J. Integer Sequences, Vol. 10 (2007), #07.7.1.
Jonathan H. B. Deane and Guido Gentile, A diluted version of the problem of the existence of the Hofstadter sequence, arXiv:2311.13854 [math.NT], 2023.
A. Isgur, R. Lech, S. Moore, S. Tanny, Y. Verberne, and Y. Zhang, Constructing New Families of Nested Recursions with Slow Solutions, SIAM J. Discrete Math., 30(2), 2016, 1128-1147. (20 pages); DOI:10.1137/15M1040505
Kellie O'Connor Gutman, V(n) = V(n - V(n - 1)) + V(n - V(n - 4)), The Mathematical Intelligencer, Volume 23, Number 3, Summer 2001, page 50.
Index entries for Hofstadter-type sequences

Cf. A132157. For partial sums see A129632.
A136036(n) = a(n+1) - a(n).
Cf. A063892, A087777.
Cf. A132174, A132175, A132176, A132177.
Cf. A202016 (occur only once).

a063882 n = a063882_list !! (n-1)
a063882_list = 1 : 1 : 1 : 1 : zipWith (+)
   (map a063882 $ zipWith (-) [5..] a063882_list)
   (map a063882 $ zipWith (-) [5..] $ drop 3 a063882_list)
-- Reinhard Zumkeller, Dec 08 2011

a := proc(n) option remember; if n<=4 then 1 else if n > a(n-1) and n > a(n-4) then RETURN(a(n-a(n-1))+a(n-a(n-4))); else ERROR(" died at n= ", n); fi; fi; end;

a[1]=a[2]=a[3]=a[4]=1;a[n_]:=a[n]=a[n-a[n-1]]+a[n-a[n-4]];Table[a[n],{n,80}]

n/2 < a(n) <= n/2 + log_2 (n) - 1 for all n > 6 [Balamohan et al., Proposition 5].

Edited by N. J. A. Sloane, Nov 06 2007

Mathematica program corrected by Harvey P. Dale, Jan 24 2025

A226222 a(1) = a(2) = a(3) = 1, a(n) = a(n-2-a(n-2)) + a(n-1-a(n-3)) for n>3.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6, 7, 7, 8, 9, 9, 9, 10, 10, 11, 11, 11, 12, 13, 13, 13, 14, 15, 16, 16, 16, 17, 18, 18, 18, 18, 19, 20, 21, 21, 21, 21, 22, 22, 23, 23, 24, 25, 25, 25, 26, 26, 27, 27, 28, 29, 30, 30, 30, 31, 32, 32, 32, 32, 33, 35, 35

Offset: 1

Reinhard Zumkeller, May 31 2013

First numbers not occurring: 62, 66, 75, 79, 114, 123, ... .

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Hofstadter's Q-Sequence
Wikipedia, Hofstadter sequence
Index entries for Hofstadter-type sequences

Cf. A005185, A046699, A063892, A070867.

a226222 n = a226222_list !! (n-1)
a226222_list = 1 : 1 : 1 : zipWith (+)
   (map a226222 $ zipWith (-) [3..] a226222_list)
   (map a226222 $ zipWith (-) [2..] $ tail a226222_list)
-- Reinhard Zumkeller, May 31 2013

a[n_]:= a[n]= If[n<4, 1, a[n-2 -a[n-2]] + a[n-1 -a[n-3]]];
Table[a[n], {n, 80}] (* G. C. Greubel, Mar 28 2022 *)

@CachedFunction
def a(n): # A226222
    if (n<4): return 1
    else: return  a(n-2-a(n-2)) + a(n-1-a(n-3))
[a(n) for n in (1..80)] # G. C. Greubel, Mar 28 2022

a(n) = a(n-2 - a(n-2)) + a(n-1 - a(n-3)), with a(1) = a(2) = a(3) = 1.

A309492 a(1) = a(2) = 1, a(3) = 3, a(4) = 5, a(5) = 2; a(n) = a(n-a(n-2)) + a(n-a(n-3)) for n > 5.

Original entry on oeis.org

1, 1, 3, 5, 2, 4, 3, 9, 6, 4, 3, 13, 10, 4, 3, 17, 14, 4, 3, 21, 18, 4, 3, 25, 22, 4, 3, 29, 26, 4, 3, 33, 30, 4, 3, 37, 34, 4, 3, 41, 38, 4, 3, 45, 42, 4, 3, 49, 46, 4, 3, 53, 50, 4, 3, 57, 54, 4, 3, 61, 58, 4, 3, 65, 62, 4, 3, 69, 66, 4, 3, 73, 70, 4, 3, 77, 74, 4, 3, 81, 78, 4, 3, 85, 82, 4, 3

Offset: 1

Altug Alkan, Aug 04 2019

A well-defined solution sequence for recurrence a(n) = a(n-a(n-2)) + a(n-a(n-3)).

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,-1,1,1,-1,1,-1).

Cf. A063892, A244477.

I:=[1,1,3,5,2];[n le 5 select I[n] else Self(n-Self(n-2))+Self(n-Self(n-3)): n in [1..90]]; // Marius A. Burtea, Aug 07 2019

a[n_] := a[n] = If[n < 6, {1, 1, 3, 5, 2}[[n]], a[n - a[n-2]] + a[n - a[n-3]]]; Array[a, 87] (* Giovanni Resta, Aug 07 2019 *)

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

Vec(x*(1 + 3*x^2 + 2*x^3 - 2*x^4 + 4*x^5 - 7*x^6 + 6*x^7 - 3*x^8) / ((1 - x)^2*(1 + x)*(1 + x^2)^2) + O(x^40)) \\ Colin Barker, Aug 15 2019

For k > 2:
  a(4*k)   = 4*k+1,
  a(4*k+1) = 4*k-2,
  a(4*k+2) = 4,
  a(4*k+3) = 3.
From Colin Barker, Aug 04 2019: (Start)
G.f.: x*(1 + 3*x^2 + 2*x^3 - 2*x^4 + 4*x^5 - 7*x^6 + 6*x^7 - 3*x^8) / ((1 - x)^2*(1 + x)*(1 + x^2)^2).
a(n) = a(n-1) - a(n-2) + a(n-3) + a(n-4) - a(n-5) + a(n-6) - a(n-7) for n > 9.
(End)

A240811 a(n) = length (or lifetime) of the meta-Fibonacci sequence f(1) = ... = f(n) = 1; f(k)=f(k-f(k-2))+f(k-f(k-n)) if that sequence is only defined for finitely many terms, or 0 if that sequence is infinite.

Original entry on oeis.org

14, 54, 0, 37, 30, 63, 368, 47, 46, 108, 188, 118, 62, 209, 126, 197, 78, 127, 190, 141, 94, 130, 138, 226, 110, 134, 158, 138, 126, 170, 242, 371, 142, 190, 178, 225, 158, 206, 214, 304, 174, 226, 238, 245, 190, 250, 262, 328, 206, 234, 278, 357, 222, 290

Offset: 2

N. J. A. Sloane, Apr 15 2014

nonn

The term a(4) = 0 is only conjectural.

D. R. Hofstadter, Curious patterns and non-patterns in a family of meta-Fibonacci recursions, Lecture in Doron Zeilberger's Experimental Mathematics Seminar, Rutgers University, April 10 2014.

Lars Blomberg, Table of n, a(n) for n = 2..10000, "infinity" = 10^8.
D. R. Hofstadter, Curious patterns and non-patterns in a family of meta-Fibonacci recursions, Lecture in Doron Zeilberger's Experimental Mathematics Seminar, Rutgers University, April 10 2014; Part 1, Part 2.
D. R. Hofstadter, Graph of first 100 terms
Index entries for Hofstadter-type sequences

Cf. A063892, A087777, A240817 (sequences for n=3..5).
See A240814 for another version.
A diagonal of the triangle in A240813.

More terms from Lars Blomberg, Oct 24 2014

A309650 a(1) = 3, a(2) = 1, a(3) = 4, a(4) = 2; a(n) = a(n-a(n-2)) + a(n-a(n-3)) for n > 4.

Original entry on oeis.org

3, 1, 4, 2, 5, 3, 6, 9, 7, 5, 3, 11, 14, 7, 5, 8, 16, 19, 7, 5, 8, 21, 24, 12, 5, 8, 26, 29, 12, 5, 8, 31, 34, 12, 5, 13, 36, 39, 12, 5, 13, 41, 44, 12, 5, 13, 46, 49, 17, 5, 13, 51, 54, 17, 5, 13, 56, 59, 17, 5, 13, 61, 64, 17, 5, 18, 66, 69, 17, 5, 18, 71, 74, 17, 5, 18, 76, 79, 17, 5, 18, 81, 84, 22, 5

Offset: 1

Altug Alkan and Nathan Fox, Aug 11 2019

A well-defined quasi-periodic solution for recurrence (a(n) = a(n-a(n-2)) + a(n-a(n-3))).

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Altug Alkan, Nathan Fox, Orhan Ozgur Aybar, Zehra Akdeniz, On Some Solutions to Hofstadter's V-Recurrence, arXiv:2002.03396 [math.DS], 2020.

Cf. A063892, A244477, A309492, A309567.

I:=[3,1,4,2]; [n le 4 select I[n] else  Self(n-Self(n-2)) + Self(n-Self(n-3)): n in [1..90]]; // Marius A. Burtea, Aug 11 2019

Nest[Append[#, #[[-#[[-2]] ]] + #[[-#[[-3]] ]]] &, {3, 1, 4, 2}, 81] (* Michael De Vlieger, May 08 2020 *)

q=vector(100); q[1]=3; q[2]=1; q[3]=4; q[4]=2; for(n=5, #q, q[n] = q[n-q[n-2]] + q[n-q[n-3]]); q

For k >= 1:
a(5*k)   = 5,
a(5*k+1) = 5*floor(sqrt(k)+1/2)-2,
a(5*k+2) = 5*k+1,
a(5*k+3) = 5*k+4,
a(5*k+4) = 5*floor(sqrt(k))+2.

cp's OEIS Frontend

A064714 Define q(0)=1, q(1)=1, q(2)=1, q(n)=q(abs(n-q(n-2)))+q(abs(n-q(n-3))) (A063892); then a(0) = 1, a(n)=a(n-1)+2*(q(n)-n/2), n > 0.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A063882 a(n) = a(n - a(n - 1)) + a(n - a(n - 4)), with a(1) = ... = a(4) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A226222 a(1) = a(2) = a(3) = 1, a(n) = a(n-2-a(n-2)) + a(n-1-a(n-3)) for n>3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Sage

Formula

A309492 a(1) = a(2) = 1, a(3) = 3, a(4) = 5, a(5) = 2; a(n) = a(n-a(n-2)) + a(n-a(n-3)) for n > 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A240811 a(n) = length (or lifetime) of the meta-Fibonacci sequence f(1) = ... = f(n) = 1; f(k)=f(k-f(k-2))+f(k-f(k-n)) if that sequence is only defined for finitely many terms, or 0 if that sequence is infinite.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A309650 a(1) = 3, a(2) = 1, a(3) = 4, a(4) = 2; a(n) = a(n-a(n-2)) + a(n-a(n-3)) for n > 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula