A202014 -id:A202014 - cp's OEIS frontend

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

Offset: 1

Theodor Schlickmann (Theodor.Schlickmann(AT)cec.eu.int), Aug 28 2001

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]

T. D. Noe and N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Altug Alkan, On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures, Complexity (2018) Article ID 8517125.
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.
Index entries for Hofstadter-type sequences

Cf. A132157. For partial sums see A129632.
A136036(n) = a(n+1) - a(n).
Cf. A063892, A087777.
Cf. A132174, A132175, A132176, A132177.
Cf. A202016 (occur only once).

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

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;

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}]

n/2 < a(n) <= n/2 + log_2 (n) - 1 for all n > 6 [Balamohan et al., Proposition 5].

Edited by N. J. A. Sloane, Nov 06 2007

Mathematica program corrected by Harvey P. Dale, Jan 24 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions