Conway's $1(0),000 challenge Background

This challenge is about A004001, a.k.a. Hofstadter-Conway $10000 sequence:

$$
a_1 = a_2 = 1, \quad a_n = a_{a_{n-1}} + a_{n-a_{n-1}}
$$

which starts with

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, 12, 13, 14, 14, 15, 15, 15, 16, 16, 16, 16, 16, ...


John Conway proved the following property of the sequence:

$$
\lim_{n\rightarrow\infty}{\frac{a_n}{n}}=\frac12
$$

After the proof, he offered $1(0),000 for the smallest \$k\$ such that all subsequent terms of \$a_j/j\$ after the \$k\$-th term are within 10% margin from the value \$1/2\$, i.e.

$$
\left|\frac{a_j}{j}-\frac12\right|&lt;\frac1{20},\quad j &gt; k
$$

To quote Sloane's comment on the OEIS page (which explains the title):


  John said afterwards that he meant to say $1000, but in fact he said $10,000. [...] The prize was claimed by Colin Mallows, who agreed not to cash the check.


Here are some graphs to get some feel of the sequence (copied from this MathOverflow.SE answer):



Also check out A004074, which lists the values of \$2a_n-n\$.

Challenge

Given the amount of margin \$r\$, solve the generalized Conway's challenge: find the smallest \$k\$ which satisfies

$$
\left|\frac{a_j}{j}-\frac12\right|&lt;\frac{r}{2},\quad j &gt; k
$$

This can be also phrased as the largest \$k\$ that satisfies \$\left|\frac{a_k}{k}-\frac12\right|\ge\frac{r}{2}\$. You can assume \$0&lt;r&lt;1\$, so that the task is well-defined in both ways.

(The original challenge is \$r=0.1\$, and the answer by Colin Mallows is 1489, according to Mathworld (which agrees with my own implementation). The value of 3173375556 on the MO answer is probably the one for \$r=0.05\$.)

For simplicity, you may assume a few conjectured properties of the sequence:


\$a_n = n/2\$ when \$n = 2^k, k \in \mathbb{N}\$.
\$2a_n - n\$


is nonnegative everywhere,
is 0 when \$n = 2^k, k \in \mathbb{N}\$,
follows the Blancmange curve-like pattern between the powers of two (as visible in the second figure above), and
when divided by \$n\$, has the maximum values between powers of two decreasing as \$n\$ increases (as visible in the first figure above).



Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

r     | answer
------+-------
0.9   | 1
0.4   | 1
0.3   | 6
0.2   | 25
0.15  | 92
0.13  | 184
0.12  | 200
0.11  | 398
0.1   | 1489
0.09  | 3009
0.085 | 6112
0.08  | 22251


Reference implementation in Python.

(A hint for termination check: A value of \$k\$ is the answer if \$\frac{2a_k}{k}-1\ge r\$ and \$\frac{2a_j}{j}-1&lt; r\$ for \$k &lt; j \le 4k\$.)
JavaScript (ES6), 83 bytes
Slow as hell.

g=n=&gt;n&lt;3||g(n-g(--n))+g(g(n))
f=(r,n=1,m)=&gt;(x=g(n)*2-n)|m?f(r,n+1,x&lt;r*n?x&amp;&amp;m:o=n):o

Try it online!
How?
We look for the highest \$n\$ such that:
$$2\cdot a(n)-n \ge r\cdot n$$
We stop when no greater value is found in a whole interval:
$$[2^k+1,2^{k+1}], k&gt;0$$
whose upper bound is characterized by \$2\cdot a(n)-n=0\$.

JavaScript (ES6), 94 bytes
A much faster version using a cache to prevent too many recursive calls.

g=n=&gt;g[n]=g[n]||n&lt;3||g(n-g(--n))+g(g(n))
f=(r,n=1,m)=&gt;(x=g(n)*2-n)|m?f(r,n+1,x&lt;r*n?x&amp;&amp;m:o=n):o

Try it online!