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

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.

Given an input of n, output g(n).

Limitations: n < 100000.

Smallest code wins.

• 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

## GolfScript (31 chars)

~([1 2.]2{.2$=[1$)]*@\+\)}3$*;=  Demo • 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 # Jelly, non-competing 10 bytes This answer is non-competing, since the challenge predates the creation of Jelly. ’ßßạ¹ß‘µṖ¡  This uses the recursive formula a(1) = 1, a(n + 1) = 1 + a(n + 1 - a(a(n))) from the OEIS page. Try it online! ### How it works ’ßßạ¹ß‘µṖ¡ Main link. Input: n ’ Decrement; yield n - 1. ßß Recursively call the main link twice, with argument n - 1. ạ¹ Take the absolute difference of a(a(n - 1)) and n. ß Recursively call the main link, with argument n - a(a(n - 1)). ‘ Increment the result, yielding 1 + a(n - a(a(n - 1))). µ Combine the chain to the left into a single link. Ṗ Pop [1, ..., n]. This yields [] iff n == 1. ¡ Execute the chain iff Ṗ returned a non-empty array.  # 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.

# 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) # Haskell, 30 27 Chars g 1=1 g n=1+(g$n-g(g$n-1))  • Welcome to the site! – Jonathan Van Matre Mar 12 '14 at 23:39 ## 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. # 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  # Python - 64 chars n=input() g=[1,2,2] for i in range(3,n):g+=[i]*g[i-1] print g[n]  • 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 # Oasis, 7 bytes (non-competing) Code: n<aae>T  Try it online! Oasis is a language designed by Adnan which is specialized in sequences. Currently, this language can do recursion and closed form. The T at the end is shorthand for 10, which indicates that a(0) = 0 and a(1) = 1. To add more testcases, simply add to the list at the end. n<aae>T n<aae>10 expanded 0 a(0) = 0 1 a(1) = 1 n push n (input) < -1 a a(above) [a is the sequence] a a(above) e a(n-above) > +1  Now we essentially calculated a(n-a(a(n-1))+1. ## 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))))}  ## 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.

# Prelude, 6955 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.

## Explanation

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

 )
(#
^#1-


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)#
(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...

# Mathematica, 27 bytes

f@1=1;f@n_:=1+f[n-f@f[n-1]]


Another recursive solution.

# 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.

l~2,{_(jj-j)}j


Test it here.

## Explanation

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.";


# J, 16 bytes

    <:{1($1+I.)^:[~] (<:{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+[:+/#<:])@]^:[~]


# Brachylog, 13 bytes (non-competing)

1|-₁↰↰:?-ṅ↰+₁


Try it online!

### Explanation

1                Input = 1 = Output
|               Or
-₁↰            a(Input - 1)
↰           a(a(Input - 1))
:?-ṅ       Input - a(a(Input - 1))
↰      a(Input - a(a(Input - 1))
+₁    1 + a(Input - a(a(Input -1))


# 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]

• 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
• Unfortunately it seems you're hard-coding the input, which we don't allow, and assuming a REPL environment, which would make this a snippet. By default, all submissions must be full programs or functions which use one of our default I/O methods rather than snippets. Let me know if you have any questions. – Alex A. Apr 28 '16 at 16:45
• @AlexA. Doing a bit of archeology? – chucksmash Apr 28 '16 at 16:59

# 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

# Haskell, 63 bytes

f n|n<3=n|n<4=2|1>0=foldr1(++)[replicate(f m)m|m<-[1..]]!!(n-1)


This is the naive approach, I was not aware of the very short recurison when I wrote this, but I thought I'd post it anyway, even tough it is longer than all other Haskell implementations, as e.g.

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

and

https://codegolf.stackexchange.com/a/23979/24877