Euler problems/101 to 110
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