The Hofstadter–Conway \$10000 sequence is defined by the nested recurrence relation $$c(n) = c(c(n-1)) + c(n-c(n-1))$$ with $c(1) = c(2) = 1$. This sequence is [A004001](https://oeis.org/A004001) and it is well-known that this sequence has many amazing properties which are investigated in a very interesting *paper* [Kubo and Vakil - On Conway's recursive sequence](https://doi.org/10.1016/0012-365X(94)00303-Z).

A related curious sequence can be defined by similar recurrence relation as below $$c^*(n) = n - c^*(c^*(n-1)) - c^*(n-c^*(n-1))$$ with $c^*(1) = c^*(2) = 1$. I introduced this sequence in [A287422](https://oeis.org/A287422) and recurrence is also investigated in terms of sensitivity of initial conditions selections
[Alkan and Aybar - On Families of Solutions for Meta-Fibonacci Recursions Related to Hofstadter–Conway $10000 Sequence](https://doi.org/10.1007/978-3-030-35441-1_14).

**Conjecture**. $c(n) - \frac{n}2$ $\ge$ $\left\lvert c^*(n) - \frac{n}2 \right\rvert$ for all $n \ge 1$. (It is checked up to $2^{32}$.)

**Question**. Can someone show that $c(n) - \frac{n}2$ $\ge$ $\left\lvert c^*(n) - \frac{n}2 \right\rvert$ for all $n \ge 1$ ? 

Comments that are related to combinatorial characterization of $c^*(n)$ are also very welcome.

(I the share below graph in order to display behaviours of both sequences for $n \le 2^{10}$.
Red:  $c(n) - \frac{n}2$, Black: $c^*(n) - \frac{n}2$.)

[![Graphs of c(n) - n/2 and c*(n) - n/2][1]][1]


**Note.** I believe that it is also possible to see a way to connection of $c(n)$ and $c^*(n)$ thanks to certain auxiliary variants defined by [A317754](https://oeis.org/A317754) and [A317854](https://oeis.org/A317854), see the below graph (red: transformation of $c(n)$, black: transformation of $c^*(n)$). (These variants also make probably interesting sounds if one can think that recurrences that produce sequences with curious sounds are general of interest.) 
[![Graphs of transformations of c(n) and c*(n)][2]][2]


  [1]: https://i.sstatic.net/N18Zj.png
  [2]: https://i.sstatic.net/5GCuO.png