A163873 a(n) = n - a(a(n-2)) with a(0) = a(1) = 0.

0, 0, 2, 3, 2, 2, 4, 5, 6, 7, 6, 6, 8, 9, 8, 8, 10, 11, 12, 13, 12, 12, 14, 15, 16, 17, 16, 16, 18, 19, 18, 18, 20, 21, 22, 23, 22, 22, 24, 25, 24, 24, 26, 27, 28, 29, 28, 28, 30, 31, 32, 33, 32, 32, 34, 35, 34, 34, 36, 37, 38, 39, 38, 38, 40, 41, 42, 43, 42, 42, 44, 45, 44, 44, 46

Offset

0,3

Comments

A very near generalization of the Hofstadter G-sequence A005206 since it is part of the following family of sequences (which would give for k=1 the original G-sequence):

a(n) = n - a(a(n-k)) with a(0)=a(1)=...=a(k-1)=0 with k=1,2,3,... (here k=2).

Some things can be said about this family of sequences: Every a(n) occurs either exactly once or exactly k+1 times (except for the initial values which occur k times). A block of k+1 occurrences of the same number n is interrupted after the first one by the following k-1 elements: n+1, n+2, ..., n+k-1 (e.g., see from a(12) to a(15): 8, 9, 8, 8).

Since every natural number occurs in the sequence at least once and 0 <= a(n) <= n for all n the terms can be ordered in such a way that every n is connected to its a(n) in a tree structure so that:

.a(n)

..|..

..a..

This will give for the first 27 elements the following (ternary) tree:

....2.___.....................

../...\..\___.................

./.....\.....\___.............

/.......\........\___.........

.........4...........5........

.........|...........|........

.........6...........7........

......../.\\......../.........

......./...\\______/___.......

.......|....\_____/_...\......

.......|........./..\...\.....

.......|....____/....\...\....

.......8...9.........10...11..

....../\\./...........|...|...

...../..\X_______.....|...|...

..../.../\__.....\....|...|...

...12..13...14...15..16...17..

../.\\./.....|....|../\\./....

./...\X___...|....|..|.\X__...

.|.../\_..\..|.../../../\..\..

.18.19.20.21.22.23.24.25.26.27

(X means two crossing paths)

This features a certain structure (similar to the G-sequence A005206 or other sequences of this family: A163875 and A163874). If the (below) following two constructs (C and D) are added on top of their ends (either marked with C or D) one will (if starting with one instance of D) receive the above tree (x marks a node, o marks spaces for nodes that are not part of the construct but will be filled by the other construct):

Diagram of D:

......x......

..../..\\....

.../....\.\..

..D...o..x.x.

.........|.|.

.........D.C.

(o will be filled by C)

Diagram of C:

.\...x.

\.\./..

.\./...

../.\..

./.\.\.

C...\.\

(This means construct C, on its way from a(n) to n, crosses exactly two other paths, e.g., from 17 to 25.)

Conjecture: This recursive structure exists for every sequence of the above mentioned family. The first node of D always has k+1 child nodes where the first one consists of a new copy of D, the second one consists of another node and then D. The remaining child nodes consist of another node and then C. Between the first and the second leaf there is always space for k-1 nodes of construct C. Construct C, on its way from a(n) to n, always crosses exactly k paths (the right ones from construct D).

Links

Table of n, a(n) for n=0..74.

Crossrefs

Same recurrence relation as A163801 and A135414.

Sequence in context: A372053 A372048 A053269 * A309563 A292588 A335965

Adjacent sequences: A163870 A163871 A163872 * A163874 A163875 A163876

Keyword

nonn

Author

Daniel Platt (d.platt(AT)web.de), Aug 08 2009

Extensions

Definition corrected by Daniel Platt (d.platt(AT)web.de), Sep 14 2009

Status

approved