Four steps to the left: vipers. Four steps to the right: a cliff. Don't die!

Question

Introduction

Suppose for a moment that the vipers and cliff are only two steps away, instead of three.

            o
           ---
Hsss!       |
 ';;' ___  /_\  ___  _
                      |

You are, unfortunately, a captive of a sadistic torturer. You must take a step either to the left or to the right every turn. If you don't, they shoot you dead instantly. You are allowed to plan out your steps beforehand, but once you take your first step, you can't change your plan. (And no dawdling either; they'll shoot you.)

Suddenly, a bright idea comes to mind...

Ah! I can just alternate stepping right and left! Step right, step left, step right, step left, and so on...

Ah ah ah, not so fast. Like I said, the torturer is sadistic. They get to choose whether you take every step, or every second step, or every third step, and so on. So if you naively choose the sequence RLRLRL... then they can force you to take every second step, which starts with LL. Uh oh! You've been bitten by vipers! Blackness swoops over you and all else fades away...

Actually no, you're not dead yet. You still have to come up with your plan. After thinking about it for a few minutes, you realize you are doomed. There is no way to plan out a series of steps that will guarantee your survival. The best you can come up with is RLLRLRRLLRR.¹ Eleven safe steps and no more. If the twelfth step is R, then the Torturer will make you take every step and then the last three steps send you off the cliff. If the twelfth step is L, then the Torturer will make you take every third step (LRLL), which puts you right in the brood of vipers and their lethal bites.

You pick R as the twelfth step, hoping to delay your demise as long as possible. With the wind roaring in your ears, you wonder to yourself...

What if I had three steps?

---

Spoiler alert!

You would still die. As it turns out, no matter how many steps you have, there will be some point where no matter what choice you make, there is a sequence of steps your Torturer can pick to ensure you meet your deadly fate.² However, when the vipers and cliff are three steps away, you can take a total of 1160 safe steps and when they're four steps away, there are at least 13,000 safe steps!³

The challenge

Given a single integer n < 13000, output a sequence of n safe steps, assuming the cliff and the vipers are four steps away.

Rules

• Can be either a full program or a function.
• Input can be taken through STDIN or equivalent, or as a function argument.
• Output must have two distinct characters (which can be +/-, R/L, 1/0, etc.).
• Any whitespace in the output doesn't matter.
• Hard-coding a solution is not allowed. That would trivialize this challenge.
• Your program should (in theory) finish in a decent amount of time. As in, n=13000 might take like a month, but it shouldn't take a thousand years or more. That is, no brute force. (Well, at least try to avoid it.)
• Life bonus: provide a series of 2000 safe steps. If you do this, the Torturer will be so impressed by your tenacity, perseverance, and forethought that they'll let you live. This one time. (Treat this sequence as a binary number and provide the decimal equivalent for verification. This is intended to reward answers that finish quickly as answers are allowed to take a very long time.)
• Score: bytes, unless you qualify for the bonus - multiply by 0.75.

Survive!

---

¹ There is a good explanation of this problem and "solution" by one of the stars of Numberphile, James Grime, over on his YouTube channel here: https://www.youtube.com/watch?v=pFHsrCNtJu4 .

² This 80-year-old conjecture, known as Erdos' discrepancy problem, was proved very recently by Terence Tao. Here is a very nice article on Quanta Magazine about this: https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/ .

³ Source: A SAT Attack on the Erdos Discrepancy Conjecture, by Boris Konev and Alexei Lisitsa. Retrieved from here: http://arxiv.org/pdf/1402.2184v2.pdf .

Answer 1

Java, 915 * 0.75 = 686.25

import java.util.*;class E implements Comparable<E>{static
int n,m,t,u;byte[]a;int k=2,b,d;E(){a=new byte[5];a[1]=13;}E(E
x){a=Arrays.copyOf(x.a,n+1);k=x.k;d=x.d;b=x.b;}int
g(int x){return(a[x]+1)%3-1;}void s(int x,int y){a[x]=(byte)(a[x]/3*3+(y+3)%3);}void
S(int x,int y){a[x]=(byte)(a[x]%3+(y+3)*3);}E
w(int x){if(g(k)==-x)return null;E e=new E(this);e.s(k,x);e.S(e.k++,x);for(m=0;++m<k;)if(k%m<1){u=e.a[m]/3-3+x;if(u==(k<9?2:4)*x)return
null;e.S(m,u);if(u==3*x){e.b++;if(k+m<=n){if(e.g(k+m)==x)return
null;e.s(k+m,-x);}}}return e;}public int compareTo(E o){m=d-o.d+(b-o.b)/60+(o.k-k)/150;return
m==0?o.k-k:m;}public static void main(String[]a){n=Integer.valueOf(a[0]);Queue<E>q=new PriorityQueue<>();q.add(new
E());for(;;){E x=q.remove(),y;if(x.k>n){for(t=0;++t<x.k;)System.out.print((x.g(t)+1)/2);return;}t=x.g(x.k<9?1:x.k%9==0?x.k/9:x.k%9);y=x.w(t);if(y!=null)q.add(y);y=x.w(-t);if(y!=null){y.d++;q.add(y);}}}}

Input is taken as a command-line argument.

This tries almost all possibilities (the only restriction is that the first 8 steps should only go within -1..1), going step by step, using a magic voodoo heuristic to choose which way to try first.

It solves 2000 and even 4000 within 1 second on my (fairly fast) computer. Needs more RAM for bigger numbers; the largest input I solved within 8GB is 5023 and it took about 30 seconds.

Decimal representation of the solution for 2000 steps, as requesed for the bonus:

67629177464446960798008264442022667063957880432486338092706841703491740570274032860458934082821213021464065304260003487277917407152662394728833698812373924467640518368465012204980858438160127647802572983143425507448999967241207186701518207195015015739598846687434709056793597015487555707466358473564611432637890414593517116857771284711814076853125419306285869381974622557155019992727242896503018802441210966188045211779436703341152749688824296759097963388158731237092792251164105828728858516951458791084595247591674731645830905744761534078963607725435881491831508342871545788662307953494333833994658998

Append Yb to it in CJam to convert back to binary.

About the heuristic: first, there is a pattern I'm using: every 9 steps try to repeat the first 9, except every (9*x)th step tries to repeat the x'th step. This is inspired from the solution I downloaded and used (hardcoded) in my python answer.

I'm keeping track of the number of times I deviated from the pattern, and also the number of times I got to an "edge" (1 step from dying). The heuristic function is basically a weighted combination of those 2 numbers and the number of steps taken so far.

The heuristic could be further tweaked to improve the speed, and there are several ways to add a random factor into it too.
In fact, I've just read about multiplicative functions in relation to this problem, and it looks like that can provide a significant improvement (TODO: implement this later).

Ungolfed and commented:

import java.util.*;

public class Erdos implements Comparable<Erdos> {
    static int n; // input (requested number of steps)
    static int m, t, u; // auxiliary variables

    byte[] a; // keeps each step and sum combined into 1 byte
    int k = 2; // number of steps + 1 (steps are 1-based)
    int edge; // number of times we got to an edge
    int diff; // number of differences from the expected pattern

    // start with one step
    Erdos() {
        a = new byte[5];
        set(1, 1);
        setSum(1, 1);
    }

    // copy constructor
    Erdos(Erdos x) {
        a = Arrays.copyOf(x.a, n + 1);
        k = x.k;
        diff = x.diff;
        edge = x.edge;
    }

    // get the x'th step (can be -1, 0 or 1)
    int get(int x) {
        return (a[x] + 1) % 3 - 1;
    }

    // set the x'th step
    void set(int x, int y) {
        a[x] = (byte) (a[x] / 3 * 3 + (y + 3) % 3);
    }

    // get the sum of every x'th step (should be within -3..3)
    int getSum(int x) {
        return a[x] / 3 - 3;
    }

    // set the sum of every x'th step
    void setSum(int x, int y) {
        a[x] = (byte) (a[x] % 3 + (y + 3) * 3);
    }

    // try to add a step with value x (1 or -1)
    Erdos grow(int x) {
        if (get(k) == -x) // predetermined step doesn't match
            return null;
        Erdos e = new Erdos(this);
        e.set(k, x);
        e.setSum(e.k++, x);
        for (m = 0; ++m < k;)
            if (k % m < 1) { // check all divisors of k
                u = e.getSum(m) + x; // updated sum
                if (u == (k < 9 ? 2 : 4) * x) // use limit 2 for the first 8 steps, 4 for the rest
                    return null; // dead
                e.setSum(m, u);
                if (u == 3 * x) { // we're at an edge
                    e.edge++;
                    if (k + m <= n) { // predetermine future step - should be going back
                        if (e.get(k + m) == x) // conflict
                            return null;
                        e.set(k + m, -x);
                    }
                }
            }
        return e;
    }

    public int compareTo(Erdos o) { // heuristic function
        m = diff - o.diff + (edge - o.edge) / 60 + (o.k - k) / 150;
        return m == 0 ? o.k - k : m;
    }

    public static void main(String[] a) {
        n = Integer.valueOf(a[0]);
        Queue<Erdos> q = new PriorityQueue<>();
        q.add(new Erdos());
        for (;;) {
            Erdos x = q.remove(), y;
            if (x.k > n) { // we made it
                for (t = 0; ++t < x.k;)
                    System.out.print((x.get(t) + 1) / 2);
                return;
            }
            t = x.get(x.k < 9 ? 1 : x.k % 9 == 0 ? x.k / 9 : x.k % 9); // next step based on the pattern
            y = x.grow(t);
            if (y != null)
                q.add(y);
            y = x.grow(-t);
            if (y != null) {
                y.diff++;
                q.add(y);
            }
        }
    }
}

Answer 2

Python 2, 236 bytes

n=input();r=len;u=[("",[0]*(n//4))]
while n>r(u[-1][0]):
 y,t=u.pop()
 for c in 0,1:
  s=t[:];u+=(y+"LR"[c],s),
  for i in range(r(s)):
   if-~r(y)//-~i*-~i==-~r(y):s[i]+=2*c-1;
   if abs(s[i])>3:u.pop();break;
print(u[-1][0])

This is fairly fast, for a brute-force-ish method, only taking a few seconds for n=223, but much longer for n>=224.

Explanation: Keep track of a list of string-list pairs (s,u), where the list u is such that u[i] is the current position after following every ith step in the string. For each string in the list, try to add "L" or "R", then change the values in the list that intersect. (i.e. if the resulting string has length 10, add or subtract 1 from positions 1,2,5 and 10, according to the directions you moved). If you exceed 3 or -3 throw the new pair away, otherwise keep it in the list. The longest strings are kept at the end. Once you have a string of length n, return it.

Answer 3

Python 2, 729 bytes

n=0
for x in"eJytVU2LwyAQPWzTvZjjspcsxFYTBdNuQSEF+///1jp+p5o0hYVSBl9nfOObNz1MlAgqzMcEEwQkDyIkFpDYCW0UnChbyZJiK2sfhDcYmu9hT0GdIPQvLduAmoCvvqEssvq84CVCpLzrNcOOspLhY6/KswB6FmoSxGPBcWts7lsMp/0q83da1hgC6k7GoqBir1ruAFIVvWIdTi++oGIAyZw8mkuG03uDDc+rEsSWTmFBwbLgtTF8hl1e/lpCigR7+pM5V9lIqVJBjStzKNRRQDp6UOrvwga6VFrGcWz6YHwLNYWUYeZfWO/DQTq7i4dAxixeszmtFEw7Cr5v9R3lRVF55TDzY6QRrSfzF9NLE7lAZ+vLnGgYLZ/FlCuoRcOugeFduHTqRWmyh1J91XpIndIbEk8jifL8hs8qQ8vjAVoGqhK5Tm/O5svpXd82QH4Azq05kYnhj93PzLbcTisFzXWfDqIC5zsq3jU7UUhSh1R3L4+i4HCXKlrGyywSBttPr2zpL4gCDPtk2HPN5tgZFomzSDPfGAlASus+e4KlLcjS0vPQ0f5/mR/r1s4PcxsgMLRSMp617AveCuup2OCAPBT6yltWrPO9azsbp6fphR87Lc7VzcbEt5F4Ydg/NzhXTA==".decode("base64").decode("zip"):n=n*64+ord(x)
print bin(n)[2:input()+2]

I think this qualifies for the bonus too if the idea is "to reward answers that finish quickly".

However, this is a hard-coded answer, which is not in the spirit of the challenge (although not explicitly disallowed when I wrote it).