# 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? Sep 18, 2012 at 9:41
• In Haskell, you can use this: golomb=1:2:2:concat(zipWith replicate(drop 2 golomb)[3..]) Sep 18, 2012 at 10:01
• @PeterTaylor: I didn't know that. Sep 18, 2012 at 23:19

# Jelly, 10 bytes

’ßßạ¹ß‘µṖ¡


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.


~([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.) Sep 24, 2012 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. Sep 24, 2012 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.

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

# 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! Mar 12, 2014 at 23:39 # APL (Dyalog Classic), 24 19 bytes {⍵=1:1⋄1+∇⍵-∇ ∇⍵-1}  -5 bytes from ngn's suggestion. Try it online! Same as the recursive function used in the PHP answer. {⍵=1:1⋄1+∇(⍵-∇(∇(⍵-1)))} ⍵(left arg) is n 1+∇(⍵-∇(∇(⍵-1))) recursive step: return 1 + f(n - f(f(n - 1))) if n is not 1. ⍵=1:1 if n is 1, then return 1.  • you can rm all ( ) and insert a space between the two ∇s – ngn Aug 24, 2020 at 14:59 • Please don't use Classic unless there's a really good reason to do so. – Adám Sep 8, 2020 at 9:52 # APL (Dyalog Extended), 11 10 bytes ⊢/⎕⍴∘⍸⍣≡,1  Try it online! -1 byte by converting to a full program, thanks to Adám. Also works in Dyalog APL 18.0. (TIO's version is 17.1, so Extended is used for the extended functionality of ⍸.) A port of randomra's J answer as a full program. ⊢/⎕⍴∘⍸⍣≡,1 ⍣≡ ⍝ Repeat until convergence ,1 ⍝ with the starting value of : ⍸ ⍝ Convert [a b c ...] into a copies of 1, b copies of 2, ... ⎕⍴∘ ⍝ and take first n values (recycling values if necessary) ⊢/ ⍝ Get the rightmost element  • -1: ⊢/⎕⍴∘⍸⍣≡,1 Try it online! – Adám Sep 14, 2020 at 5:49 ## 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... Sep 22, 2012 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))))}  ## 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

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 :) Sep 22, 2012 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 Sep 22, 2012 at 2:05
• It saves two characters over if I had done traditional nested loops :) Sep 22, 2012 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. Apr 28, 2016 at 16:45
• @AlexA. Doing a bit of archeology? Apr 28, 2016 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

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