login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Benoit Cloitre, Plot of a(n)-c*n where c=0.6823278...

Nick Hobson, Python program for this sequence

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

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é 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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 23 04:28 EST 2014. Contains 249839 sequences.