# Definition

From the description on OEIS A006345:

To find a(n), consider either a 1 or a 2. For each, find the longest repeated suffix, that is, for each of a(n)=1,2, find the longest sequence s with the property that the sequence a(1),...,a(n) ends with ss. Use the digit that results in the shorter such suffix. a(1) = 1.

# Worked-out Example

a(1)=1.

If a(2)=1, we will have the sequence 1 1 where the longest doubled substring from the end is 1. If a(2)=2 instead, then it would be the empty substring. Therefore a(2)=2.

When n=6, we choose between 1 2 1 1 2 1 and 1 2 1 1 2 2. In the first choice, 1 2 1 is doubled consecutively from the end. In the second choice, it is 2 instead. Therefore, a(6)=2.

When n=9, we choose between 1 2 1 1 2 2 1 2 1 and 1 2 1 1 2 2 1 2 2. In the first choice, the longest doubled consecutive substring is 2 1, while in the second choice 1 2 2 is doubled consecutively at the end. Therefore a(9)=1.

Given n, return a(n).

# Specs

• n will be positive.
• You can use 0-indexed instead of 1-indexed. In that case, please state so in your answer. Also, in that case, n can be 0 also.

# Testcases

The testcases are 1-indexed. However, you can use 0-indexed.

n  a(n)
1  1
2  2
3  1
4  1
5  2
6  2
7  1
8  2
9  1
10 1
11 2
12 1
13 2
14 2
15 1
16 1
17 2
18 1
19 1
20 1


# References

• In the test case of n=9, the first choice 1 2 1 1 2 2 1 2 1 has the doubled substring 2 1 at the end. Aug 1, 2016 at 19:02
• Note that the linked OEIS page has a golfed Perl solution of ~43 bytes. Aug 2, 2016 at 1:21

