Generate n digits of Gijswijt's sequence

Pyth, 25 22 21 bytes

t_u+eSmtfxG*Td1._GGQN

OP confirmed that we only need to handle single-digit numbers. This allowed to store the list as a string of digits. -> Saved 3 bytes

Try it online: Demonstration

Explanation:

t_u+...GQN      implicit: Q = input number
         N      start with the string G = '"'
  u     Q       do the following Q times:
    ...            generate the next number
   +   G           and prepend it to G
 _              print reversed string at the end
t               remove the first char (the '"')

And here's how I generate the next number:

eSmtfxG*Td1._G
           ._G    generate all prefixes of G
  m               map each prefix d to:
    f     1          find the first number T >= 1, so that:
       *Td              d repeated T times
     xG                 occurs at the beginning of G
 S                  sort all numbers
e                   take the last one (maximum)   

21 bytes with lists

_u+eSmhhrcGd8SlGGtQ]1

Try it online: Demonstration

Uses the same ideas of Martin and Peter. At each step I split the string into pieces of length 1, pieces of length 2, ... Then I range-length-encode them and use the maximal first run as next number.

20 bytes with strings

t_u+eSmhhrcGd8SlGGQN

Try it online: Demonstration

Combines the ideas of the two codes above.


CJam, 33 31 30 27 bytes

Thanks to Peter Taylor for saving 1 byte.

1sri({),:)1$W%f/:e`$W=sc+}

Test it here.

Explanation

1s      e# Initialise the sequence as "1".
ri(     e# Read input N and decrement.
{       e# For each I from 0 to N-1...
  )     e#   Increment to get I from 1 to N.
  ,     e#   Turn into a range [0 1 ... I-1].
  :)    e#   Increment each element to get [1 2 ... I].
  1$    e#   Copy sequence so far.
  W%    e#   Reverse the copy.
  f/    e#   For each element x in [1 2 ... I], split the (reversed) sequence
        e#   into (non-overlapping) chunks of length x. These are the potentially
        e#   repeated blocks we're looking for. We now want to find the splitting
        e#   which starts with the largest number of equal blocks.
  :e`   e#   To do that, we run-length encode each list blocks.
  $     e#   Then we sort the list of run-length encoded splittings, which primarily
        e#   sorts them by the length of the first run.
  W=    e#   We extract the last splitting which starts with the longest run.
  sc    e#   And then we extract the length of the first run by flattening
        e#   the list into a string and retrieving the first character.
  +     e#   This is the new element of the sequence, so we append it.
}/

CJam (30 29 27 24 bytes)

'1ri{{)W$W%/e`sc}%$W>+}/

Online demo

This is very much a joint effort with Martin.

  • The clever use of run-length encoding (e`) to identify repetitions is Martin's
  • So is the use of W$ to simplify the stack management
  • I eliminated a couple of increment/decrement operations by using $W>+ special-casing, as explained in the dissection below

My first 30-byte approach:

1ari{,1$f{W%0+_@)</{}#}$W>+}/`

Online demo

Dissection

1a        e# Special-case the first term
ri{       e# Read int n and iterate for i=0 to n-1
  ,1$f{   e#   Iterate for j=0 to i-1 a map with extra parameter of the sequence so far
    W%0+  e#     Reverse and append 0 to ensure a non-trivial non-repeating tail
    _@)</ e#     Take the first j+1 elements and split around them
    {}#   e#     Find the index of the first non-empty part from the split
          e#     That's equivalent to the number of times the initial word repeats
  }
  $W>+    e#   Add the maximal value to the sequence
          e#   NB Special case: if i=0 then we're taking the last term of an empty array
          e#   and nothing is appended - hence the 1a at the start of the program
}/
`         e# Format for pretty printing