cp's OEIS Frontend

A005374 Hofstadter H-sequence: a(n) = n - a(a(a(n-1))).

%I A005374 M0449 #111 Jul 02 2025 16:01:54
%S A005374 0,1,1,2,3,4,4,5,5,6,7,7,8,9,10,10,11,12,13,13,14,14,15,16,17,17,18,
%T A005374 18,19,20,20,21,22,23,23,24,24,25,26,26,27,28,29,29,30,31,32,32,33,33,
%U A005374 34,35,35,36,37,38,38,39,40,41,41,42,42,43,44,45,45,46,46,47,48,48,49,50
%N A005374 Hofstadter H-sequence: a(n) = n - a(a(a(n-1))).
%C A005374 Rule for constructing the sequence: a(n) = An, where An denotes the Lamé antecessor to (or right shift of) n, which is found by replacing each Lm(i) in the Zeckendorffian expansion (obtained by repeatedly subtracting the largest Lamé number (A000930) you can until nothing remains) by Lm(i-1) (A1=1). For example: 58 = 41 + 13 + 4, so a(58)= 28 + 9 + 3 = 40.
%C A005374 From Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006: (Start)
%C A005374 As is shown on page 137 of Goedel, Escher, Bach, a recursively built tree structure can be obtained from this sequence:
%C A005374   20.21..22..23.24.25.26.27.28
%C A005374   .\./.../.../...\./...\./../
%C A005374   ..14.15..16....17....18..19
%C A005374   ...\./.../..../.......\./
%C A005374   ....10.11...12........13
%C A005374   .....\./.../........./
%C A005374   ......7...8........9.
%C A005374   .......\./......./
%C A005374   ........5......6
%C A005374   .........\.../
%C A005374   ...........4
%C A005374   ........../
%C A005374   .........3
%C A005374   ......../
%C A005374   .......2
%C A005374   ....\./
%C A005374   .....1
%C A005374 To construct the tree: node n is connected to the node a(n) below it:
%C A005374   ...n
%C A005374   ../
%C A005374   a(n)
%C A005374 For example:
%C A005374   ...8
%C A005374   ../
%C A005374   .5
%C A005374 since a(8) = 5. If the nodes of the tree are read from bottom-to-top, left-to-right, we obtain the natural numbers: 1, 2, 3, 4, 5, 6, ...
%C A005374 The tree has a recursive structure, since the following construct
%C A005374   ....../
%C A005374   .....x
%C A005374   ..../
%C A005374   ...x
%C A005374   \./
%C A005374   .x
%C A005374 can be repeatedly added on top of its own ends, to construct the tree from its root: E.g.,
%C A005374   ................../
%C A005374   .................x
%C A005374   ................/
%C A005374   ...............x
%C A005374   ......../...\./
%C A005374   .......x.....x
%C A005374   ....../...../
%C A005374   .....x.....x
%C A005374   ..\./...../
%C A005374   ...x.....x
%C A005374   ....\.../
%C A005374   ......x
%C A005374 (End)
%C A005374 From _Pierre Letouzey_, Feb 20 2025: (Start)
%C A005374 For all n >= 0, A005206(n) <= a(n) <= A005375(n), as proved in Letouzey-Li-Steiner link. Last equality A005206(n) = a(n) occurs at n = 12; last equality a(n) = A005375(n) occurs at n = 18.
%C A005374 For all n >= 0, |a(n)-c*n| < 0.996, where c is the real root of x^3 + x - 1 = 0, c = 0.682327803828019327369483739... Proved in Letouzey link. (End)
%C A005374 The bound for |a(n)-c*n| is improved to 0.862 in Shallit (2025). - _Jeffrey Shallit_, Mar 09 2025
%D A005374 D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 137.
%D A005374 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005374 Reinhard Zumkeller, <a href="/A005374/b005374.txt">Table of n, a(n) for n = 0..10000</a>
%H A005374 Benoit Cloitre, <a href="/A005374/a005374.png">Plot of a(n)-c*n where c=0.6823278...</a>
%H A005374 Larry Ericksen and Peter G. Anderson, <a href="http://www.cs.rit.edu/~pga/k-zeck.pdf">Patterns in differences between rows in k-Zeckendorf arrays</a>, The Fibonacci Quarterly, Vol. 50, No. 1 (February 2012), pp. 11-18.
%H A005374 Nick Hobson, <a href="/A005374/a005374.py.txt">Python program for this sequence</a>
%H A005374 D. R. Hofstadter, <a href="/A006336/a006336_1.pdf">Eta-Lore</a> [Cached copy, with permission]
%H A005374 D. R. Hofstadter, <a href="/A006336/a006336_2.pdf">Pi-Mu Sequences</a> [Cached copy, with permission]
%H A005374 D. R. Hofstadter and N. J. A. Sloane, <a href="/A006336/a006336.pdf">Correspondence, 1977 and 1991</a>
%H A005374 Pierre Letouzey, S. Li and W. Steiner, <a href="https://arxiv.org/abs/2410.00529">Pointwise order of generalized Hofstadter functions G,H and beyond</a>, arXiv:2410.00529 [cs.DM], 2024.
%H A005374 Pierre Letouzey, <a href="https://arxiv.org/abs/2502.12615">Generalized Hofstadter functions G,H and beyond: numeration systems and discrepancy</a> arXiv:2502.12615 [cs.DM], 2025.
%H A005374 Programming Puzzles & Code Golf Stack Exchange, <a href="https://codegolf.stackexchange.com/questions/87364/hofstadter-h-sequence">Hofstadter H-sequence</a>
%H A005374 Jeffrey Shallit, <a href="https://arxiv.org/abs/2503.01026">The Narayana Morphism and Related Words</a>, arXiv:2503.01026 [math.CO], 2025.
%H A005374 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HofstadterH-Sequence.html">Hofstadter H-Sequence</a>
%H A005374 Wikipedia, <a href="http://en.wikipedia.org/wiki/Hofstadter_sequence">Hofstadter sequence</a>
%H A005374 <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>
%H A005374 <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>
%F A005374 Conjecture: a(n) = floor(c*n) + 0 or 1, where c is the real root of x^3+x-1 = 0, c=0.682327803828019327369483739... - _Benoit Cloitre_, Nov 05 2002 [Proved by Letouzey, see Letouzey link. - _Pierre Letouzey_, Feb 20 2025], [Also proved in Shallit (2025). - _Jeffrey Shallit_, Mar 09 2025]
%F A005374 a(n) = A020942(n) - 2*A064105(n) + A064106(n) (e.g. for n = 30 we get 20 = 93 - 2*137 + 201), and a(n) = 2*A020942(n) - A064105(n) - A023443(n) (e.g. for n = 30 we get 20 = 2*93 - 137 - 29). [Corrected by _N. J. A. Sloane_, Apr 29 2024 at the suggestion of _A.H.M. Smeets_.]
%F A005374 Also: a(n) = a(n-1) + 1 if n-1 belongs to sequence A064105-A020942-A000012, a(n-1) otherwise.
%F A005374 Recurrence: a(n) = a(n-1) if n-1 belongs to sequence A020942, a(n-1) + 1 otherwise.
%F A005374 Recurrence for n>=3: a(n) = Lm(k-1) + a(n-Lm(k)), where Lm(n) denotes Lamé sequence A000930(n) (Lm(n) = Lm(n-1) + Lm(n-3)) and k is such that Lm(k)< n <= Lm(k+1). Special case: a(Lm(n)) = Lm(n-1) for n>=1.
%F A005374 For n > 0: a(A136495(n)) = n. - _Reinhard Zumkeller_, Dec 17 2011
%p A005374 A005374 := proc(n) option remember: if n<1 then 0 else n-A005374(A005374(A005374(n-1))) fi end: # Francisco Salinas (franciscodesalinas(AT)hotmail.com), Jan 06 2002
%p A005374 H:=proc(n) option remember; if n=1 then 1 else n-H(H(H(n-1))); fi; end proc;
%t A005374 a[n_]:= a[n]= n - a[a[a[n-1]]]; a[0] = 0; Table[a[n], {n, 0, 73}] (* _Jean-François Alcover_, Jul 28 2011 *)
%o A005374 (Haskell)
%o A005374 a005374 n = a005374_list !! n
%o A005374 a005374_list = 0 : 1 : zipWith (-)
%o A005374    [2..] (map (a005374 . a005374) $ tail a005374_list)
%o A005374 -- _Reinhard Zumkeller_, Dec 17 2011
%o A005374 (PARI) first(m)=my(v=vector(m));v[1]=1;for(i=2,m,v[i]=i-v[v[v[i-1]]]);concat([0],v) \\ _Anders Hellström_, Dec 07 2015
%o A005374 (SageMath)
%o A005374 @CachedFunction # a = A005374
%o A005374 def a(n): return 0 if (n==0) else n - a(a(a(n-1)))
%o A005374 [a(n) for n in range(101)] # _G. C. Greubel_, Nov 14 2022
%Y A005374 Cf. A202340, A202341, A202342.
%K A005374 nonn,nice
%O A005374 0,4
%A A005374 _N. J. A. Sloane_
%E A005374 More terms from _James Sellers_, Jul 12 2000
%E A005374 Additional comments and formulas from Diego Torres (torresvillarroel(AT)hotmail.com), Nov 23 2002