# 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_(k-1)*f_(n+1)*f_n | ||

+ | + f_(k-2)*(f_n)^2 | ||

+ | |||

<haskell> | <haskell> | ||

− | problem_104 = | + | 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 (k-1) | ||

+ | fkm2 = fibo (k-2) | ||

+ | 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_(k-1)*f_(n+1)*f_n + f_(k-2)*(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 (k-1) fkm2 = fibo (k-2) 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