s!l|take l s==take l(drop l s)=l|1<2=s!(l-1)
g[w,x]|w<x=1|1<2=2
a 1=1
a n=g$(\s x->(x:s)!n)(a<$>[n-1,n-2..1])<$>[1,2]  • Do you really need (\x->(\s->...? Otherwise you could write (\x s->.... Aug 1, 2016 at 20:53 • That helps to save a few Aug 1, 2016 at 22:09 • Welcome to PPCG! Aug 1, 2016 at 22:12 • Instead of using the sane upper bound div ..., you can use the shorter n. The extra comparisons will all return false and not change the result. Aug 1, 2016 at 22:57 • ooh nice, I guess I assumed take would crash if given too large a value Aug 1, 2016 at 23:10 ## Python, 137 bytes def a(n,s=[0],r=lambda l:max([0]+filter(lambda i:l[-i:]==l[-i*2:-i],range(len(l))))): for _ in[0]*n:s+=[r(s+[0])>r(s+[1])] return-~s[n]  This solution is using 0-based indexing. # Jelly, 252422 20 bytes 2 bytes thanks to Dennis. 2;€µḣJf;€$ṪLµÞḢ
Ç¡Ḣ


Try it online!

A port of my answer in Pyth.

Ç¡Ḣ   Main chain

¡    Repeat for (input) times:
Ç         the helper chain
Ḣ   Then take the first element

2;€µḣJf;€$ṪLµÞḢ Helper chain, argument: z 2;€ append z to 1 and 2, creating two possibilities µ µÞ sort the possibilities by the following: ḣJ generate all prefixes from shortest to longest ;€ append the prefixes to themselves f$           intersect with the original set of prefixes
Ṫ          take the last prefix in the intersection
L         find its length
Ḣ   take the first (minimum)


# Mathematica, 84 bytes

a@n_:=a@n=First@MinimalBy[{1,2},Array[a,n-1]~Append~#/.{___,b___,b___}:>Length@{b}&]


;€¬;\€Z;/f;€$ṪḢ; 1Ç¡o2Ḣ  # MATL, 34 bytes vXKi:"2:"K@h'(.+)\1$'XXgn]>QhXK]0)


### Explanation

v             % Concatenate stack vertically: produces empty array
XK            % Copy to clipboard K. This clipboard holds the current sequence
i:            % Take input n. Generate vector [1 2 ... n]
"             % For each k in [1 2 ... n]
2:          %   Push [1 2]. These are the possible digits for extending the sequence
"           %     For each j in [1 2]
K         %       Push contents of clipboard K (current sequence)
@         %       Push j (1 or 2)
h         %       Concatenate horizontally: gives a possible extension of sequence
'(.+)\1$' % String to be used as regex pattern: maximal-length repeated suffix XX % Regex match gn % Convert to vector and push its length: gives length of match ] % End. We now have the suffix lengths of the two possible extensions > % Push 1 if extension with "1" has longer suffix than with "2"; else 0 Q % Add 1: gives 2 if extension with "1" produced a longer suffix, or 1 % otherwise. This is the digit to be appended to the sequence h % Concatenate horizontally XK % Update clipboard with extended sequence, for the next iteration ] % End 0) % Get last entry (1-based modular indexing). Implicitly display  # Python 2, 94 bytes import re s='1' exec"s+=3-int(re.search(r'(.*)(.)\\1$',s).groups()[1]);"*input()
print s[-1]


Uses 0-based indexing. Test it on Ideone.

# Pyth, 26 bytes

huh.mleq#.<T/lT2._b+RGS2QY


Test suite.

### Explanation

When n = 6, we choose between 1 2 1 1 2 1 and 1 2 1 1 2 2.

We generate these two possibilities, and then look at their suffixes.

For the first one, the suffixes are: 1, 2 1, 1 2 1, 1 1 2 1, 2 1 1 2 1, 1 2 1 1 2 1.

We filter for doubled suffixes by checking if they are the same after rotating them for their length divided by 2 (it turns out that this check is not perfect, because it confirms 1 and 2 also).

We take the last doubled suffix and then take its length.

We then choose the possibility that corresponds to a minimum length generated above.

Then we proceed to the next value of n.

For the purpose of this program, it was golfier to generate the reversed array instead.

huh.mleq#.<T/lT2._b+RGS2QY
u                      QY   repeat Q (input) times,
storing the temporary result in G:
+RGS2         prepend 1 and 2 to G,
creating two possibilities
.m             b              find the one that
makes the following minimal:
._                   generate all prefixes
q#                            filter for prefixes as T
that equals:
.<T/lT2                         T left-rotated
by its length halved
e                              take the last one
l                               generate its length
h                              take the first minimal one
h                                take the first one from the generated
array and implicitly print it out


# Pyth, 46 29 bytes

Took some inspiration from @Leaky Nun's excellent Pyth answer. Tried to see if there was a shorter way using strings. Still 3 bytes short!

huh.melM+kf!x>blTT._bm+dGS2Qk


You can try it out here.

• Using reduce instead of explicit for-loop saves you 4 bytes Aug 2, 2016 at 1:57

# Retina, 51 42 bytes

9 bytes thanks to Martin Ender.

.+
$*x +((.*)(^|2|(?<3>1))\2)x$1$#3 !.$


Try it online!

$a.=/(.*)(.)\1$/^$2for($a)x$_;$_=$a%5+1  The code is 39 bytes long and requires the -p switch (+1 byte). The loop is inspired by the Perl solution on the relevant OEIS page, although I did come up independently with the regular expression. Test it on Ideone. • You have outgolfed OEIS, specifically, Ton Hospel/Phil Carmody... Aug 2, 2016 at 4:36 • Not really comparable since the OEIS script takes no input and prints the whole sequence. Aug 2, 2016 at 4:39 # JavaScript (ES6), 84 Index base 0 n=>eval("s='1';for(r=d=>(s+d).match(/(.*)\\1$/)[0].length;n--;s+=c)c=r(1)>r(2)?2:1")


Less golfed

n=>{
r = d => (s+d).match(/(.*)\1$/)[0].length; c = '1'; for(s = c; n--; s += c) c = r(1) > r(2) ? 2 : 1; return c; }  Test F= n=>eval("s='1';for(r=d=>(s+d).match(/(.*)\\1$/)[0].length;n--;s+=c)c=r(1)>r(2)?2:1")

for(n=0;n<20;n++)console.log(n,F(n))

# Husk, 20 bytes

!¡λ◄(L←SnmDṫ:⁰)ḣ2);1


Same algorithm as Leaky Nun's answers.