A005374 -id:A005374 - cp's OEIS frontend

A005185 Hofstadter Q-sequence: a(1) = a(2) = 1; a(n) = a(n-a(n-1)) + a(n-a(n-2)) for n > 2.

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, 12, 12, 12, 16, 14, 14, 16, 16, 16, 16, 20, 17, 17, 20, 21, 19, 20, 22, 21, 22, 23, 23, 24, 24, 24, 24, 24, 32, 24, 25, 30, 28, 26, 30, 30, 28, 32, 30, 32, 32, 32, 32, 40, 33, 31, 38, 35, 33, 39, 40, 37, 38, 40, 39

Offset: 1

Simon Plouffe and N. J. A. Sloane, May 20 1991

Rate of growth is not known. In fact it is not even known if this sequence is defined for all positive n.
Roman Pearce, Aug 29 2014, has computed that a(n) exists for n <= 10^10. - N. J. A. Sloane
a(n) exists for n <= 3*10^10. - M. Eric Carr, Jul 02 2023

			a(18) = 11 because a(17) is 10 and a(16) is 9, so we take a(18 - 10) + a(18 - 9) = a(8) + a(9) = 5 + 6 = 11.

B. W. Conolly, "Meta-Fibonacci sequences," in S. Vajda, editor, Fibonacci and Lucas Numbers and the Golden Section. Halstead Press, NY, 1989, pp. 127-138.
R. K. Guy, Unsolved Problems in Number Theory, Sect. E31.
D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 138.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
S. Vajda, Fibonacci and Lucas Numbers and the Golden Section, Wiley, 1989, see p. 129.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 129.

T. D. Noe and N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Altug Alkan, On a conjecture about generalized Q-recurrence, Open Mathematics, Vol. 16 (2018), pp. 1490-1500.
Altug Alkan, On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures, Complexity (2018) Article ID 8517125.
Altug Alkan, Nathan Fox, and Orhan Ozgur Aybar, On Hofstadter Heart Sequences, Complexity, 2017.
B. Balamohan, A. Kuznetsov, and S. Tanny, On the behavior of a variant of Hofstadter's Q-sequence, J. Integer Sequences, Vol. 10 (2007), #07.7.1.
Thomas Bloom, Problem 422, Erdős Problems.
Paul Bourke, Hofstadter "Q" Series.
Paul Bourke, Hofstadter "Q" Series. [Cached copy, pdf only, with permission]
Paul Bourke, Listen to first 300 terms of this sequence. [Cached copy from the Hofstadter "Q" web page, with permission]
Joseph Callaghan, John J. Chew III, and Stephen M. Tanny, On the behavior of a family of meta-Fibonacci sequences, SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824. See p. 794.
Benoit Cloitre, Plot of a(n)/n - 1/2 for n=1 up to 2^19.
J.-P. Davalan, Douglas Hofstadter's sequences.
Jonathan H. B. Deane and Guido Gentile, A diluted version of the problem of the existence of the Hofstadter sequence, arXiv:2311.13854 [math.NT], 2023.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
Nathan Fox, Linear-Recurrent Solutions to Meta-Fibonacci Recurrences, Part 1 (video), Rutgers Experimental Math Seminar, Oct 01 2015. Part 2 is vimeo.com/141111991.
Nathan Fox, Finding Linear-Recurrent Solutions to Hofstadter-Like Recurrences Using Symbolic Computation, arXiv:1609.06342 [math.NT], 2016.
Nathan Fox, A Slow Relative of Hofstadter's Q-Sequence, arXiv:1611.08244 [math.NT], 2016.
Nathan Fox, A New Approach to the Hofstadter Q-Recurrence, arXiv:1807.01365 [math.NT], 2018.
S. W. Golomb, Discrete chaos: sequences satisfying "strange" recursions, unpublished manuscript, circa 1990 [cached copy, with permission (annotated)].
J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.
R. K. Guy, Letter to N. J. A. Sloane, Sep 25 1986.
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
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.
D. R. Hofstadter, Curious patterns and non-patterns in a family of meta-Fibonacci recursions, Lecture in Doron Zeilberger's Experimental Mathematics Seminar, Rutgers University, April 10 2014; Part 1, Part 2.
D. R. Hofstadter, Plot of first 100 million terms.
Abraham Isgur, Mustazee Rahman, and Stephen Tanny, Solving non-homogeneous nested recursions using trees, Annals of Combinatorics 17.4 (2013): 695-710. See p. 695. - _N. J. A. Sloane_, Apr 16 2014
A. Isgur, R. Lech, S. Moore, S. Tanny, Y. Verberne, and Y. Zhang, Constructing New Families of Nested Recursions with Slow Solutions, SIAM J. Discrete Math., 30(2), 2016, 1128-1147. (20 pages); DOI:10.1137/15M1040505.
Piotr Miska, Bartosz Sobolewski, and Maciej Ulas, Binary sequences meet the Fibonacci sequence, arXiv:2412.11319 [math.NT], 2024. See p. 20.
K. Pinn, Order and chaos in Hofstadter's Q(n) sequence, Complexity, 4:3 (1999), 41-46.
K. Pinn, A chaotic cousin of Conway's recursive sequence, Experimental Mathematics, 9:1 (2000), 55-65.
K. Pinn, A Chaotic Cousin Of Conway's Recursive Sequence, arXiv:cond-mat/9808031 [cond-mat.stat-mech], 1998.
N. J. A. Sloane and Brady Haran, Amazing Graphs III, Numberphile video (2019).
I. Vardi, Email to N. J. A. Sloane, Jun. 1991.
A. M. M. Sharif Ullah, Surface Roughness Modeling Using Q-Sequence, Mathematical and Computational Applications, 2017.
Eric Weisstein's World of Mathematics, Hofstadter's Q-Sequence.
Wikipedia, Hofstadter sequence.
Pedro Zanetti, C++ code snippet for this sequence.
Index entries for sequences from "Goedel, Escher, Bach"
Index entries for Hofstadter-type sequences

