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

# Task

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. – Sherlock9 Aug 1 '16 at 19:02
• Note that the linked OEIS page has a golfed Perl solution of ~43 bytes. – liori Aug 2 '16 at 1:21

## Haskell, 146140137133 118 bytes

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->.... – flawr Aug 1 '16 at 20:53 • That helps to save a few – Program man Aug 1 '16 at 22:09 • Welcome to PPCG! – betseg Aug 1 '16 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. – Christian Sievers Aug 1 '16 at 22:57 • ooh nice, I guess I assumed take would crash if given too large a value – Program man Aug 1 '16 at 23:10 ## Python, 137 bytes def a(n,s=,r=lambda l:max(+filter(lambda i:l[-i:]==l[-i*2:-i],range(len(l))))): for _ in*n:s+=[r(s+)>r(s+)] 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());"*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,
start with Y (empty array),
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 – Leaky Nun Aug 2 '16 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 port of this answer.

$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... – Leaky Nun Aug 2 '16 at 4:36 • Not really comparable since the OEIS script takes no input and prints the whole sequence. – Dennis Aug 2 '16 at 4:39 # JavaScript (ES6), 84 Index base 0 n=>eval("s='1';for(r=d=>(s+d).match(/(.*)\\1$/).length;n--;s+=c)c=r(1)>r(2)?2:1")


Less golfed

n=>{
r = d => (s+d).match(/(.*)\1$/).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$/).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.