|
| |
|
|
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)
|
|
78
| |
|
|
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; 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.
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.
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.
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 (njas(AT)research.att.com), 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
J.-P. Davalan, Douglas Hofstadter's sequences
R. K. Guy, Hofstadter's Meta-Fibonacci sequence, Amer. Math. Monthly, 93(3) 186-187 1986. [Broken link]
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, 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
| 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} ]
|
|
|
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 (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 */
(Haskell)
a005185 n = a005185_list !! (n-1)
a005185_list = 1 : 1 : qH 3 1 1 where
qH n u v = w : qH (n + 1) v w where
w = a005185 (n - u) + a005185 (n - v)
-- Reinhard Zumkeller, Sep 15 2011
|
|
|
CROSSREFS
| Cf. A004001, A005206, A005374, A005375, A005378, A005379.
Cf. A081827 (first differences).
Sequence in context: A080595 A123579 A166493 * A119466 A100922 A047785
Adjacent sequences: A005182 A005183 A005184 * A005186 A005187 A005188
|
|
|
KEYWORD
| nonn,nice,easy
|
|
|
AUTHOR
| Simon Plouffe, N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
