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!)
A005374 Hofstadter H-sequence: a(n) = n - a(a(a(n-1))).
(Formerly M0449)
25
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, 18, 19, 20, 20, 21, 22, 23, 23, 24, 24, 25, 26, 26, 27, 28, 29, 29, 30, 31, 32, 32, 33, 33, 34, 35, 35, 36, 37, 38, 38, 39, 40, 41, 41, 42, 42, 43, 44, 45, 45, 46, 46, 47, 48, 48, 49, 50 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
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.
From Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006: (Start)
As is shown on page 137 of Goedel, Escher, Bach, a recursively built tree structure can be obtained from this sequence:
20.21..22..23.24.25.26.27.28
.\./.../.../...\./...\./../
..14.15..16....17....18..19
...\./.../..../.......\./
....10.11...12........13
.....\./.../........./
......7...8........9.
.......\./......./
........5......6
.........\.../
...........4
........../
.........3
......../
.......2
....\./
.....1
To construct the tree: node n is connected to the node a(n) below it:
...n
../
a(n)
For example:
...8
../
.5
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, ...
The tree has a recursive structure, since the following construct
....../
.....x
..../
...x
\./
.x
can be repeatedly added on top of its own ends, to construct the tree from its root: E.g.,
................../
.................x
................/
...............x
......../...\./
.......x.....x
....../...../
.....x.....x
..\./...../
...x.....x
....\.../
......x (End)
REFERENCES
D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 137.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, No. 1 (February 2012), pp. 11-18.
D. R. Hofstadter, Eta-Lore [Cached copy, with permission]
D. R. Hofstadter, Pi-Mu Sequences [Cached copy, with permission]
D. R. Hofstadter and N. J. A. Sloane, Correspondence, 1977 and 1991
Programming Puzzles & Code Golf Stack Exchange, Hofstadter H-sequence
Eric Weisstein's World of Mathematics, Hofstadter H-Sequence
FORMULA
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
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.]
Also: a(n) = a(n-1) + 1 if n-1 belongs to sequence A064105-A020942-A000012, a(n-1) otherwise.
Recurrence: a(n) = a(n-1) if n-1 belongs to sequence A020942, a(n-1) + 1 otherwise.
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.
For n > 0: a(A136495(n)) = n. - Reinhard Zumkeller, Dec 17 2011
MAPLE
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
H:=proc(n) option remember; if n=1 then 1 else n-H(H(H(n-1))); fi; end proc;
MATHEMATICA
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 *)
PROG
(Haskell)
a005374 n = a005374_list !! n
a005374_list = 0 : 1 : zipWith (-)
[2..] (map (a005374 . a005374) $ tail a005374_list)
-- Reinhard Zumkeller, Dec 17 2011
(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
(SageMath)
@CachedFunction # a = A005374
def a(n): return 0 if (n==0) else n - a(a(a(n-1)))
[a(n) for n in range(101)] # G. C. Greubel, Nov 14 2022
CROSSREFS
Sequence in context: A225553 A039733 A179510 * A206767 A071991 A276952
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
More terms from James A. Sellers, Jul 12 2000
Additional comments and formulas from Diego Torres (torresvillarroel(AT)hotmail.com), Nov 23 2002
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 June 21 06:22 EDT 2024. Contains 373540 sequences. (Running on oeis4.)