Euler problems/101 to 110
From HaskellWiki
(Removing category tags. See Talk:Euler_problems) 

Line 27:  Line 27:  
Solution: 
Solution: 

+  
+  Very nice problem. I didnt realize you could deal with the precision problem. 

+  Therefore I used this identity to speed up the fibonacci calculation: 

+  f_(2*n+k) 

+  = f_k*(f_(n+1))^2 

+  + 2*f_(k1)*f_(n+1)*f_n 

+  + f_(k2)*(f_n)^2 

+  
<haskell> 
<haskell> 

−  problem_104 = undefined 
+  import Data.List 
+  import Data.Char 

+  
+  fibos = rec 0 1 

+  where 

+  rec a b = a:rec b (a+b) 

+  
+  fibo_2nk n k = 

+  let 

+  fk = fibo k 

+  fkm1 = fibo (k1) 

+  fkm2 = fibo (k2) 

+  fnp1sq = fnp1^2 

+  fnp1 = fibo (n+1) 

+  fn = fibo n 

+  fnsq = fn^2 

+  in 

+  fk*fnp1sq + 2*fkm1*fnp1*fn + fkm2*fnsq 

+  
+  fibo x = 

+  let 

+  threshold = 30000 

+  n = div x 3 

+  k = n+mod x 3 

+  in 

+  if x < threshold 

+  then fibos !! x 

+  else fibo_2nk n k 

+  
+  findCandidates = rec 0 1 0 

+  where 

+  m = 10^9 

+  rec a b n = 

+  let 

+  continue = rec b (mod (a+b) m) (n+1) 

+  isBackPan a = (sort $ show a) == "123456789" 

+  in 

+  if isBackPan a 

+  then n:continue 

+  else continue 

+  search = 

+  let 

+  isFrontPan x = (sort $ take 9 $ show x) == "123456789" 

+  in 

+  map fst 

+  $ take 1 

+  $ dropWhile (not.snd) 

+  $ zip findCandidates 

+  $ map (isFrontPan.fibo) findCandidates 

+  
+  problem_104 = search 

</haskell> 
</haskell> 

−  +  It took 8 sec on a 2.2Ghz machine. 

== [http://projecteuler.net/index.php?section=view&id=105 Problem 105] == 
== [http://projecteuler.net/index.php?section=view&id=105 Problem 105] == 

Find the sum of the special sum sets in the file. 
Find the sum of the special sum sets in the file. 
Revision as of 16:40, 30 November 2007
Contents 
1 Problem 101
Investigate the optimum polynomial function to model the first k terms of a given sequence.
Solution:
problem_101 = undefined
2 Problem 102
For how many triangles in the text file does the interior contain the origin?
Solution:
problem_102 = undefined
3 Problem 103
Investigating sets with a special subset sum property.
Solution:
problem_103 = undefined
4 Problem 104
Finding Fibonacci numbers for which the first and last nine digits are pandigital.
Solution:
Very nice problem. I didnt realize you could deal with the precision problem. Therefore I used this identity to speed up the fibonacci calculation: f_(2*n+k) = f_k*(f_(n+1))^2 + 2*f_(k1)*f_(n+1)*f_n + f_(k2)*(f_n)^2
import Data.List import Data.Char fibos = rec 0 1 where rec a b = a:rec b (a+b) fibo_2nk n k = let fk = fibo k fkm1 = fibo (k1) fkm2 = fibo (k2) fnp1sq = fnp1^2 fnp1 = fibo (n+1) fn = fibo n fnsq = fn^2 in fk*fnp1sq + 2*fkm1*fnp1*fn + fkm2*fnsq fibo x = let threshold = 30000 n = div x 3 k = n+mod x 3 in if x < threshold then fibos !! x else fibo_2nk n k findCandidates = rec 0 1 0 where m = 10^9 rec a b n = let continue = rec b (mod (a+b) m) (n+1) isBackPan a = (sort $ show a) == "123456789" in if isBackPan a then n:continue else continue search = let isFrontPan x = (sort $ take 9 $ show x) == "123456789" in map fst $ take 1 $ dropWhile (not.snd) $ zip findCandidates $ map (isFrontPan.fibo) findCandidates problem_104 = search
It took 8 sec on a 2.2Ghz machine.
5 Problem 105
Find the sum of the special sum sets in the file.
Solution:
problem_105 = undefined
6 Problem 106
Find the minimum number of comparisons needed to identify special sum sets.
Solution:
problem_106 = undefined
7 Problem 107
Determining the most efficient way to connect the network.
Solution:
problem_107 = undefined
8 Problem 108
Solving the Diophantine equation 1/x + 1/y = 1/n.
Solution:
problem_108 = undefined
9 Problem 109
How many distinct ways can a player checkout in the game of darts with a score of less than 100?
Solution:
problem_109 = undefined
10 Problem 110
Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.
Solution:
problem_110 = undefined