login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A123070 Hofstadter Flip-G-sequence. 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 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).

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

Index entries for Hofstadter-type sequences

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)

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 12:29 EST 2019. Contains 319330 sequences. (Running on oeis4.)