|
Search: id:A063882
|
|
|
| A063882 |
|
a(n) = a(n - a(n - 1)) + a(n - a(n - 4)), with a(1) = ... = a(4) = 1. |
|
+0
12
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
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.
|
|
REFERENCES
|
Kellie O'Connor Gutman (RKLGutman(AT)aol.com), p. 50 of "The Mathematical Intelligencer", Volume 23, Number 3, Summer 2001
|
|
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.
Index entries for Hofstadter-type sequences
|
|
FORMULA
|
n/2 < a(n) <= n/2 - log_2 (n) - 1 for all n > 6 [Balamohan et al.]
|
|
MAPLE
|
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;
|
|
MATHEMATICA
|
a[n_] := a[n] = a[n - a[n - 1]] + a[n - a[n - 4]]
|
|
CROSSREFS
|
Cf. A132157. For partial sums see A129632.
A136036(n) = a(n+1) - a(n).
Adjacent sequences: A063879 A063880 A063881 this_sequence A063883 A063884 A063885
Sequence in context: A104135 A046108 A079411 this_sequence A097873 A005375 A125051
|
|
KEYWORD
|
nice,nonn
|
|
AUTHOR
|
Theodor Schlickmann (Theodor.Schlickmann(AT)cec.eu.int), Aug 28 2001
|
|
EXTENSIONS
|
Edited by njas, Nov 06 2007
|
|
|
Search completed in 0.002 seconds
|
