# My Weblog

## Project Euler Problem 94

Project Euler problem 94 is similar to problem 100 but bit tricky in statement “third differs by no more than one unit”. Let if two sides have length a and third has (2b) so according to statement $a = 2*b \pm 1$ .Doing a bit analysis you will get $b = \frac { 2 + \sqrt (1+3{k^2} )} 3$ and $\frac {(-2)+\sqrt (1+3{k^2})} 3$. The only thing that bugged me for almost hour was difference by 2. The project euler forum states that (1,1,0) and (1,1,2) are not valid.

import Data.List

contiNuedFraction::Integer->[Integer]
contiNuedFraction n=
let
d=truncate.sqrt.fromIntegral $n lst=iterate helpFun (d,0,1) helpFun (a_0,p_0,q_0)=(a_1,p_1,q_1) where p_1=a_0*q_0-p_0 q_1=div (n-p_1^2) q_0 a_1=div (d+p_1) q_1 in [a|(a,_,_)<-lst] pellsolver::Integer->[(Integer,Integer)] pellsolver n= let d=truncate.sqrt.fromIntegral$ n
lst=takeWhile (/=2*d) $contiNuedFraction n len=length lst r=take (if even len then len else 2*len)$ contiNuedFraction n
p_0=r!!0
p_1=(r!!0)*(r!!1)+1
q_0=1
q_1=r!!1
(pfinal,_)=foldl recFun (p_1,p_0) $drop 2 r (qfinal,_)=foldl recFun (q_1,q_0)$ drop 2 r where
recFun (p_1,p_0) a=(a*p_1+p_0,p_1)
in iterate (helpFun (pfinal,qfinal)) $(pfinal,qfinal) where helpFun (x_1,y_1) (x_k,y_k)=(x_1*x_k+n*y_1*y_k,x_1*y_k+y_1*x_k) solve = let lst_1=filter (\(x,_)->mod (2+x) 3 ==0 )$ pellsolver 3
lst_2=[(6*p-2)|(x,_)<-lst_1,let p=div (x+2) 3]
lst_3=filter  (\(x,_)->mod (x-2) 3 ==0 ) $pellsolver 3 lst_4=[(6*p+2)|(x,_)<-lst_3,let p=div (x-2) 3] in (sum.takeWhile (<=10^9)$ lst_2) + (sum.takeWhile (<=10^9) \$ lst_4)-2