Hofstadter-Conway \$10000 sequence is defined by nested recurrence relation $$c(n) = c(c(n-1)) + c(n-c(n-1))$$ with $c(1) = c(2) = 1$. This sequence is https://oeis.org/A004001 and it is well-known that this sequence has many amazing properties: https://www.sciencedirect.com/science/article/pii/0012365X9400303Z

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 https://oeis.org/A287422 and recurrence is also investigated in terms of sensitivity of initial conditions selections: https://link.springer.com/chapter/10.1007%2F978-3-030-35441-1_14

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$ ? (It is checked up to $2^{30}$.)

(I 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$)

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.