|
Search: id:A005185
|
|
|
| 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)
|
|
+0
66
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Rate of growth is not known. In fact it is not even known if this sequence is defined for all positive n.
|
|
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.
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.
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.
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.
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 njas, 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. Intger Sequences, Vol. 10 (2007), #07.7.1.
P. Bourke, Hofstadter "Q" Series
J.-P. Davalan, Douglas Hofstadter's sequences
R. K. Guy, Hofstadter's Meta-Fibonacci sequence, Amer. Math. Monthly, 93(3) 186-187 1986.
Nick Hobson, Python program for this sequence
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
T. Sillke, Hofstadter Sequence
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
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
|
a := proc(n) option remember; if n<=2 then 1 else if n > a(n-1) and n > a(n-2) then RETURN(a(n-a(n-1))+a(n-a(n-2))); else ERROR(" died at n= ", n); fi; fi; end;
|
|
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} ]
|
|
PROGRAM
|
(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 (zerinvarylajos(AT)yahoo.com), 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 */
|
|
CROSSREFS
|
Cf. A004001, A005206, A005374, A005375, A005378, A005379.
Sequence in context: A094606 A080595 A123579 this_sequence A119466 A100922 A047785
Adjacent sequences: A005182 A005183 A005184 this_sequence A005186 A005187 A005188
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
Simon Plouffe, njas
|
|
|
Search completed in 0.003 seconds
|
