|
|
A063882
|
|
a(n) = a(n - a(n - 1)) + a(n - a(n - 4)), with a(1) = ... = a(4) = 1.
|
|
31
|
|
|
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;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
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.
|
|
LINKS
|
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
|
|
FORMULA
|
n/2 < a(n) <= n/2 + log_2 (n) - 1 for all n > 6 [Balamohan et al., Proposition 5].
|
|
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[1] = a[2] = a[3] = a[4] = 1; a[n_] := a[n] = a[n-a[n-1]] + a[n-a[n-4]]
|
|
PROG
|
(Haskell)
a063882 n = a063882_list !! (n-1)
a063882_list = 1 : 1 : 1 : 1 : zipWith (+)
(map a063882 $ zipWith (-) [5..] a063882_list)
(map a063882 $ zipWith (-) [5..] $ drop 3 a063882_list)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nice,nonn
|
|
AUTHOR
|
Theodor Schlickmann (Theodor.Schlickmann(AT)cec.eu.int), Aug 28 2001
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|