0,4

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 bottum-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

D. Hofstadter, "Goedel, Escher, Bach", p. 137.

Albert Neumueller, Table of n, a(n) for n = 1..1649

Index entries for sequences from "Goedel, Escher, Bach"

Index entries for Hofstadter-type sequences

See discussion in the Physics Forum, http://www.physicsforums.com/showthread.php?t=127822

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: 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).

Cf. A005206

Sequence in context: A020888 A086335 A123387 this_sequence A057361 A136409 A039729

Adjacent sequences: A123067 A123068 A123069 this_sequence A123071 A123072 A123073

nonn

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