Cf. A004001, A005206, A005374, A005375, A005378.
Cf. A005379, A070867, A226222, A239913, A284019.
Cf. A081827 (first differences).
Cf. A226244, A226245 (record values and where they occur).
See A244477 for a different start.

#include 
#define LIM 20
int Qa[LIM];
int Q(int n){if (n==1 || n==2){return 1;} else{return Qa[n-Qa[n-1]]+Qa[n-Qa[n-2]];}}
int main(){int i;printf("n\tQ\n");for(i=1; iGonzalo Ciruelos, Aug 01 2013

a005185 n = a005185_list !! (n-1)
a005185_list = 1 : 1 : zipWith (+)
   (map a005185 $ zipWith (-) [3..] a005185_list)
   (map a005185 $ zipWith (-) [3..] $ tail a005185_list)
-- Reinhard Zumkeller, Jun 02 2013, Sep 15 2011

I:=[1,1]; [n le 2 select I[n] else Self(n-Self(n-1))+Self(n-Self(n-2)): n in [1..90]]; // Vincenzo Librandi, Aug 08 2014

A005185 := proc(n) option remember;
    if n<=2 then 1
    elif n > procname(n-1) and n > procname(n-2) then
        RETURN(procname(n-procname(n-1))+procname(n-procname(n-2)));
    else
        ERROR(" died at n= ", n);
    fi; end proc;
# More generally, the following defines the Hofstadter-Huber sequence Q(r,s) - N. J. A. Sloane, Apr 15 2014
r:=1; s:=2;
a:=proc(n) option remember; global r,s;
if n <= s then  1
else
    if (a(n-r) <= n) and (a(n-s) <= n) then
    a(n-a(n-r))+a(n-a(n-s));
    else lprint("died with n =",n); return (-1);
    fi; fi; end;
[seq(a(n), n=1..100)];

a[1]=a[2]=1; a[n_]:= a[n]= a[n -a[n-1]] + a[n -a[n-2]]; Table[ a[n], {n,70}]

q:=proc(n) option remember; begin if n<=2 then 1 else q(n-q(n-1))+q(n-q(n-2)) end_if; end_proc: q(i)$i=1..100; // Zerinvary Lajos, Apr 03 2007

{a(n)= local(A); if(n<1, 0, A=vector(n,k,1); for(k=3, n, A[k]= A[k-A[k-1]]+ A[k-A[k-2]]); A[n])} /* Michael Somos, Jul 16 2007 */

from functools import lru_cache
@lru_cache(maxsize=None)
def a(n):
    if n < 3: return 1
    return a(n - a(n-1)) + a(n - a(n-2))
print([a(n) for n in range(1, 75)]) # Michael S. Branicky, Jul 26 2021

@CachedFunction
def a(n):
    if (n<3): return 1
    else: return a(n -a(n-1)) + a(n -a(n-2))
[a(n) for n in (1..70)] # G. C. Greubel, Feb 13 2020

(define q (lambda (n) (cond ( (eqv? n 0) 1) ( (eqv? n 1) 1) ( #t (+ (q (- n (q (- n 1)))) (q (- n (q (- n 2)))))))))

;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization
(definec (A005185 n) (if (<= n 2) 1 (+ (A005185 (- n (A005185 (- n 1)))) (A005185 (- n (A005185 (- n 2)))))))
;; Antti Karttunen, Mar 22 2017

A005206 Hofstadter G-sequence: a(0) = 0; a(n) = n - a(a(n-1)) for n > 0.

Original entry on oeis.org

0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 33, 34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47

Offset: 0

N. J. A. Sloane

Rule for finding n-th term: a(n) = An, where An denotes the Fibonacci antecedent to (or right shift of) n, which is found by replacing each F(i) in the Zeckendorf expansion (obtained by repeatedly subtracting the largest Fibonacci number you can until nothing remains) by F(i-1) (A1=1). For example: 58 = 55 + 3, so a(58) = 34 + 2 = 36. - Diego Torres (torresvillarroel(AT)hotmail.com), Nov 24 2002
From Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006: (Start)
A recursively built tree structure can be obtained from the sequence (see Hofstadter, p. 137):
  14  15  16  17  18  19  20  21
    \ /   /     \ /     \ /   /
     9  10      11      12  13
      \ /       /         \ /
       6       7           8
        \     /           /
         \   /           /
          \ /           /
           4           5
            \         /
             \       /
              \     /
               \   /
                \ /
                 3
                /
               2
            \ /
             1
To construct the tree: node n is connected with the node a(n) below
     n
    /
  a(n)
For example, since a(7) = 4:
    7
   /
  4
If the nodes of the tree are read from bottom to top, left to right, one obtains the positive integers: 1, 2, 3, 4, 5, 6, ... The tree has a recursive structure, since the construct
      /
     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
When moving from a node to a lower connected node, one is moving to the parent. Parent node of n: floor((n+1)/tau). Left child of n: floor(tau*n). Right child of n: floor(tau*(n+1))-1 where tau=(1+sqrt(5))/2. (See the Sillke link.)
(End)
The number n appears A001468(n) times; A001468(n) = floor((n+1)*Phi) - floor(n*Phi) with Phi = (1 + sqrt 5)/2. - Philippe Deléham, Sep 22 2005
Number of positive Wythoff A-numbers A000201 not exceeding n. - N. J. A. Sloane, Oct 09 2006
Number of positive Wythoff B-numbers < A000201(n+1). - N. J. A. Sloane, Oct 09 2006
From Bernard Schott, Apr 23 2022: (Start)
Properties coming from the 1st problem proposed during the 45th Czech and Slovak Mathematical Olympiad in 1996 (see IMO Compendium link):
-> a(n) >= a(n-1) for any positive integer n,
-> a(n) - a(n-1) belongs to {0,1},
-> No integer n exists such that a(n-1) = a(n) = a(n+1). (End)
For n >= 1, find n in the Wythoff array (A035513). a(n) is the number that precedes n in its row, using the preceding column of the extended Wythoff array (A287870) if n is at the start of the (unextended) row. - Peter Munn, Sep 17 2022
See my 2023 publication on Hofstadter's G-sequence for a proof of the equality of (a(n)) with the sequence A073869. - Michel Dekking, Apr 28 2024
From Michel Dekking, Dec 16 2024: (Start)
Focus on the pairs of duplicate values, i.e., the pairs (a(n-1),a(n)) with a(n-1) = a(n). Directly from Theorem 1 in Kimberling and Stolarsky (2016) one derives that the m-th pair of duplicate values (a(n-1),a(n)) occurs at n = U(m), where U = 2,5,7,10,... is the upper Wythoff sequence. For example, (3,3) is the second pair, and occurs at U(2) = 5.
This property can be used to give a simple construction for (a(n)) -- ignoring the superfluous a(0) = 0.
Let 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,... be the sequence of positive natural numbers. Double all the elements of the lower Wythoff sequence (L(n)) = 1,3,4,6,8,9,11,....:
     (x(n)) := 1,1, 2, 3,3, 4,4, 5, 6,6, 7, 8,8, 9,9, 10,....
Claim: the result is (a(n)). This follows since because of the doubling, the m-th pair of duplicate values (a(n-1),a(n)) occurs in x at n = L(m) + m = U(m). The second equality by a well-known formula.
It follows from this by Theorem 1 of K&S, that a(n-1) = x(n-1), and a(n) = x(n) if n = U(m), for all m. But since L and U are complementary sequences, a(n) = x(n) will also hold if n = L(k), for all k. For example, L(4) = 6, and a(6) = x(6) = 4.
Corollary: for n >= 2 replace every pair of duplicate values (a(n-1),a(n)) by 0, and all the remaining elements of (a(n)) by 1. Then the result is the Fibonacci word 0,1,0,0,1,0,1,0,0... This is implied by the fact that L gives the positions of the 0s, and U the position of the 1's in the Fibonacci word. (End)
For all n >= 0, a(n) <= A005374(n), as proved in Letouzey-Li-Steiner link. Last equality occurs at n = 12, while a(n) < A005374(n) afterwards. - Pierre Letouzey, Feb 20 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).

N. J. A. Sloane and T. D. Noe, Table of n, a(n) for n = 0..20000 (the first 1000 terms were found by T. D. Noe)
L. Carlitz, Fibonacci Representations, Fibonacci Quarterly, volume 6, number 4, October 1968, pages 193-220. a(n) = e(n) at equation 1.10 or 2.11 and see equation 3.8 recurrence.
M. Celaya and F. Ruskey, Morphic Words and Nested Recurrence Relations, arXiv preprint arXiv:1307.0153 [math.CO], 2013.
M. Celaya and F. Ruskey, Another Property of Only the Golden Ratio, American Mathematical Monthly, Problem 11651, solutions volume 121, number 6, June-July 2014, pages 549-556.
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
F. M. Dekking, On Hofstadter's G-sequence, Journal of Integer Sequences 26 (2023), Article 23.9.2, 1-11.
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. Gault and M. Clint, "Curiouser and curiouser" said Alice. Further reflections on an interesting recursive function, Internat. J. Computer Math., 26 (1988), 35-43. Also annotated scanned copy.
Martin Griffiths, A formula for an infinite family of Fibonacci-word sequences, Fib. Q., 56 (2018), 75-80.
H. W. Gould, J. B. Kim and V. E. Hoggatt, Jr., Sequences associated with t-ary coding of Fibonacci's rabbits, Fib. Quart., 15 (1977), 311-318.
Vincent Granville and Jean-Paul Rasson, A strange recursive relation, J. Number Theory 30 (1988), no. 2, 238--241. MR0961919(89j:11014).
J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.
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
The IMO Compendium, Problem 1, 45th Czech and Slovak Mathematical Olympiad 1996.
Clark Kimberling and K. B. Stolarsky, Slow Beatty sequences, devious convergence, and partitional divergence, Amer. Math. Monthly, 123 (No. 2, 2016), 267-273.
Pierre Letouzey, Hofstadter's problem for curious readers, Technical Report, 2015.
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.
Mustazee Rahman, A Combinatorial interpretation of Hofstadter's G-sequence, arXiv:1105.1718 [math.CO], 2011-2013.
B. Schoenmakers, A tight lower bound for top-down skew heaps, Information Processing Letters, 61(5): 279-284, 14 March 1997.
Torsten Sillke, Floor Recurrences
Th. Stoll, On Hofstadter's married functions, Fib. Q., 46/47 (2008/2009), 62-67. - _N. J. A. Sloane_, May 30 2009
Eric Weisstein's World of Mathematics, Hofstadter G-Sequence
Wikipedia, Hofstadter sequence
Index entries for Hofstadter-type sequences
Index entries for sequences from "Goedel, Escher, Bach"
Index to sequences related to Olympiads.

Apart from initial terms, same as A060143. Cf. A123070.
a(n):=Sum{k=1..n} h(k), n >= 1, with h(k):= A005614(k-1) and a(0):=0.
Cf. A060144, A019446, A072649, A213676, A000201.
Cf. A035513, A287870.

a005206 n = a005206_list !! n
a005206_list = 0 : zipWith (-) [1..] (map a005206 a005206_list)
-- Reinhard Zumkeller, Feb 02 2012, Aug 07 2011

a005206 = sum . zipWith (*) a000045_list . a213676_row . a000201 . (+ 1)
-- Reinhard Zumkeller, Mar 10 2013

[Floor((n+1)*(1+Sqrt(5))/2)-n-1: n in [0..80]]; // Vincenzo Librandi, Nov 19 2016

H:=proc(n) option remember; if n=0 then 0 elif n=1 then 1 else n-H(H(n-1)); fi; end proc: seq(H(n),n=0..76);

a[0] = 0; a[n_] := a[n] = n - a[a[n - 1]]; Array[a, 77, 0]
(* Second program: *)
Fold[Append[#1, #2 - #1[[#1[[#2]] + 1 ]] ] &, {0}, Range@ 76] (* Michael De Vlieger, Nov 13 2017 *)

first(n)=my(v=vector(n)); v[1]=1; for(k=2,n, v[k]=k-v[v[k-1]]); concat(0,v) \\ Charles R Greathouse IV, Sep 02 2015

from math import isqrt
def A005206(n): return (n+1+isqrt(5*(n+1)**2)>>1)-n-1 # Chai Wah Wu, Aug 09 2022

a(n) = floor((n+1)*tau) - n - 1 = A000201(n+1)-n-1, where tau = (1+sqrt(5))/2; or a(n) = floor(sigma*(n+1)) where sigma = (sqrt(5)-1)/2.
a(0)=0, a(1)=1, a(n) = n - a(floor(n/tau)). - Benoit Cloitre, Nov 27 2002
a(n) = A019446(n) - 1. - Reinhard Zumkeller, Feb 02 2012
a(n) = n - A060144(n+1). - Reinhard Zumkeller, Apr 07 2012
a(n) = Sum_{k=1..A072649(m)} A000045(m)*A213676(m,k): m=A000201(n+1). - Reinhard Zumkeller, Mar 10 2013
From Pierre Letouzey, Sep 09 2015: (Start)
a(n + a(n)) = n.
a(n) + a(a(n+1) - 1) = n.
a(0) = 0, a(n+1) = a(n) + d(n) and d(0) = 1, d(n+1)=1-d(n)*d(a(n)). (End)
a(n) = A293688(n)/(n+1) for n >= 0 (conjectured). - Enrique Navarrete, Oct 15 2017
A generalization of Diego Torres's 2002 comment as a formula: if n = Sum_{i in S} A000045(i+1), where S is a set of positive integers, then a(n) = Sum_{i in S} A000045(i). - Peter Munn, Sep 28 2022
Conjectures from Chunqing Liu, Aug 01 2023: (Start)
a(A000201(n)-1) = n-1.
a(A001950(n)-1) = a(A001950(n)) = A000201(n). (End)

a(0) = 0 added in the Name by Bernard Schott, Apr 23 2022

A136495 Solution of the complementary equation b(n)=a(a(n))+n.

Original entry on oeis.org

1, 3, 4, 5, 7, 9, 10, 12, 13, 14, 16, 17, 18, 20, 22, 23, 24, 26, 28, 29, 31, 32, 33, 35, 37, 38, 40, 41, 42, 44, 45, 46, 48, 50, 51, 53, 54, 55, 57, 58, 59, 61, 63, 64, 65, 67, 69, 70, 72, 73, 74, 76, 77, 78, 80, 82, 83, 84, 86, 88, 89, 91, 92, 93, 95, 97, 98, 100, 101, 102

Offset: 1

Clark Kimberling, Jan 01 2008

nonn

b = 1 + (column 1 of Z) = 1 + A020942. The pair (a,b) also satisfy the following complementary equations: b(n)=a(a(a(n)))+1; a(b(n))=a(n)+b(n); b(a(n))=a(n)+b(n)-1; (and others).
Let Z = (3rd order Zeckendorf array) = A136189. Then a = ordered union of columns 1,3,4,6,7,9,10,12,13,... of Z, b = ordered union of columns 2,5,8,11,14,... of Z.
Position of the n-th occurrence of either 1 or 3 in A105083(n-1) for n>=1. - Jeffrey Shallit, Mar 08 2025

			b(1) = a(a(1))+1 = a(1)+1 = 1+1 = 2;
b(2) = a(a(2))+2 = a(3)+2 = 4+2 = 6;
b(3) = a(a(3))+3 = a(4)+3 = 5+3 = 8;
b(4) = a(a(4))+4 = a(5)+4 = 7+4 = 11.

Clark Kimberling and Peter J. C. Moses, Complementary equations and Zeckendorf arrays, in Applications of Fibonacci Numbers, vol.10, Proceedings of the Thirteenth International Conference on Fibonacci Numbers and Their Applications, William Webb, editor, Congressus Numerantium, Winnipeg, Manitoba 201 (2010) 161-178.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.
Eric Weisstein's World of Mathematics, Hofstadter H-Sequence.

Cf. A005374, A020942, A035513, A105083, A136189, A136496.

import Data.List (elemIndex)
import Data.Maybe (fromJust)
a136495 n = (fromJust $ n `elemIndex` tail a005374_list) + 1
-- Reinhard Zumkeller, Dec 17 2011

A005374(a(n)) = n. - Reinhard Zumkeller, Dec 17 2011

a(n) = A005374(A005374(n-1)) + n. - Alan Michael Gómez Calderón, Jul 16 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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Formula

A202340 Number of times n occurs in Hofstadter H-sequence A005374.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A154951 Found by taking the tree defined by the Hofstadter H-sequence (A005374), mirroring it left to right and relabeling the nodes so they increase left to right. a(n) is the parent node of node n in the tree so constructed.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

A082401 a(n)=A005374(n)-floor(r*n) where r is the positive root of x^3+x-1=0.

Views

Author

Keywords

Formula

A005185 Hofstadter Q-sequence: a(1) = a(2) = 1; a(n) = a(n-a(n-1)) + a(n-a(n-2)) for n > 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Haskell

Magma

Maple

Mathematica

MuPAD

PARI

Python

Sage

Scheme

Scheme

A005206 Hofstadter G-sequence: a(0) = 0; a(n) = n - a(a(n-1)) for n > 0.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Haskell

Magma

Maple

Mathematica

PARI