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.

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

Limitations: n < 100000.

Smallest code wins.

Answer 1

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.

Answer 2

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.

Answer 3

GolfScript (31 chars)

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

Demo

Answer 4

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 5

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 6

Haskell, 30 27 Chars

g 1=1
g n=1+(g$n-g(g$n-1))

Answer 7

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.

Answer 8

APL (Dyalog Extended), ¹¹ 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 [1]:
     ⍸      ⍝   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

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

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

Answer 11

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.

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

Answer 12

Python - 64 chars

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

Answer 13

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 14

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 15

Mathematica, 27 bytes

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

Another recursive solution.

Answer 16

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

Answer 17

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+[:+/#<:])@]^:[~]

Answer 18

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

Answer 19

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 20

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

Answer 21

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

Answer 22

05AB1E, 7 bytes

1Ýλè₅₆>

Port of the recursive formula used in @LeakyNun's Oasis answer, so make sure to upvote that answer as well:

$$a(0)=0\\a(1)=1\\a(n)=a(n-a(a(n-1)))+1$$

Try it online or verify all test cases or verify the infinite sequence.

Explanation:

  λ      # Create a recursive environment,
   è     # to output the 0-based (implicit) input'th term
1Ý       # Starting with a(0)=0 and a(1)=1
         # And where every following a(n) is calculated as:
         #  (implicitly push the previous term a(n-1))
    ₅    #  Calculate a(value) using this term: a(a(n-1))
     ₆   #  Calculate a(n-value) using this: a(n-a(a(n-1)))
      >  #  Increase it by 1: a(n-a(a(n-1)))+1