|
%I M0449 #69 Nov 15 2022 02:41:54
%S 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 18,19,20,20,21,22,23,23,24,24,25,26,26,27,28,29,29,30,31,32,32,33,33,
%U 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 Hofstadter H-sequence: a(n) = n - a(a(a(n-1))).
%C 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 From Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006: (Start)
%C As is shown on page 137 of Goedel, Escher, Bach, a recursively built tree structure can be obtained from this sequence:
%C 20.21..22..23.24.25.26.27.28
%C .\./.../.../...\./...\./../
%C ..14.15..16....17....18..19
%C ...\./.../..../.......\./
%C ....10.11...12........13
%C .....\./.../........./
%C ......7...8........9.
%C .......\./......./
%C ........5......6
%C .........\.../
%C ...........4
%C ........../
%C .........3
%C ......../
%C .......2
%C ....\./
%C .....1
%C To construct the tree: node n is connected to the node a(n) below it:
%C ...n
%C ../
%C a(n)
%C For example:
%C ...8
%C ../
%C .5
%C 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 The tree has a recursive structure, since the following construct
%C ....../
%C .....x
%C ..../
%C ...x
%C \./
%C .x
%C can be repeatedly added on top of its own ends, to construct the tree from its root: E.g.,
%C ................../
%C .................x
%C ................/
%C ...............x
%C ......../...\./
%C .......x.....x
%C ....../...../
%C .....x.....x
%C ..\./...../
%C ...x.....x
%C ....\.../
%C ......x (End)
%D D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 137.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Reinhard Zumkeller, <a href="/A005374/b005374.txt">Table of n, a(n) for n = 0..10000</a>
%H Benoit Cloitre, <a href="/A005374/a005374.png">Plot of a(n)-c*n where c=0.6823278...</a>
%H Nick Hobson, <a href="/A005374/a005374.py.txt">Python program for this sequence</a>
%H D. R. Hofstadter, <a href="/A006336/a006336_1.pdf">Eta-Lore</a> [Cached copy, with permission]
%H D. R. Hofstadter, <a href="/A006336/a006336_2.pdf">Pi-Mu Sequences</a> [Cached copy, with permission]
%H D. R. Hofstadter and N. J. A. Sloane, <a href="/A006336/a006336.pdf">Correspondence, 1977 and 1991</a>
%H Programming Puzzles & Code Golf Stack Exchange, <a href="https://codegolf.stackexchange.com/questions/87364/hofstadter-h-sequence">Hofstadter H-sequence</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HofstadterH-Sequence.html">Hofstadter H-Sequence</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Hofstadter_sequence">Hofstadter sequence</a>
%H <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>
%H <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>
%F 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
%F Equals = A020942 - 2*A064105 + A064106 = 2*A020942 - A064105 - A001477. [Daniel Platt points out that there must be an error in this formula, since it fails for n=30: H(30)=20, A020942(30)=93, A064105(30)=131, A064106(30)=186, A001477(30)=30. Hence 20=93-2*131+186=2*93-131-30 <=> 20=17=25. Sep 11 2009]
%F Also: a(n) = a(n-1) + 1 if n-1 belongs to sequence A064105-A020942-A000012, a(n-1) otherwise.
%F Recurrence: a(n) = a(n-1) if n-1 belongs to sequence A020942, a(n-1) + 1 otherwise.
%F 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 For n > 0: a(A136495(n)) = n. - _Reinhard Zumkeller_, Dec 17 2011
%p 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 H:=proc(n) option remember; if n=1 then 1 else n-H(H(H(n-1))); fi; end proc;
%t 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 (Haskell)
%o a005374 n = a005374_list !! n
%o a005374_list = 0 : 1 : zipWith (-)
%o [2..] (map (a005374 . a005374) $ tail a005374_list)
%o -- _Reinhard Zumkeller_, Dec 17 2011
%o (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 (SageMath)
%o @CachedFunction # a = A005374
%o def a(n): return 0 if (n==0) else n - a(a(a(n-1)))
%o [a(n) for n in range(101)] # _G. C. Greubel_, Nov 14 2022
%Y Cf. A202340, A202341, A202342.
%K nonn,nice
%O 0,4
%A _N. J. A. Sloane_
%E More terms from _James A. Sellers_, Jul 12 2000
%E Additional comments and formulas from Diego Torres (torresvillarroel(AT)hotmail.com), Nov 23 2002
|
