# Matthew Russell
# Experimental Math
# Homework 11
# I give permission to post this

#####################################################################################

# Write a Maple procedure CS(n) that inputs a positive integer n and outputs the
# number mu(n) defined in the above-mentioned masterpiece, in other words sequence A094004.
# How far can you go in one hour?

# My work is below. I was able to compute the first 18 terms:
# 1,4,5,8,9,14,15,66,68,70,123,124,125,132,133,134,135,136

#####################################################################################

CS:=proc(n) local best,S:

best:=0:
for S in Inits(n) do
	best:=max(best,Curl(S)):
od:

return best:

end:


# Inits(n): returns the list of all possible starting strings consisting of 2s and 3s
# of length n
Inits:=proc(n) local K,L,l:
option remember:

if n=1 then
	return [[2],[3]]:
else
	K:=[]:
	L:=Inits(n-1):
	for l in L do
		K:=[op(K),[op(l),2],[op(l),3]]:
	od:
	return K:
fi:

end:

# Curl1(L): inputs a starting string L and calculates the next term in the sequence,
# returning a list consisting of the single term added and the entire new sequence
Curl1:=proc(L) local l,curr,posslength,block,block1,j,counter:
option remember:
l:=nops(L):
if l =1 then
	return [1,[op(L),1]]:
fi:
curr:=1:
for posslength from 1 to trunc(l/2) do
	block:=[op(l-posslength+1..l,L)]:
	block1:=block:
	counter:=1:
	for j from 1 while block1=block and (j+1)*posslength<=l do
		block1:=[op(l-posslength*(j+1)+1..l-posslength*(j),L)]:
		if block1=block then
			counter:=counter+1:
		fi:
	od:
	curr:=max(counter,curr):
od:

return [curr,[op(L),curr]]:

end:


# Curl(L): inputs a starting string of 2s and 3s L and returns the length
# of the sequence right before the first 1 appears.
Curl:=proc(L) local l,curr,c,L1,c1,dum:

L1:=L:
c1:=0:
for dum from 0 while c1<>1 do
	c:=Curl1(L1):
	L1:=c[2]:
	c1:=c[1]:
od:

return nops(L1)-1:

end: