cp's OEIS Frontend

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.

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

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

Crossrefs

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.

Programs

  • Haskell
    a005206 n = a005206_list !! n
a005206_list = 0 : zipWith (-) [1..] (map a005206 a005206_list)
-- Reinhard Zumkeller, Feb 02 2012, Aug 07 2011
  • Haskell
    a005206 = sum . zipWith (*) a000045_list . a213676_row . a000201 . (+ 1)
-- Reinhard Zumkeller, Mar 10 2013
  • Magma
    [Floor((n+1)*(1+Sqrt(5))/2)-n-1: n in [0..80]]; // Vincenzo Librandi, Nov 19 2016
  • Maple
    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);
  • Mathematica
    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 *)
  • 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
  • Python
    from math import isqrt
def A005206(n): return (n+1+isqrt(5*(n+1)**2)>>1)-n-1 # Chai Wah Wu, Aug 09 2022

Formula

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)

Extensions

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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