Conway's $1(0),000 challenge

Question

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|<\frac1{20},\quad j > 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|<\frac{r}{2},\quad j > 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<r<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< r\$ for \$k < j \le 4k\$.)

Answer 1

JavaScript (ES6), 83 bytes

Slow as hell.

g=n=>n<3||g(n-g(--n))+g(g(n))
f=(r,n=1,m)=>(x=g(n)*2-n)|m?f(r,n+1,x<r*n?x&&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>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=>g[n]=g[n]||n<3||g(n-g(--n))+g(g(n))
f=(r,n=1,m)=>(x=g(n)*2-n)|m?f(r,n+1,x<r*n?x&&m:o=n):o

Try it online!

Answer 2

Pure Bash, ^{110 109 108} 105 bytes

a=(0 1 1)
v=1
m=1
for((n=3;c<2;n++)){
c=$[a[n]=v=a[v]+a[n-v],(2*v-n)*$2>=$1*n?m=n,0:c+!(n&n-1)]
}
echo $m

Try it online!

3 bytes off due to the same improvements made by ceilingcat for my C answer.

Input is a fraction, passed as arguments -- the numerator in the first argument, and the denominator in the second argument. For example, to pass 0.13, the command would look like: ./program 13 100

(Bash doesn't support floating-point numbers natively, but rational numbers are perfect for this challenge.)

The program runs quickly enough that it can get through all the OP's test cases in a single run at TIO, even though bash is a relatively slow interpreted language.

Output is on stdout.

Answer 3

05AB1E, 49 48 40 bytes

∞oüŸvy¦R.ΔтS_λè₅N₁-₅+}·yαIy*@}Dˆ(i¯àDdiq

-1 byte thanks to @Grimmy.

Try it online. (No test suite, because of the q.)

Explanation:

Inspired by @Arnauld's approach, so I too look for the largest \$n\$ such that:
$$2\cdot a(n)-n \ge r\cdot n$$

And I also stop when no greater value is found in a whole interval:
$$\left(2^k,2^{k+1}\right],k>0$$

∞                 # Push an infinite positive list: [1,2,3,...]
 o                # Take each as 2 to the power: [2,4,8,...]
  ü               # For each overlapping pair:
   Ÿ              #  Create a list in that range:
                  #   [[2,3,4],[4,5,6,7,8],[8,9,10,11,12,13,14,15,16],...]
vy                # Loop over each inner list in the range [a,b]:
  ¦               #  Remove the first value to make the range (a,b]
   R              #  Reverse it to [b,a)
  .Δ              #  Find the first value `y` in this list which is truthy for,
                  #  or -1 if none are found:
       λ          #   Create a recursive environment,
        è         #   to output the `y`'th value afterwards
    тS_           #   Start it at a(0)=0, a(1)=a(2)=1
                  #   (push 100 as list [1,0,0] and invert booleans to [0,1,1])
                  #    (implicitly push a(n-1))
         ₅        #    And use that for a(x): a(a(n-1))
         N₁-      #    Push n-a(n-1)
            ₅     #    And use that for a(x) as well: a(n-a(n-1))
             +    #    And add those together
       }·         #   After the recursive environment, double it: 2*a(y)
         yα       #   Take the absolute difference with `y`: |2*a(y)-y|
           Iy*    #   Push the input multiplied by `y`
              @   #   Check |2*a(y)-y| >= input*y
   }Dˆ            #  After the found_first, add a copy to the global_array
      (i          #  If this value was -1 (thus none were found):
        ¯         #   Push the global_array
         à        #   Pop and push its maximum
          D       #   Duplicate it
           di     #   Pop the copy, and if this maximum is NOT -1:
             q    #    Terminate the program
                  #    (after which this maximum is output implicitly as result)

NOTE: The vy cannot be ε or ʒ to act as a foreach with implicit y, because we'd need a --no-lazy flag in order to have a proper output, which isn't possible due to the lazy infinite recursive list.

Answer 4

Erlang (escript), 178 bytes

a(X)->case X>2 of true->a(a(X-1))+a(X-a(X-1));_->1end.
c(R)->c(R,1,0,0).
c(R,N,M,O)->case 2*a(N)-N>R*N of true->c(R,N+1,N,N+1);_->case N>O bsl 1of true->M;_->c(R,N+1,M,O)end end.

Try it online!

Answer 5

C (gcc), ^{119 116} 113 bytes

f(float r){int a[99999]={0,1,1},v=1,m=1,n=2,c=0;for(;c<2;c=2*v>=r*n+n?m=n,0:c+!(n&n-1))a[n]=v=a[v]+a[++n-v];v=m;}

Try it online!

3 bytes off thanks to ceilingcat.

And now 3 more bytes off from ceilingcat.

This is a port of my bash answer. It's a function which accepts r as an argument (a float this time) and returns the desired result.