login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005185 Hofstadter Q-sequence: a(1) = a(2) = 1; a(n) = a(n-a(n-1)) + a(n-a(n-2)) for n > 2.
(Formerly M0438)
92
1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, 12, 12, 12, 16, 14, 14, 16, 16, 16, 16, 20, 17, 17, 20, 21, 19, 20, 22, 21, 22, 23, 23, 24, 24, 24, 24, 24, 32, 24, 25, 30, 28, 26, 30, 30, 28, 32, 30, 32, 32, 32, 32, 40, 33, 31, 38, 35, 33, 39, 40, 37, 38, 40, 39 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Rate of growth is not known. In fact it is not even known if this sequence is defined for all positive n.

Roman Pearce, Aug 29, 2014, has computed that a(n) exists for n <= 10^10. - N. J. A. Sloane

a(A081829(n)+1) < a(A081829(n)); a(A081828(n)+1) = a(A081828(n)); a(A081830(n)+1) > a(A081830(n)); a(A194626(n)+1) = a(A194626(n)) + 1. - Reinhard Zumkeller, Sep 15 2011

REFERENCES

B. W. Conolly, ``Meta-Fibonacci sequences,'' in S. Vajda, editor, Fibonacci and Lucas Numbers and the Golden Section. Halstead Press, NY, 1989, pp. 127-138.

R. K. Guy, Unsolved Problems in Number Theory, Sect. E31.

D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 138.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

S. Vajda, Fibonacci and Lucas Numbers and the Golden Section, Wiley, 1989, see p. 129.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 129.

LINKS

T. D. Noe and N. J. A. Sloane, Table of n, a(n) for n=1..10000

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.

P. Bourke, Hofstadter "Q" Series

P. Bourke, Hofstadter "Q" Series [Cached copy, pdf only, with permission]

P. Bourke, Listen to first 300 terms of this sequence [Cached copy from the Hofstadter "Q" web page, with permission]

Joseph Callaghan, John J. Chew III, and Stephen M. Tanny, On the behavior of a family of meta-Fibonacci sequences, SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824. See p. 794.

Benoit Cloitre, Plot of a(n)/n - 1/2 for n=1 up to 2^19

J.-P. Davalan, Douglas Hofstadter's sequences

Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.

S. W. Golomb, Discrete chaos: sequences satisfying "strange" recursions, unpublished manuscript, circa 1990 [cached copy, with permission (annotated)]

J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.

R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.

Nick Hobson, Python program for this sequence

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, Plot of first 100 million terms

Abraham Isgur, Mustazee Rahman, and Stephen Tanny, Solving non-homogeneous nested recursions using trees, Annals of Combinatorics 17.4 (2013): 695-710. See p. 695. - N. J. A. Sloane, Apr 16 2014

K. Pinn, Order and chaos in Hofstadter's Q(n) sequence, Complexity, 4:3 (1999), 41-46.

K. Pinn, A chaotic cousin of Conway's recursive sequence, Experimental Mathematics, 9:1 (2000), 55-65.

K. Pinn, A Chaotic Cousin Of Conway's Recursive Sequence

Eric Weisstein's World of Mathematics, Hofstadter's Q-Sequence

Wikipedia, Hofstadter sequence

Index entries for sequences from "Goedel, Escher, Bach"

Index entries for Hofstadter-type sequences

EXAMPLE

a(18) = 11 because a(17) is 10 and a(16) is 9, so we take a(18 - 10) + a(18 - 9) = a(8) + a(9) = 5 + 6 = 11.

MAPLE

A005185 := proc(n) option remember;

    if n<=2 then

        1

    elif n > procname(n-1) and n > procname(n-2) then

        RETURN(procname(n-procname(n-1))+procname(n-procname(n-2)));

    else

        ERROR(" died at n= ", n);

    fi;

end proc;

# More generally, the following defines the Hofstadter-Huber sequence Q(r, s) - N. J. A. Sloane, Apr 15 2014

r:=1; s:=2;

a:=proc(n) option remember; global r, s;

if n <= s then  1

else

    if (a(n-r) <= n) and (a(n-s) <= n) then

    a(n-a(n-r))+a(n-a(n-s));

    else lprint("died with n =", n); return (-1);

    fi;

fi; end;

[seq(a(n), n=1..100)];

MATHEMATICA

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

PROG

(Scheme): (define q (lambda (n) (cond ( (eqv? n 0) 1) ( (eqv? n 1) 1) ( #t (+ (q (- n (q (- n 1)))) (q (- n (q (- n 2)))))))))

(Mupad) q:=proc(n) option remember; begin if n<=2 then 1 else q(n-q(n-1))+q(n-q(n-2)) end_if; end_proc: q(i)$i=1..100; // Zerinvary Lajos, Apr 03 2007

(PARI) {a(n)= local(A); if(n<1, 0, A=vector(n, k, 1); for(k=3, n, A[k]= A[k-A[k-1]]+ A[k-A[k-2]]); A[n])} /* Michael Somos, Jul 16 2007 */

(Haskell)

a005185 n = a005185_list !! (n-1)

a005185_list = 1 : 1 : zipWith (+)

   (map a005185 $ zipWith (-) [3..] a005185_list)

   (map a005185 $ zipWith (-) [3..] $ tail a005185_list)

-- Reinhard Zumkeller, Jun 02 2013, Sep 15 2011

(C)

#include <stdio.h>

#define LIM 20

int Qa[LIM];

int Q(int n){if (n==1 || n==2){return 1; } else{return Qa[n-Qa[n-1]]+Qa[n-Qa[n-2]]; }}

int main(){int i; printf("n\tQ\n"); for(i=1; i<LIM; i+=1){printf("%d\t%d\n", i, Q(i)); Qa[i]=Q(i); }printf("\n"); } // Gonzalo Ciruelos, Aug 01 2013

(MAGMA) I:=[1, 1]; [n le 2 select I[n] else Self(n-Self(n-1))+Self(n-Self(n-2)): n in [1..90]]; // Vincenzo Librandi, Aug 08 2014

CROSSREFS

Cf. A004001, A005206, A005374, A005375, A005378, A005379, A070867, A226222, A239913.

Cf. A081827 (first differences).

Cf. A226244, A226245 (record values and where they occur).

See A244477 for a different start.

Sequence in context: A080595 A123579 A166493 * A119466 A100922 A047785

Adjacent sequences:  A005182 A005183 A005184 * A005186 A005187 A005188

KEYWORD

nonn,nice,easy,look

AUTHOR

Simon Plouffe and N. J. A. Sloane, May 20 1991

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 22 19:09 EDT 2014. Contains 248400 sequences.