|
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 one or exactly k+1 times (except from the initial values which occur k times). A block of k+1 occurences of the same number n is after the first one interrupted 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 elements 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 pathes)
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 crosses on its way from a(n) to n exactly two other pathes, e.g. from 17 to 25)
Conjecture: This recursive structure exists for every sequence of the above mentioned family. The first node of D has always k+1 children nodes where the first one consists of a new copy of D, the second one consists of another node and then D. The remaining children nodes consist of another node and then C. Between the first and the second leaf is always space for k-1 nodes of construct C. Construct C crosses on its way from a(n) to n always exactly k pathes (the right ones from construct D).
| 