cp's OEIS Frontend

A123070 Hofstadter Flip-G-sequence.

%I A123070 #101 Aug 31 2025 19:55:13
%S A123070 0,1,1,2,3,3,4,5,5,6,6,7,8,8,9,10,10,11,11,12,13,13,14,14,15,16,16,17,
%T A123070 18,18,19,19,20,21,21,22,23,23,24,24,25,26,26,27,27,28,29,29,30,31,31,
%U A123070 32,32,33,34,34,35,35,36,37,37,38,39,39,40,40,41,42,42,43,44
%N A123070 Hofstadter Flip-G-sequence.
%C A123070 This sequence is an answer to the question posed on page 137 of Goedel, Escher, Bach: find a sequence that generates a tree which is like that of the G-sequence (see A005206), but flipped and renumbered, so that when the nodes of the tree are read from bottom-to-top, left-to-right, the natural numbers: 1, 2, 3, 4, 5, 6, ... are obtained.
%C A123070   14.15.16.17.18.19.20.21
%C A123070   .\..\./...\./..\...\./
%C A123070   ..9..10....11...12.13
%C A123070   ...\./......\...\./
%C A123070   ....6........7...8
%C A123070   .....\........\./
%C A123070   ......4........5
%C A123070   ........\..../
%C A123070   ..........3
%C A123070   ............\
%C A123070   .............2
%C A123070   ..............\ /
%C A123070   ...............1
%C A123070 To construct the tree: node n is connected to the node flip-G(n) = a(n) below it:
%C A123070   n
%C A123070   .\
%C A123070   .a(n)
%C A123070 For example:
%C A123070   7
%C A123070   .\
%C A123070   ..5
%C A123070 since a(7) = 5. The tree has a recursive structure, since the following construct
%C A123070   \
%C A123070   .x
%C A123070   ..\ /
%C A123070   ...x
%C A123070 can be repeatedly added on top of its own ends, to construct the tree from its root: e.g.
%C A123070   \
%C A123070   .x
%C A123070   ..\./...\
%C A123070   ...x.....x
%C A123070   ....\.....\ /
%C A123070   .....x.....x
%C A123070   ......\.../
%C A123070   ........x
%D A123070 D. Hofstadter, "Goedel, Escher, Bach", p. 137.
%H A123070 David Fifield, <a href="/A123070/b123070.txt">Table of n, a(n) for n = 0..10000</a>
%H A123070 Alan Michael Gómez Calderón, <a href="/A123070/a123070_15.txt">A Proof for a Hofstadter Flip-G-sequence Closed-form formula</a>
%H A123070 Alan Michael Gómez Calderón, <a href="/A123070/a123070_12.txt">A Proof using Walnut for a Hofstadter Flip-G-sequence Closed-form formula</a>
%H A123070 Pierre Letouzey, <a href="http://hal.inria.fr/hal-01195587">Hofstadter's problem for curious readers</a>, technical report, 2015.
%H A123070 Physics Forum Discussion, <a href="https://www.physicsforums.com/threads/recursive-trees-from-ged.127822">Recursive Trees (from GED)</a>.
%H A123070 Jeffrey Shallit, <a href="/A123070/a123070.pdf">Fibonacci automaton for the Flip-G sequence</a>.
%H A123070 <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>
%H A123070 <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>
%F A123070 Conjecture: a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2; a(n) = (n+1) - a(a(n-1)+1) for n>=4. [Conjecture has been proved; see Letouzey link. - _Pierre Letouzey_, Sep 09 2015]
%F A123070 Conjecture: a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2; for n>=4, let T = n-a(n-1). If T = (n-1) - a((n-1)-1) then a(n) = max{a-inv(T)} otherwise a(n) = min{a-inv(T)}, where a-inv(n) is the inverse of a(n).
%F A123070 From _Pierre Letouzey_, Sep 09 2015: (Start)
%F A123070 Alternative definition via differences:
%F A123070 a(0) = 0; a(n+1) = a(n) + d(n) where:
%F A123070 d(0) = 1, d(1) = 0, d(2) = 1, d(3) = 1; d(n)=1-d(n-1)*d(a(n)) for n>=4.
%F A123070 Also satisfies: a(n-1)+a(a(n)) = n for n>=4.
%F A123070 a(n) = A005206(n) + e(n), where e(n) is 0 or 1 depending of the shape of the decomposition of n as sums of Fibonacci numbers via Zeckendorf's theorem. (End)
%F A123070 There is an 11-state Fibonacci automaton that generates the sequence a(n) as follows:  the inputs are the Zeckendorf representations of n and x in parallel, and the automaton accepts if and only if x = a(n). See the file a123070.pdf in the "links" section above. - _Jeffrey Shallit_, Feb 19 2025
%F A123070 a(n) = A005206(n - 3) + 2, for n >= 3; a(n) = n - floor((n - 2)/(1 + phi)) - 1, where phi is the golden ratio (1 + sqrt(5))/2 = (A001622). - _Alan Michael Gómez Calderón_, Aug 05 2025
%t A123070 a[n_] := a[n] = Switch[n, 0, 0, 1, 1, 2, 1, 3, 2, _, (n+1) - a[a[n-1]+1]];
%t A123070 a /@ Range[0, 100] (* _Jean-François Alcover_, Nov 16 2019 *)
%o A123070 (Python) # Emulate a breadth-first traversal of the tree defining the "flip-tree" of the Hofstadter G-sequence.
%o A123070 def gflip_iter():
%o A123070     yield 0
%o A123070     yield 1
%o A123070     # Start on a left-branch node, parent node is 1.
%o A123070     queue = [(1, 1)]
%o A123070     n = 2
%o A123070     while True:
%o A123070         parent, state = queue.pop(0)
%o A123070         yield parent
%o A123070         if state == 0:
%o A123070             # Root node. Add the two children.
%o A123070             queue.append((n, 1))
%o A123070             queue.append((n, 0))
%o A123070         elif state == 1:
%o A123070             # Left-branch node. Add a new root.
%o A123070             queue.append((n, 0))
%o A123070         n += 1
%o A123070 i = gflip_iter()
%o A123070 for n in range(0, 10001):
%o A123070     print("%d %d" % (n, next(i)))
%o A123070 # David Fifield (david(AT)bamsoftware.com), Jan 17 2009
%Y A123070 Cf. A005206, A060144.
%K A123070 nonn,changed
%O A123070 0,4
%A A123070 Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006