Calculate the nth term of Golomb's self-describing sequence

Question

Inspired by the previous question.

Golomb's self-describing sequence g(n) is a sequence where any natural number n is repeated within the sequence g(n) times.

The first few numbers in the sequence are:

n    1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
g(n) 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8

You can see that g(4)=3, and that "4" is repeated 3 times in the sequence.

Limitations: n<100000.

Smallest code wins.

Answer 1

GolfScript (31 chars)

~([1 2.]2{.2$=[1$)]*@\+\)}3$*;=

Demo

Answer 2

PHP

This recursive version is shorter (60) but computationally inefficient:

function g($n){return$n==1?1:1+g($n-g(g($n-1)));}echo g($n);

This is much faster but longer (78):

$a=[1,2,2];for($i=3;$i<$n;$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

Much faster, but at 89 characters would be:

$a=[1,2,2];for($i=3;!isset($a[$n-1]);$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

Which is O(n)

Answer 3

PHP - 63 Chars

function g($n){for(;++$i<=$n;){for(;++$j<=$i;){echo $i;}$j=0;}}

Fast AND short.

I appear to have had the wrong sequence in mind. Derp.

This is CORRECT, fast, and short.

function g($n){for(;++$i<$n;){echo round(1.201*pow($i,.618));}}

Accuracy may suffer past the required 100,000 mark, but I did in fact meet the mark.

Answer 4

Javascript, 93 chars

c=[,1],i=c.length;function g(n){for(i;i<n;i++) c[i]=g(i);return c[n]||(c[n]=1+g(n-g(g(n-1))))}

Answer 5

J, 43 characters

f=:3 :'<.@:+&0.5(p^2-p)*y^p-1[p=:(+%)/20$1'

Defines a function using the asymptotic expression given on the wikipedia page.

   f 5
3
   f 20
8
   f 100000
1479

Annoyingly 9 characters are used just rounding to the nearest integer.

Answer 6

main()
{
int k=2,l=2,c=2,j=1,m,t;
printf("%d",j);
while(c<100000)
{
    for(m=1;m<3;m++)
    {
    for(t=0;t<k;t++)
    {
    printf("%d",l);
    c++;
    }
    l++;
    }
    k++;
}
getch();
}

Answer 7

Python - 76 chars

n=20;g=[1,2,2];[[g.append(i)for j in range(g[i-1])]for i in range(3,n)];g[n]

Answer 8

Python - 60 chars

n=20
g=[1,2,2]
for i in range(3,n):g+=[i]*g[i-1]
print g[n]

Answer 9

Perl, 48 chars

(@a=(@a,($,)x($a[$,++]||$,)))<$_?redo:say$,for<>

Input on stdin, output to stdout. Needs Perl 5.10+ and the -M5.010 to enable the sayfeature. Takes about O(n²) time due to inefficient array manipulation, but still fast enough to easily calculate up to the 100,000th term.

Answer 10

#include<iostream>
using namespace std;
#include<math.h>
int main()
{
    float T=(1+pow(5,.5))/2;
    long long int t,n,i;

    cin>>t;
    while(t--)
    {
        float f,g;
        cin>>n;
        f=pow(T,2-T);
        g=pow(n,T-1);
        if(f*g - (long long int)(f*g)>=0.5)
        {
            cout<< (long long int)(f*g)+1<<"\n";
        }
        else
        {
            cout<< (long long int)(f*g)<<"\n";
        }
    }
    return 0;
}