Generate n digits of Gijswijt's sequence

Question

Introduction

Gijswijt's sequence (A090822) is famously really, REALLY slow. To illustrate:

• The first 3 appears in the 9th term (alright).
• The first 4 appears in the 220th term (a long way away, but feasible).
• The first 5 appears at (approximately) the 10^(10^23)th term (just no).
• No one really even knows where the first 6 is... it's suspected it's at the...

  2^(2^(3^(4^5)))th term.

You can assume that you won't have to deal with a two-digit number.

The sequence is generated like so:

1. The first term is 1.
2. Each term after that is the amount of repeating "blocks" previous to it (if there are multiple repeating "blocks", the largest amount of repeating blocks is used).

To clarify, here are the first few terms.

1 -> 1, 1 (one repeating block (1), so the digit recorded is 1)

1, 1 -> 1, 1, 2 (two repeating blocks (1), so the digit recorded is 2)

1, 1, 2 -> 1, 1, 2, 1 (one repeating block (2 or 1, 1, 2), so the digit recorded is 1)

1, 1, 2, 1 -> 1, 1, 2, 1, 1 (you get the idea)

1, 1, 2, 1, 1 -> 1, 1, 2, 1, 1, 2

1, 1, 2, 1, 1, 2 -> 1, 1, 2, 1, 1, 2, 2 (two repeating blocks (1, 1, 2), so the digit recorded is 2)

Task

Your task is, as stated in the question, to generate n digits of the Gijswijt sequence.

Instructions

• The input will be an integer n.
• Your code can output the digits in any form (a list, multiple outputs, etc.).

This is code golf, so shortest code in bytes wins.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

Haskell, 97 bytes

f 1=[1]
f n|x<-f$n-1=last[k|k<-[1..n],p<-[1..n],k*p<n,take(k*p)x==([1..k]>>take p x)]:x
reverse.f

The third line defines an anonymous function that takes an integer and returns a list of integers. See it in action.

Explanation

The helper function f constructs the sequence in reverse, by recursively checking whether the previous sequence begins with a repeated block. k is the number of repetitions, and p is the length of the block.

f 1=[1]                                   -- Base case: return [1]
f n|x<-f$n-1=                             -- Recursive case; bind f(n-1) to x.
  last[k|k<-[1..n],                       -- Find the greatest element k of [1..n] such that
  p<-[1..n],                              -- there exists a block length p such that
  k*p<n,                                  -- k*p is at most the length of x, and
  take(k*p)x                              -- the prefix of x of length p*k
    ==                                    -- is equal to
  ([1..k]>>take p x)                      -- the prefix of length p repeated k times.
  ]:x                                     -- Insert that k to x, and return the result.
reverse.f                                 -- Composition of reverse and f.

Answer 5

Pyth, 41 38 bytes

J]1VSQ=J+h.MZmh+fn@c+J0dT<JdSNZSNJ;P_J

Try it online!

Answer 6

Retina, 66 60 bytes

+1`((\d+)?(?<1>\2)*(?<!\3(?>(?<-1>\3)*)(?!.*\2)(.+)))!
$1$#1

Input is a unary integer using ! as the digit (although that could be changed to any other non-numeric character). Output is simply a string of digits.

Try it online! (Alternatively, for convenience here's a version that takes decimal input.)

For testing purposes, this can be sped up a lot with a small modification, which allows testing of input 220 in under a minute:

+1`((\d+)?(?<1>\2)*(?=!)(?<!\3(?>(?<-1>\3)*)(?!.*\2)(.+)))!
$1$#1

Try it online! (Decimal version.)

If you want to test even larger numbers, it's best to just feed it some massive input and put a : after the initial +. This will make Retina print the current sequence each time it finishes computing a new digit (with all the digits off-by-one).

Explanation

The solution consists of a single regex substitution, which is applied to the input repeatedly until the result stops changing, which in this case happens because the regex no longer matches. The + at the beginning introduces this loop. The 1 is a limit which tells Retina only to replace the first match (this is only relevant for the very first iteration). In each iteration, the stage replaces one ! (from the left) with the next digit of the sequence.

