|
| |
|
|
A005374
|
|
Hofstadter H-sequence: a(n)=n-a(a(a(n-1))).
(Formerly M0449)
|
|
15
|
|
|
|
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 of construction for the sequence: a(n) = An, where An denotes the Lam{\'}e 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{\'}e 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.
Comments 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
|
_Reinhard Zumkeller_, Table of n, a(n) for n = 0..10000
Nick Hobson, Python program for this sequence
Eric Weisstein's World of Mathematics, Hofstadter H-Sequence
Wikipedia, Hofstadter sequence
Index entries for Hofstadter-type sequences
Index entries for sequences from "Goedel, Escher, Bach"
|
|
|
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
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]
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{\'e} 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: # from 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}] (* From 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
|
|
|
CROSSREFS
|
Cf. A202340, A202341, A202342.
Sequence in context: A225553 A039733 A179510 * A206767 A071991 A096336
Adjacent sequences: A005371 A005372 A005373 * A005375 A005376 A005377
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms from James A. Sellers, Jul 12 2000
Additional comments and formulae from Diego Torres (torresvillarroel(AT)hotmail.com), Nov 23 2002
|
|
|
STATUS
|
approved
|
| |
|
|
