

A123070


Hofstadter FlipGsequence.


3



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, 18, 18, 19, 19, 20, 21, 21, 22, 23, 23, 24, 24, 25, 26, 26, 27, 27, 28, 29, 29, 30, 31, 31, 32, 32, 33, 34, 34, 35, 35, 36, 37, 37, 38, 39, 39, 40, 40, 41, 42, 42, 43, 44
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 Gsequence (see A005206), but flipped and renumbered, so that when the nodes of the tree are read from bottomtotop, lefttoright, 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 flipG(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).
Index entries for sequences from "Goedel, Escher, Bach"
Index entries for Hofstadtertype sequences


FORMULA

Conjecture: a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2; a(n) = (n+1)  a(a(n1)+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 = na(n1). If T = (n1)  a((n1)1) then a(n) = max{ainv(T)} otherwise a(n) = min{ainv(T)}, where ainv(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)=1d(n1)*d(a(n)) for n>=4.
Also satisfies: a(n1)+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)


PROG

(Python) # Emulate a breadthfirst traversal of the tree defining the "fliptree" of the Hofstadter Gsequence.
.def gflip_iter():
....yield 0
....yield 1
....# Start on a leftbranch 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:
............# Leftbranch node. Add a new root.
............queue.append((n, 0))
........n += 1
.i = gflip_iter()
.for n in range(0, 10001):
....print "%d %d" % (n, i.next())
# David Fifield (david(AT)bamsoftware.com), Jan 17 2009


CROSSREFS

Cf. A005206.
Sequence in context: A274089 A086335 A123387 * A057361 A136409 A039729
Adjacent sequences: A123067 A123068 A123069 * A123071 A123072 A123073


KEYWORD

nonn


AUTHOR

Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006


STATUS

approved