As usual, if you need a primer on balancing groups I refer you to my SO answer.

Here is an annotated version of the regex. Note that the goal is to capture the maximum number of repeated blocks in group 1.

(                 # Group 1, this will contain some repeated block at the end
                  # of the existing sequence. We mainly need this so we can
                  # write it back in the substitution. We're also abusing it
                  # for the actual counting but I'll explain that below.
  (\d+)?          # If possible (that is except on the first iteration) capture
                  # one of more digits into group 2. This is a candidate block
                  # which we're checking for maximum repetitions. Note that this
                  # will match the *first* occurrence of the block.
  (?<1>\2)*       # Now we capture as many copies of that block as possible
                  # into group 1. The reason we use group 1 is that this captures
                  # one repetition less than there is in total (because the first
                  # repetition is group 2 itself). Together with the outer
                  # (unrelated) capture of the actual group one, we fix this
                  # off-by-one error. More importantly, this additional capture
                  # from the outer group isn't added until later, such that the
                  # lookbehind which comes next doesn't see it yet, which is
                  # actually very useful.
                  # Before we go into the lookbehind note that at the end of the
                  # regex there's a '!' to ensure that we can actually reach the
                  # end of the string with this repetition of blocks. While this 
                  # isn't actually checked until later, we can essentially assume
                  # that the lookbehind is only relevant if we've actually counted
                  # repetitions of a block at the end of the current sequence.

  (?<!            # We now use a lookbehind to ensure that this is actually the
                  # largest number of repetitions possible. We do this by ensuring
                  # that there is no shorter block which can be matched more
                  # often from the end than the current one. The first time this
                  # is true (since, due to the regex engine's backtracking rules,
                  # we start from longer blocks and move to shorter blocks later),
                  # we know we've found the maximum number of repetitions.
                  # Remember that lookbehinds are matched right-to-left, so
                  # you should read the explanation of the lookbehind from
                  # bottom to top.
    \3            # Try to match *another* occurrence of block 3. If this works,
                  # then this block can be used more often than the current one
                  # and we haven't found the maximum number of repetitions yet.
    (?>           # An atomic group to ensure that we're actually using up all
                  # repetitions from group 1, and don't backtrack.
      (?<-1>\3)*  # For each repetition in group 1, try to match block 3 again.
    )
    (?!.*\2)      # We ensure that this block isn't longer than the candidate
                  # block, by checking that the candidate block doesn't appear
                  # right of it.
    (.+)          # We capture a block from the end into group 3.
  )               # Lookbehind explanation starts here. Read upwards.
)
!                 # As I said above, this ensures that our block actually reaches
                  # the end of the string.

Finally, after this is all done, we write back $1 (thereby deleting the !) as well as the number of captures in the group with $#1 which corresponds to the maximum number of repetitions.

Answer 7

Ruby, 84 bytes

The Retina answer inspired me to do a regex-based solution to find the best sequence instead of somehow counting sequences in an array, but with less of the genius (negative lookbehinds with quantifiers don't seem to be allowed in Ruby, so I doubt I could directly port Retina's answer over anyways)

->n{s='';n.times{s+=(1..n).map{|i|s=~/(\d{#{i}})\1+$/?$&.size/i: 1}.max.to_s};s[-1]}

Given an already-generated sequence s, it maps over all i from 1 to s.length (n was used in this case to save bytes since n>=s.length) and then uses this regex to help calculate the number of repetitions of a subsequence with length i:

/(.{#{i}})\1+$/
/(                 # Assign the following to group 1
  .{#{i}}          # Match `i` number of characters
         )         # End group 1
          \1+      # Match 1 or more repetitions of group 1
             $/    # Match the end of string

If a match is found of that length, it calculates the number of repetitions by dividing the length of the given match $& by i, the length of the subsequence; if no match was found, it is treated as 1. The function then finds the maximum number of repetitions from this mapping and adds that number to the end of the string.