Golomb sequence

Question

Golomb sequence

I'm trying to resolve a small programming challenge, which is calculating the nth number of the Golomb's sequence (see this for more help). I've written a simple solution, but it may have any problem, because the number at 2500000 position is 10813 but my program gives me 10814.

var golomb = (function(){
    var cache = [null, 1];
    const o = 0.5 * (1 + Math.sqrt(5)); // Golden ratio 
    return function(n){
        return cache[n] || (function(){
            return Math.round(Math.pow(o, 2-o) * Math.pow(n, o-1));
        })();
    };
})();

var num = golomb(process.argv[2]);
console.log(num);

Maybe, the golden ratio needs more lenght than JavaScript gives. Someone can help? Thanks.

javascript
node.js

Answer 1

Sgmonda, the formula you got from Wolfram Alpha isn't an exact solution. I've actually complained to them, since I like the Golomb sequence. The recurrence relation is exact but slow, even if you cache it. Heh, that's why the programming challenge is a challenge.

Answer 2

From the wikipedia article:

Colin Mallows has given an explicit recurrence relation:
a(1) = 1;
a(n + 1) = 1 + a(n + 1 − a(a(n)))

You need to implement your solution in this iterative method that uses integers.

A quick attempt at trying to implement that gives:

function golomb(n) {
    if(n == 1) return 1;
    else return 1 + golomb(n − golomb(golomb(n-1)));
}

Answer 3

For what it's worth, here is a function based on the recurrence relation, with a cache, that gives the correct answer pretty quickly

var golomb = (function() {
    var cache = [null, 1];
    return function(n) {
       var i;
       for (i=cache.length;i<n;i++) cache[i]=golomb(i);
       return cache[n] || (cache[n]=1+golomb(n-golomb(golomb(n-1))));
    }
})();

check it up on jsFiddle