Four steps to the left: vipers. Four steps to the right: a cliff. Don't die!
Java, 915 * 0.75 = 686.25

import java.util.*;class E implements Comparable&lt;E&gt;{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&lt;k;)if(k%m&lt;1){u=e.a[m]/3-3+x;if(u==(k&lt;9?2:4)*x)return
null;e.S(m,u);if(u==3*x){e.b++;if(k+m&lt;=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&lt;E&gt;q=new PriorityQueue&lt;&gt;();q.add(new
E());for(;;){E x=q.remove(),y;if(x.k&gt;n){for(t=0;++t&lt;x.k;)System.out.print((x.g(t)+1)/2);return;}t=x.g(x.k&lt;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 &quot;edge&quot; (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&lt;Erdos&gt; {
    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 &lt; k;)
            if (k % m &lt; 1) { // check all divisors of k
                u = e.getSum(m) + x; // updated sum
                if (u == (k &lt; 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 &lt;= 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&lt;Erdos&gt; q = new PriorityQueue&lt;&gt;();
        q.add(new Erdos());
        for (;;) {
            Erdos x = q.remove(), y;
            if (x.k &gt; n) { // we made it
                for (t = 0; ++t &lt; x.k;)
                    System.out.print((x.get(t) + 1) / 2);
                return;
            }
            t = x.get(x.k &lt; 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);
            }
        }
    }
}