|
| |
|
|
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)
|
|
229
|
|
|
|
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.
|
|
|
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
|
D. R. Hofstadter, Eta-Lore [Cached copy, with permission]
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.
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.
|
|
|
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, 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)
(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
(Scheme)
;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization
(Sage)
@CachedFunction
def a(n):
if (n<3): return 1
else: return a(n -a(n-1)) + a(n -a(n-2))
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def a(n):
if n < 3: return 1
return a(n - a(n-1)) + a(n - a(n-2))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
