OFFSET
0,4
COMMENTS
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.
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 to the node flip-G(n) = a(n) below it:
n
.\
.a(n)
For example:
7
.\
..5
since a(7) = 5. The tree has a recursive structure, since the following 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
REFERENCES
D. Hofstadter, "Goedel, Escher, Bach", p. 137.
LINKS
David Fifield, Table of n, a(n) for n = 0..10000
Pierre Letouzey, Hofstadter's problem for curious readers, technical report, 2015.
Physics Forum Discussion, Recursive Trees (from GED).
FORMULA
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]
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).
From Pierre Letouzey, Sep 09 2015: (Start)
Alternative definition via differences:
a(0) = 0; a(n+1) = a(n) + d(n) where:
d(0) = 1, d(1) = 0, d(2) = 1, d(3) = 1; d(n)=1-d(n-1)*d(a(n)) for n>=4.
Also satisfies: a(n-1)+a(a(n)) = n for n>=4.
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)
MATHEMATICA
a[n_] := a[n] = Switch[n, 0, 0, 1, 1, 2, 1, 3, 2, _, (n+1) - a[a[n-1]+1]];
a /@ Range[0, 100] (* Jean-François Alcover, Nov 16 2019 *)
PROG
(Python) # Emulate a breadth-first traversal of the tree defining the "flip-tree" of the Hofstadter G-sequence.
def gflip_iter():
yield 0
yield 1
# Start on a left-branch node, parent node is 1.
queue = [(1, 1)]
n = 2
while True:
parent, state = queue.pop(0)
yield parent
if state == 0:
# Root node. Add the two children.
queue.append((n, 1))
queue.append((n, 0))
elif state == 1:
# Left-branch node. Add a new root.
queue.append((n, 0))
n += 1
i = gflip_iter()
for n in range(0, 10001):
print("%d %d" % (n, next(i)))
# David Fifield (david(AT)bamsoftware.com), Jan 17 2009
CROSSREFS
KEYWORD
nonn
AUTHOR
Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006
STATUS
approved