Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
For naïve approaches this is the same as the previous question except that it uses n rather than 2 - n % 1. Do you have any reason to expect answers to be significantly different? –  Peter Taylor Sep 18 '12 at 9:41
1  
In Haskell, you can use this: golomb=1:2:2:concat(zipWith replicate(drop 2 golomb)[3..]) –  FUZxxl Sep 18 '12 at 10:01
    
@PeterTaylor: I didn't know that. –  beary605 Sep 18 '12 at 23:19

13 Answers 13

up vote 2 down vote accepted

GolfScript (31 chars)

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

Demo

share|improve this answer
    
Nice, but have you really tried this with n=99999, and if so, how long did it take? (When I tried it, it ran for an hour before hitting the 100 MiB memory limit I'd set for it and crashing.) –  Ilmari Karonen Sep 24 '12 at 2:43
    
@IlmariKaronen, no. The question doesn't set any limits on memory or time efficiency, so I assume that the bound on the input size is for those languages which have fixed-width ints. –  Peter Taylor Sep 24 '12 at 7:06

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.

share|improve this answer

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)

share|improve this answer

Python - 60 chars

n=20
g=[1,2,2]
for i in range(3,n):g+=[i]*g[i-1]
print g[n]
share|improve this answer
1  
That's nice. I didn't think doing [i]*g[i-1] would do that so I bent over backwards to do it another way; I thought it would behave more like multiplying a matrix by a scalar for some reason... –  chucksmash Sep 22 '12 at 2:12

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))))}
share|improve this answer

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.

share|improve this answer
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();
}
share|improve this answer

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]
share|improve this answer
    
This actually fills the list with a bunch of Nones. Seems to be the "correct" amount of Nones tho :) –  daniero Sep 22 '12 at 0:10
1  
@Daniero yeah it's kind of weird code. I had to run it a couple of times to convince myself it actually worked. It fills the list comprehension with a bunch of Nones since list.append() returns None type. I just used the nested list comprehensions to achieve a nested loop. The only purpose of the list comprehensions here is to cause the code to loop the right number of times - they are throw away values –  chucksmash Sep 22 '12 at 2:05
    
It saves two characters over if I had done traditional nested loops :) –  chucksmash Sep 22 '12 at 2:09

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(n2) time due to inefficient array manipulation, but still fast enough to easily calculate up to the 100,000th term.

share|improve this answer
#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;
}
share|improve this answer

Haskell, 30 27 Chars

g 1=1
g n=1+(g$n-g(g$n-1))
share|improve this answer
    
Welcome to the site! –  Jonathan Van Matre Mar 12 at 23:39
    
Thanks! I hope to stick around. –  user1502040 Mar 12 at 23:50

JavaScript - 48 Characters

for(g=[,i=j=k=1,2];i<1e5;k=--k?k:g[++j])g[i++]=j

Creates a 1-indexed array g containing the sequence values.

Edit - JavaScript - 46 Characters

v=[,1];for(x=2;x<1e5;)v[x]=1+v[x-v[v[x++-1]]]

Creates a 1-indexed array v containing the sequence values.

Edit 2 - ECMAScript 6 - 27 Characters

g=x=>x-1?1+g(x-g(g(x-1))):1

The first two are reasonably fast - the third is very slow

share|improve this answer

Julia - 28

By a recursive way:

a(n)=n==1?1:1+a(n-a(a(n-1)))

Output:

[a(i) for i=1:20]'
1x20 Array{Int64,2}:
 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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