Difference between revisions of "Euler problems/101 to 110"
(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> |
||
+ | 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 |
||
+ | |||
⚫ | |||
</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
Problem 101
Investigate the optimum polynomial function to model the first k terms of a given sequence.
Solution:
problem_101 = undefined
Problem 102
For how many triangles in the text file does the interior contain the origin?
Solution:
problem_102 = undefined
Problem 103
Investigating sets with a special subset sum property.
Solution:
problem_103 = undefined
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.
Problem 105
Find the sum of the special sum sets in the file.
Solution:
problem_105 = undefined
Problem 106
Find the minimum number of comparisons needed to identify special sum sets.
Solution:
problem_106 = undefined
Problem 107
Determining the most efficient way to connect the network.
Solution:
problem_107 = undefined
Problem 108
Solving the Diophantine equation 1/x + 1/y = 1/n.
Solution:
problem_108 = undefined
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
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