Sign up ×
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
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

17 Answers 17

up vote 3 down vote accepted

GolfScript (31 chars)

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


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


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):


Much faster, but at 89 characters would be:


Which is O(n)

share|improve this answer

Python - 60 chars

for i in range(3,n):g+=[i]*g[i-1]
print g[n]
share|improve this answer
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
   f 20
   f 100000

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

share|improve this answer
int k=2,l=2,c=2,j=1,m,t;
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
@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


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

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 '14 at 23:39
Thanks! I hope to stick around. – user1502040 Mar 12 '14 at 23:50

Julia - 28

By a recursive way:



[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

Mathematica, 27 bytes


Another recursive solution.

share|improve this answer

CJam, 14 bytes

CJam is much younger than this challenge, so this answer is not eligible for the green checkmark. However, it's quite rare that you get to use j this nicely, so I wanted to post it anyway.


Test it here.


j is basically the "memoised recursion operator". It takes an integer N, an array and a block F. The array is used to initialise the memoisation: the element at index i will be returned for F(i). j then computes F(N), either by looking it up, or by running the block (with n on the stack) if the value hasn't been memoised yet. The really nifty feature is that within the block, j only takes an integer i, and calls F(i) recursively. So here is the code:

l~             "Read and eval input.";
  2,           "Push a 2-range onto the stack, i.e. [0 1]. The first value is irrelevant
                but the second value is the base case of the recursion.";
    {       }j "Compute F(N).";
     _(        "Duplicate i and decrement to i-1.";
       jj      "Compute F(F(i-1)).";
         -     "Subtract from i.";
          j    "Compute F(n-F(F(i-1))).";
           )   "Increment the result.";
share|improve this answer

J, 16 bytes


    (<:{1($1+I.)^:[~]) every 1+i.20  NB. results for inputs 1..20
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8

This solution is heavily based on algorithmshark's solution to a similar problem. You can find some explanation about this method there.

J, 33 bytes

In this approach I build up a sequence h(k) with the values of the first indexes i where the g(i)=k so h = 1 2 4 6 9 12 16.... We can get h(k) fairly simply from h(1..k-1) with the expression ({:+1+[:+/#<:]) where the input is h(1..k-1).

Computing the output from h is straightforward. h ([:+/]>:[) input

[:+/]>:1 2(,{:+1+[:+/#<:])@]^:[~]
share|improve this answer
using namespace std;
int main()
    float T=(1+pow(5,.5))/2;
    long long int t,n,i;

        float f,g;
        if(f*g - (long long int)(f*g)>=0.5)
            cout<< (long long int)(f*g)+1<<"\n";
            cout<< (long long int)(f*g)<<"\n";
    return 0;
share|improve this answer

JavaScript - 48 Characters


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

Edit - JavaScript - 46 Characters


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

Edit 2 - ECMAScript 6 - 27 Characters


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

share|improve this answer

Prelude, 69 55 54 bytes

?1-(v  #1)-
1   0v ^(#    0 (1+0)#)!
    (#)  ^#1-(0)#

If a standard compliant interpreter is used, this takes input and output as byte values. To actually use decimal numbers on STDIN/STDOUT, you'd need the Python interpreter with NUMERIC_OUTPUT = True and an additional option NUMERIC_INPUT = True.


The skeleton of the program is

?1-(    1 -
1                     )!

We read the input N onto the first voice and decrement it to get N-1. We also initialise the second voice to 1. Then we loop N-1 one times, each iteration of which gets the next value of the sequence on the second stack. At the end we print the Nth number.

The idea of the program is to put each element of the sequence in a queue on the third voice, and to decrement the head of that queue in each iteration. When the head reaches 0, we increment the value of the sequence and remove that 0.

Now the issue is that Prelude uses stacks and not queues. So we need to shift around that stack a bit to use it like a queue.

v  #
0v ^

This copies the current value of the sequence to the first voice (as a temporary copy), pushes a 0 onto the second voice (to mark the end of the queue). And then performs a loop to shift (and thereby reverse) the third stack onto the second. After the loop, we put the copy of the current sequence value on top of the second stack (which is the tail of our queue).


This looks a bit ugly, but essentially it's a loop that shifts the stack back onto the third voice. Since the ) is in the same column as the shifting instructions, the 0 we put on the second voice earlier will also end up on the third voice, so we need to remove it with another #. Then decrement the top of the 3rd voice, i.e. the head of the queue.

Now it gets a bit annoying - we want run some code when that value is 0, but Prelude's only control structure (the loop) only responds to non-zero values.

 0 (1+0)#

Note that the top of the second voice is truthy (since the Golomb sequence does not contain any 0s). So the workload goes into that voice (the latter pair of parentheses). We just need to prevent that from happening if the head of the queue isn't 0 yet. So first we have a "loop" on the third voice which pushes a 0 onto the second voice if the head of the queue is still non-zero. We also put a 0 on the third voice to exit the loop right away. The # on the third voice then either removes that 0, or removes the head of the queue if that was already zero. Now that second loop is only entered if the head of the queue was zero (and the 0 on the second voice was never pushed). In that case we increment the current value of the sequence and push a 0 to exit the loop. Lastly, there will always be a 0 on top of the stack, which we need to discard.

I told you that logical negation is annoying in Prelude...

share|improve this answer

Your Answer


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.