The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
a(A202014(n)) = n and a(m) < n for m < A202014(n). [Reinhard Zumkeller, Dec 08 2011]
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.
Jonathan H. B. Deane and Guido Gentile, A diluted version of the problem of the existence of the Hofstadter sequence, arXiv:2311.13854 [math.NT], 2023.
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
Kellie O'Connor Gutman, V(n) = V(n - V(n - 1)) + V(n - V(n - 4)), The Mathematical Intelligencer, Volume 23, Number 3, Summer 2001, page 50.
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)
-- Reinhard Zumkeller, Dec 08 2011
CROSSREFS
Cf. A132157. For partial sums see A129632.
A136036(n) = a(n+1) - a(n).
Cf. A202016 (occur only once).
Sequence in context: A079411 A360744 A198454 * A097873 A005375 A138370
KEYWORD
nice,nonn
AUTHOR
Theodor Schlickmann (Theodor.Schlickmann(AT)cec.eu.int), Aug 28 2001
EXTENSIONS
Edited by N. J. A. Sloane, Nov 06 2007
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 30 17:56 EDT 2024. Contains 372971 sequences. (Running on oeis4.)