This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A005206 M0436 #268 Apr 21 2025 02:25:44
%S A005206 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,
%T A005206 17,18,19,19,20,21,21,22,22,23,24,24,25,25,26,27,27,28,29,29,30,30,31,
%U A005206 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
%N A005206 Hofstadter G-sequence: a(0) = 0; a(n) = n - a(a(n-1)) for n > 0.
%C A005206 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
%C A005206 From Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006: (Start)
%C A005206 A recursively built tree structure can be obtained from the sequence (see Hofstadter, p. 137):
%C A005206 14 15 16 17 18 19 20 21
%C A005206 \ / / \ / \ / /
%C A005206 9 10 11 12 13
%C A005206 \ / / \ /
%C A005206 6 7 8
%C A005206 \ / /
%C A005206 \ / /
%C A005206 \ / /
%C A005206 4 5
%C A005206 \ /
%C A005206 \ /
%C A005206 \ /
%C A005206 \ /
%C A005206 \ /
%C A005206 3
%C A005206 /
%C A005206 2
%C A005206 \ /
%C A005206 1
%C A005206 To construct the tree: node n is connected with the node a(n) below
%C A005206 n
%C A005206 /
%C A005206 a(n)
%C A005206 For example, since a(7) = 4:
%C A005206 7
%C A005206 /
%C A005206 4
%C A005206 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
%C A005206 /
%C A005206 x
%C A005206 \ /
%C A005206 x
%C A005206 can be repeatedly added on top of its own ends, to construct the tree from its root: e.g.,
%C A005206 /
%C A005206 x
%C A005206 / \ /
%C A005206 x x
%C A005206 \ / /
%C A005206 x x
%C A005206 \ /
%C A005206 \ /
%C A005206 x
%C A005206 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.)
%C A005206 (End)
%C A005206 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
%C A005206 Number of positive Wythoff A-numbers A000201 not exceeding n. - _N. J. A. Sloane_, Oct 09 2006
%C A005206 Number of positive Wythoff B-numbers < A000201(n+1). - _N. J. A. Sloane_, Oct 09 2006
%C A005206 From _Bernard Schott_, Apr 23 2022: (Start)
%C A005206 Properties coming from the 1st problem proposed during the 45th Czech and Slovak Mathematical Olympiad in 1996 (see IMO Compendium link):
%C A005206 -> a(n) >= a(n-1) for any positive integer n,
%C A005206 -> a(n) - a(n-1) belongs to {0,1},
%C A005206 -> No integer n exists such that a(n-1) = a(n) = a(n+1). (End)
%C A005206 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
%C A005206 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
%C A005206 From _Michel Dekking_, Dec 16 2024: (Start)
%C A005206 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.
%C A005206 This property can be used to give a simple construction for (a(n)) -- ignoring the superfluous a(0) = 0.
%C A005206 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,....:
%C A005206 (x(n)) := 1,1, 2, 3,3, 4,4, 5, 6,6, 7, 8,8, 9,9, 10,....
%C A005206 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.
%C A005206 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.
%C A005206 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)
%C A005206 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 A005206 D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 137.
%D A005206 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005206 N. J. A. Sloane and T. D. Noe, <a href="/A005206/b005206.txt">Table of n, a(n) for n = 0..20000</a> (the first 1000 terms were found by T. D. Noe)
%H A005206 L. Carlitz, <a href="https://fq.math.ca/Scanned/6-4/carlitz.pdf">Fibonacci Representations</a>, 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.
%H A005206 M. Celaya and F. Ruskey, <a href="http://arxiv.org/abs/1307.0153">Morphic Words and Nested Recurrence Relations</a>, arXiv preprint arXiv:1307.0153 [math.CO], 2013.
%H A005206 M. Celaya and F. Ruskey, <a href="https://www.jstor.org/stable/10.4169/amer.math.monthly.121.06.549">Another Property of Only the Golden Ratio</a>, American Mathematical Monthly, Problem 11651, solutions volume 121, number 6, June-July 2014, pages 549-556.
%H A005206 F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.html">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
%H A005206 F. M. Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Dekking2/dek9.html">On Hofstadter's G-sequence</a>, Journal of Integer Sequences 26 (2023), Article 23.9.2, 1-11.
%H A005206 Larry Ericksen and Peter G. Anderson, <a href="http://www.cs.rit.edu/~pga/k-zeck.pdf">Patterns in differences between rows in k-Zeckendorf arrays</a>, The Fibonacci Quarterly, Vol. 50, No. 1 (February 2012), pp. 11-18.
%H A005206 D. Gault and M. Clint, <a href="http://dx.doi.org/10.1080/00207168808803682">"Curiouser and curiouser" said Alice. Further reflections on an interesting recursive function</a>, Internat. J. Computer Math., 26 (1988), 35-43. Also <a href="/A005206/a005206.pdf">annotated scanned copy</a>.
%H A005206 Martin Griffiths, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/56-1/GriffithsmgFibWordSeq121517.pdf">A formula for an infinite family of Fibonacci-word sequences</a>, Fib. Q., 56 (2018), 75-80.
%H A005206 H. W. Gould, J. B. Kim and V. E. Hoggatt, Jr., <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/15-4/gould.pdf">Sequences associated with t-ary coding of Fibonacci's rabbits</a>, Fib. Quart., 15 (1977), 311-318.
%H A005206 Vincent Granville and Jean-Paul Rasson, <a href="http://dx.doi.org/10.1016/0022-314X(88)90020-0">A strange recursive relation</a>, J. Number Theory 30 (1988), no. 2, 238--241. MR0961919(89j:11014).
%H A005206 J. Grytczuk, <a href="http://dx.doi.org/10.1016/j.disc.2003.10.022">Another variation on Conway's recursive sequence</a>, Discr. Math. 282 (2004), 149-161.
%H A005206 Nick Hobson, <a href="/A005206/a005206.py.txt">Python program for this sequence</a>
%H A005206 D. R. Hofstadter, <a href="/A006336/a006336_1.pdf">Eta-Lore</a> [Cached copy, with permission]
%H A005206 D. R. Hofstadter, <a href="/A006336/a006336_2.pdf">Pi-Mu Sequences</a> [Cached copy, with permission]
%H A005206 D. R. Hofstadter and N. J. A. Sloane, <a href="/A006336/a006336.pdf">Correspondence, 1977 and 1991</a>
%H A005206 The IMO Compendium, <a href="https://imomath.com/othercomp/Czs/CzsMO96.pdf">Problem 1</a>, 45th Czech and Slovak Mathematical Olympiad 1996.
%H A005206 Clark Kimberling and K. B. Stolarsky, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.123.3.267">Slow Beatty sequences, devious convergence, and partitional divergence</a>, Amer. Math. Monthly, 123 (No. 2, 2016), 267-273.
%H A005206 Pierre Letouzey, <a href="http://hal.inria.fr/hal-01195587">Hofstadter's problem for curious readers</a>, Technical Report, 2015.
%H A005206 Pierre Letouzey, S. Li and W. Steiner, <a href="https://arxiv.org/abs/2410.00529">Pointwise order of generalized Hofstadter functions G,H and beyond</a>, arXiv:2410.00529 [cs.DM], 2024.
%H A005206 Pierre Letouzey, <a href="https://arxiv.org/abs/2502.12615">Generalized Hofstadter functions G,H and beyond: numeration systems and discrepancy</a> arXiv:2502.12615 [cs.DM], 2025.
%H A005206 Mustazee Rahman, <a href="http://arxiv.org/abs/1105.1718">A Combinatorial interpretation of Hofstadter's G-sequence</a>, arXiv:1105.1718 [math.CO], 2011-2013.
%H A005206 B. Schoenmakers, <a href="http://www.win.tue.nl/~berry/papers/lowskew.pdf">A tight lower bound for top-down skew heaps</a>, Information Processing Letters, 61(5): 279-284, 14 March 1997.
%H A005206 Torsten Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/floor-recurrence">Floor Recurrences</a>
%H A005206 Th. Stoll, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/46_47-1/Stoll_11-08.pdf">On Hofstadter's married functions</a>, Fib. Q., 46/47 (2008/2009), 62-67. - _N. J. A. Sloane_, May 30 2009
%H A005206 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HofstadterG-Sequence.html">Hofstadter G-Sequence</a>
%H A005206 Wikipedia, <a href="http://en.wikipedia.org/wiki/Hofstadter_sequence">Hofstadter sequence</a>
%H A005206 <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>
%H A005206 <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>
%H A005206 <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.
%F A005206 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.
%F A005206 a(0)=0, a(1)=1, a(n) = n - a(floor(n/tau)). - _Benoit Cloitre_, Nov 27 2002
%F A005206 a(n) = A019446(n) - 1. - _Reinhard Zumkeller_, Feb 02 2012
%F A005206 a(n) = n - A060144(n+1). - _Reinhard Zumkeller_, Apr 07 2012
%F A005206 a(n) = Sum_{k=1..A072649(m)} A000045(m)*A213676(m,k): m=A000201(n+1). - _Reinhard Zumkeller_, Mar 10 2013
%F A005206 From _Pierre Letouzey_, Sep 09 2015: (Start)
%F A005206 a(n + a(n)) = n.
%F A005206 a(n) + a(a(n+1) - 1) = n.
%F A005206 a(0) = 0, a(n+1) = a(n) + d(n) and d(0) = 1, d(n+1)=1-d(n)*d(a(n)). (End)
%F A005206 a(n) = A293688(n)/(n+1) for n >= 0 (conjectured). - _Enrique Navarrete_, Oct 15 2017
%F A005206 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
%F A005206 Conjectures from _Chunqing Liu_, Aug 01 2023: (Start)
%F A005206 a(A000201(n)-1) = n-1.
%F A005206 a(A001950(n)-1) = a(A001950(n)) = A000201(n). (End)
%p A005206 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);
%t A005206 a[0] = 0; a[n_] := a[n] = n - a[a[n - 1]]; Array[a, 77, 0]
%t A005206 (* Second program: *)
%t A005206 Fold[Append[#1, #2 - #1[[#1[[#2]] + 1 ]] ] &, {0}, Range@ 76] (* _Michael De Vlieger_, Nov 13 2017 *)
%o A005206 (Haskell)
%o A005206 a005206 n = a005206_list !! n
%o A005206 a005206_list = 0 : zipWith (-) [1..] (map a005206 a005206_list)
%o A005206 -- _Reinhard Zumkeller_, Feb 02 2012, Aug 07 2011
%o A005206 (Haskell)
%o A005206 a005206 = sum . zipWith (*) a000045_list . a213676_row . a000201 . (+ 1)
%o A005206 -- _Reinhard Zumkeller_, Mar 10 2013
%o A005206 (PARI) 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
%o A005206 (Magma) [Floor((n+1)*(1+Sqrt(5))/2)-n-1: n in [0..80]]; // _Vincenzo Librandi_, Nov 19 2016
%o A005206 (Python)
%o A005206 from math import isqrt
%o A005206 def A005206(n): return (n+1+isqrt(5*(n+1)**2)>>1)-n-1 # _Chai Wah Wu_, Aug 09 2022
%Y A005206 Apart from initial terms, same as A060143. Cf. A123070.
%Y A005206 a(n):=Sum{k=1..n} h(k), n >= 1, with h(k):= A005614(k-1) and a(0):=0.
%Y A005206 Cf. A060144, A019446, A072649, A213676, A000201.
%Y A005206 Cf. A035513, A287870.
%K A005206 nonn,easy,nice
%O A005206 0,4
%A A005206 _N. J. A. Sloane_
%E A005206 a(0) = 0 added in the Name by _Bernard Schott_, Apr 23 2022