cp's OEIS Frontend

A063882 a(n) = a(n - a(n - 1)) + a(n - a(n - 4)), with a(1) = ... = a(4) = 1.

%I A063882 #46 Jan 24 2025 19:35:30
%S A063882 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,
%T A063882 17,17,17,18,18,19,20,20,21,21,22,22,22,23,23,24,25,25,26,26,27,27,28,
%U A063882 29,29,29,30,30,31,32,32,33,33,34,34,34,35,35,36,37,37,38,38,39,39,40
%N A063882 a(n) = a(n - a(n - 1)) + a(n - a(n - 4)), with a(1) = ... = a(4) = 1.
%C A063882 A captivating recursive function. A meta-Fibonacci recursion.
%C A063882 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.
%C A063882 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.
%C A063882 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.
%C A063882 a(A202014(n)) = n and a(m) < n for m < A202014(n). [_Reinhard Zumkeller_, Dec 08 2011]
%H A063882 T. D. Noe and N. J. A. Sloane, <a href="/A063882/b063882.txt">Table of n, a(n) for n = 1..10000</a>
%H A063882 Altug Alkan, <a href="https://doi.org//10.1155/2018/8517125">On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures</a>, Complexity (2018) Article ID 8517125.
%H A063882 B. Balamohan, A. Kuznetsov, and S. Tanny, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Tanny/tanny3.html">On the behavior of a variant of Hofstadter's Q-sequence</a>, J. Integer Sequences, Vol. 10 (2007), #07.7.1.
%H A063882 Jonathan H. B. Deane and Guido Gentile, <a href="https://arxiv.org/abs/2311.13854">A diluted version of the problem of the existence of the Hofstadter sequence</a>, arXiv:2311.13854 [math.NT], 2023.
%H A063882 A. Isgur, R. Lech, S. Moore, S. Tanny, Y. Verberne, and Y. Zhang, <a href="http://dx.doi.org/10.1137/15M1040505">Constructing New Families of Nested Recursions with Slow Solutions</a>, SIAM J. Discrete Math., 30(2), 2016, 1128-1147. (20 pages); DOI:10.1137/15M1040505
%H A063882 Kellie O'Connor Gutman, <a href="http://dx.doi.org/10.1007/BF03026855">V(n) = V(n - V(n - 1)) + V(n - V(n - 4))</a>, The Mathematical Intelligencer, Volume 23, Number 3, Summer 2001, page 50.
%H A063882 <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>
%F A063882 n/2 < a(n) <= n/2 + log_2 (n) - 1 for all n > 6 [Balamohan et al., Proposition 5].
%p A063882 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;
%t A063882 a[1]=a[2]=a[3]=a[4]=1;a[n_]:=a[n]=a[n-a[n-1]]+a[n-a[n-4]];Table[a[n],{n,80}]
%o A063882 (Haskell)
%o A063882 a063882 n = a063882_list !! (n-1)
%o A063882 a063882_list = 1 : 1 : 1 : 1 : zipWith (+)
%o A063882    (map a063882 $ zipWith (-) [5..] a063882_list)
%o A063882    (map a063882 $ zipWith (-) [5..] $ drop 3 a063882_list)
%o A063882 -- _Reinhard Zumkeller_, Dec 08 2011
%Y A063882 Cf. A132157. For partial sums see A129632.
%Y A063882 A136036(n) = a(n+1) - a(n).
%Y A063882 Cf. A063892, A087777.
%Y A063882 Cf. A132174, A132175, A132176, A132177.
%Y A063882 Cf. A202016 (occur only once).
%K A063882 nice,nonn
%O A063882 1,5
%A A063882 Theodor Schlickmann (Theodor.Schlickmann(AT)cec.eu.int), Aug 28 2001
%E A063882 Edited by _N. J. A. Sloane_, Nov 06 2007
%E A063882 Mathematica program corrected by _Harvey P. Dale_, Jan 24 2025