13
\$\begingroup\$

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 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\$.)

\$\endgroup\$
  • 1
    \$\begingroup\$ I thought this post is spam when I first read its title. \$\endgroup\$ – tsh Apr 22 at 1:48
  • \$\begingroup\$ This would be a great fastest-code. \$\endgroup\$ – S.S. Anne Apr 22 at 15:10
4
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What does \$k\$ stand for here? \$\endgroup\$ – user92069 Apr 21 at 10:57
  • \$\begingroup\$ @petStorm Any positive integer. \$\endgroup\$ – Arnauld Apr 21 at 11:07
  • \$\begingroup\$ @petStorm To be a bit more specific, we don't care about the value of \$k\$. We just need to know that we've reached the boundary of the Blancmange curve, which happens whenever \$n\$ is a power of \$2\$. \$\endgroup\$ – Arnauld Apr 21 at 11:24
3
\$\begingroup\$

05AB1E, 49 48 bytes

тS_λλ₁₅N₁-₅+}U∞oü‚vyŸ¦R.ΔXyè·αIy*@}Dˆ(i¯®KDgĀiθq

-1 byte thanks to @Grimmy.

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

In theory this 46 bytes version should work, but apparently there is a bug with the recursive environment inside a loop/map preventing this..

∞oü‚vyŸ¦R.ΔDтS_λèλ₁₅N₁-₅+}·αIy*@}Dˆ(i¯®KDgĀiθ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$$

   λ             # Create a recursive environment,
                 # outputting an infinite list
т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])
    λ            # Within the recursive environment:
     ₁           #  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): a(n-a(n-1)) as well
           +     #  And add those together
            }U   # Pop and store this infinite list in variable `X`
∞                # Push an infinite positive list: [1,2,3,...]
 o               # Take each as 2 to the power: [2,4,8,...]
  ü‚             # Pair each overlapping pair together: [{2,4},{4,8},{8,16},...]
v                # Loop `y` over each pair {a,b}:
 yŸ              #  Convert the pair to a list in that 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:
   Xyè           #   Index `y` in the infinite recursive sequence `X`: a(y)
      ·          #   Double it: 2⋅a(y)
       α         #   Take the absolute difference with `y`: |y-2⋅a(y)|
        Iy*@     #   Check whether it's >= the input multiplied by `y`: |y-2⋅a(y)| >= Iy
  }Dˆ            #  Add a copy of the found value into the global array
     (i          #  If this value was -1 (thus none were found):
       ¯         #   Push the global array
        ®K       #   Remove all -1
          DgĀi   #   And if it's non-empty:
              θ  #    Leave the last (largest) value of the global array (excluding -1s)
               q #    And terminate the program
                 #    (after which the top of the stack is output implicitly)

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 011S => тS_ \$\endgroup\$ – Grimmy Apr 22 at 4:49
  • \$\begingroup\$ @Grimmy Thanks. I had the feeling that could be golfed, but didn't think about that.. \$\endgroup\$ – Kevin Cruijssen Apr 22 at 7:05
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @ceilingcat Thanks -- bash arithmetic expressions are close enough to C that the same improvements worked on my bash answer too. \$\endgroup\$ – Mitchell Spector Apr 22 at 16:11
  • \$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$ – Mitchell Spector Apr 23 at 1:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.