#C19.txt, March 31, 2016, Self-avoiding walks
Help:=proc(): print(` Walks(n), IsBad1(w,m) , IsBad(w,m), FMWalks(n,m), SeqFM(N,m)  `): 
print(`SAW71() , EstimatePars(L)`):
end:

#Walks(n): all the walks using N=I,S=-I,E=1,W=-1 N=[0,1], S=[0,-1], E=[1,0], W=[-1,0]
Walks:=proc(n) local S,w:
option remember:

if n=0 then
  RETURN({[]}):
fi:

S:=Walks(n-1):

{seq( seq([ op(w), i], i in {-1,1,-I,I}),w in S)}:

end:

#IsBad1(w,m): Does the walk w contain a subwalk that loops exactly m steps
IsBad1:=proc(w,m) local i,j:

for i from 1 to nops(w)-m+1 do
 if add(w[i+j],j=0..m-1)=0 then
   RETURN(true):
 fi:
od:
false:
end:

  #IsBad(w,m): Does the walk w contain a subwalk that loops with <=m steps
  IsBad:=proc(w,m) local m1:

  for m1 from 2  by 2 to m do
  if IsBad1(w,m1) then
   RETURN(true):
  fi:
 od:
 false:

  end:
 

#FMwalks(n,m): all the finite-memory
#self-avoiding walks with memory m
#walks using N=I,S=-I,E=1,W=-1 N=[0,1], S=[0,-1], E=[1,0], W=[-1,0]
#such that you never visit a point that you visited in the last m
#steps
FMWalks:=proc(n,m) local W,v,S,a,G,hope:
option remember:

if n=0 then
  RETURN({[]}):
fi:

W:=FMWalks(n-1,m):

S:={1,-1,I,-I}:

G:={}:

for v in W do
 for a in S do 
  hope:=[op(v),a]:
  if not IsBad(hope,m) then
   G:=G union {hope}:
  fi:
 od:
od:

G:
end:

 #SeqFM(N,m): the list of length N whose i-th member is the number of memory-m walks of length i
 SeqFM:=proc(N,m) local n:
 [seq( nops(FMWalks(n,m)), n=0..N)]:

 end:

 #The number of self-avoiding walks from 65 to 71 taken from A001411.txt
  #Is conjectured to be asymptotically mu^n* n^theta where theta is nice
 SAW71:=proc():
 [12066271136346725726547810652,
 31992427160420423715150496804,
 84841788997462209800131419244,
 224916973773967421352838735684,
 596373847126147985434982575724,
 1580784678250571882017480243636,
 4190893020903935054619120005916]:
 end:


#EstimatePars(L)
#log(a(n))=log(C)+ n*log(mu)+theta*log(n)
# Inputs a list of length 3 [[a1,b1],[a2,b2],[a3,b3]]
#finds constants C, mu and theta such that
#fits the data. Output is [C,mu,theta]

 EstimatePars:=proc(L) local eq,var, logC, logmu, theta:
 var:={logC, logmu, theta}:

 eq:={seq(log(L[i][2])=logC+L[i][1]*logmu+theta*log(L[i][1]), i=1..3)}:

  var:=solve(eq,var):

  evalf([exp(subs(var,logC)), exp(subs(var,logmu)),subs(var,theta)]):

end: