A163801 a(n) = n - a(a(n-2)) with a(0)=0, a(1)=1.

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

Offset: 0

Author

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

Keywords

• easy
• nonn

Comments

A generalization of the Hofstadter G-sequence A005206 since it is part of the following family of sequences:

a(n)=n-a(a(n-k)) with the initial values a(0)=0,a(1)=a(2)=...=a(k-1)=1 and with k=1,2,3... (here k=2)

Every a(n) occurs either exactly one or exactly three times. Two blocks of three same elements are interrupted by either exactly one singular or exactly three consecutive natural numbers.

Since every natural number occurs in the sequence at least once 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..

..|..

.a(n)

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

....1..............................

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

....2..............................

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

....|......\.......................

....|.........\....................

....3...........4..................

....|.............\................

....5...............6..............

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

....7........8......9....10........

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

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

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

...11...12....13.14.15......16.....

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

...17.18.19.20.21.22.23.24..25..26.

Conjecture: Which features a certain structure (Comparable to A005206 or A135414). 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):

Diagram of D:

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

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

..D..C..x...

.........\..

..........D.

Diagram of C:

..x..

..|..

..C..

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000

Crossrefs

Same recurrence relation as A135414.

Cf. A379275.

Programs

Maple

a:= proc(n) option remember; `if`(n<2, n, n-a(a(n-2))) end:
seq(a(n), n=0..74);  # Alois P. Heinz, Dec 19 2024

Mathematica

A163801[n_] := A163801[n] = If[n < 2, n, n - A163801[A163801[n-2]]];
Array[A163801, 100, 0] (* Paolo Xausa, Jan 04 2025 *)