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