A202340 -id:A202340 - cp's OEIS frontend

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

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

Offset: 0

N. J. A. Sloane

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)
From Pierre Letouzey, Feb 20 2025: (Start)
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.
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)
The bound for |a(n)-c*n| is improved to 0.862 in Shallit (2025). - Jeffrey Shallit, Mar 09 2025

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).

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Benoit Cloitre, Plot of a(n)-c*n where c=0.6823278...
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.
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
Pierre Letouzey, S. Li and W. Steiner, Pointwise order of generalized Hofstadter functions G,H and beyond, arXiv:2410.00529 [cs.DM], 2024.
Pierre Letouzey, Generalized Hofstadter functions G,H and beyond: numeration systems and discrepancy arXiv:2502.12615 [cs.DM], 2025.
Programming Puzzles & Code Golf Stack Exchange, Hofstadter H-sequence
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.
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"

Cf. A202340, A202341, A202342.

a005374 n = a005374_list !! n
a005374_list = 0 : 1 : zipWith (-)
   [2..] (map (a005374 . a005374) $ tail a005374_list)
-- Reinhard Zumkeller, Dec 17 2011

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;

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 *)

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

@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

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

More terms from James Sellers, Jul 12 2000

Additional comments and formulas from Diego Torres (torresvillarroel(AT)hotmail.com), Nov 23 2002

A202342 Numbers occurring exactly twice in Hofstadter H-sequence A005374.

Original entry on oeis.org

1, 4, 5, 7, 10, 13, 14, 17, 18, 20, 23, 24, 26, 29, 32, 33, 35, 38, 41, 42, 45, 46, 48, 51, 54, 55, 58, 59, 61, 64, 65, 67, 70, 73, 74, 77, 78, 80, 83, 84, 86, 89, 92, 93, 95, 98, 101, 102, 105, 106, 108, 111, 112, 114, 117, 120, 121, 123, 126, 129, 130, 133

Offset: 1

Reinhard Zumkeller, Dec 17 2011

nonn

Position of the n-th occurrence of the digit 1 in A105083(n-1) for n>=1. - Jeffrey Shallit, Mar 08 2025

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
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.
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.
Eric Weisstein's World of Mathematics, Hofstadter H-Sequence.
Wikipedia, Hofstadter sequence
Index entries for Hofstadter-type sequences

Cf. A005374, A105083, A202340, A136495, A136496, A202341 (complement).

import Data.List (elemIndices)
a202342 n = a202342_list !! (n-1)
a202342_list = elemIndices 2 a202340_list

A202340(a(n)) = 2.
a(n) = A005374(A136496(n)). - Alan Michael Gómez Calderón, Dec 22 2024
a(n) = A136495(A136495(n)). - Alan Michael Gómez Calderón, Jan 06 2025

A105083 Trajectory of 1 under the morphism 1 -> 12, 2 -> 3, 3 -> 1.

Original entry on oeis.org

1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2

Offset: 0

Roger L. Bagula, Apr 06 2005

nonn

Aresh Pourkavoos, Table of n, a(n) for n = 0..10000
P. Arnoux and E. Harriss, What is a Rauzy Fractal?, Notices Amer. Math. Soc., 61 (No. 7, 2014), 768-770, also p. 704 and front cover.
Marcy Barge and Jaroslaw Kwapisz, Geometric theory of unimodular Pisot substitutions, Amer. J. Math. 128 (2006), no. 5, 1219--1282. MR2262174 (2007m:37039). - _N. J. A. Sloane_, Aug 06 2014
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.
Victor F. Sirvent and Yang Wang, Self-Affine Tiling via Substitution Dynamical Systems and Rauzy Fractals, Pac. J. Math., 206 (2002), 465-485. See Example 2.2 and Figure 2 pp. 474-475.
Index entries for sequences that are fixed points of mappings

Cf. A005374, A073058, A092782, A202340, A245553, A245554, A000930.

Nest[ Function[ l, {Flatten[(l /. {1 -> {1, 2}, 2 -> {3}, 3 -> {1}})] }], {1}, 12]

N_TERMS=10000
def a():
  # Index of the current term
  n = 0
  # Stores the place values of the greedy representation of n,
  # minus two since A000930 begins with duplicate ones.
  places = []
  # Edge case: a(0)=1.
  yield 0, 1
  while True:
    n += 1
    # Add A000930(2+0)=1 to the representation of n
    places.append(0)
    # Apply carryover rule for as long as necessary:
    # if places contains n+2 and n,
    # both terms are replaced by n+3.
    while len(places) > 1 and places[-2] <= places[-1]+2:
      places.pop()
      places[-1] += 1
    # Look at the smallest term to decide a(n)
    an = 1 if places[-1] > 1 else places[-1]+2
    yield n, an
# Asymptotic behavior is O(log(n)*log(log(n))) memory
# and O(n) time to generate the first n terms,
# although a term may take as long as O(log(n)).
for n, an in a():
  print(n, an)
  if (n >= N_TERMS):
    break
# Aresh Pourkavoos, Jan 26 2021

From Aresh Pourkavoos, Jan 26 2021: (Start)
Limit S(infinity) of the following strings: S(0) = 2, S(1) = 1, S(2) = 0, S(n+3) = S(n+2)S(n). S(n) has length A000930(n).
Individual terms of a(n) may also be found by greedily writing n as a sum of entries of A000930. a(n) is 2 if the smallest term is 1, 3 if the smallest term is 2, and 1 otherwise.
(End)
a(n) = A005374(n+1) - A005374(n) - 2*(A202340(n+1) - 2). - Alan Michael Gómez Calderón, Jul 19 2025

Edited by N. J. A. Sloane, Oct 10 2007 and Aug 03 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A202342 Numbers occurring exactly twice in Hofstadter H-sequence A005374.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Formula

A105083 Trajectory of 1 under the morphism 1 -> 12, 2 -> 3, 3 -> 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A202341 Numbers occurring exactly once in Hofstadter H-sequence A005374.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell