-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathproblems71-80.hs
113 lines (92 loc) · 4.39 KB
/
problems71-80.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import Data.Char
import Data.Ratio
import Data.List (group, sort)
import qualified Data.Set as Set
import Math.NumberTheory.Primes (totient, primes)
problem71 = Set.findMax . Set.deleteMax $ fracs
where
fracs = Set.fromList $ map nearestFrac [1..(10^6)]
nearestFrac d = (3*d `div` 7) % d
-- Number of reduced proper fractions for denominator d <= 10^6
-- This is the length of the Farey sequence.
-- totient function is the number of numbers relitively prime to
-- a certain number.
problem72 = sum $ map totient [2..(10^6)]
problem73 = sum [1 | d<-[4..12000],
let lower = (d `div` 3) + 1,
let upper = (d `div` 2),
n <- [lower..upper],
gcd d n == 1 ]
--Probably Could optimize this a little more....
problem74 = length $ filter (==60) $ map (loopLength) [3..999999]
where loopLength x
| x == 169 = 3
| x == 145 = 0
| x == 2 = 0
| x == 1 = 0
| x == 40585 = 0
| x == 363601 = 3
| x == 1454 = 3
| x == 871 = 2
| x == 872 = 2
| x == 45361 = 2
| x == 45362 = 2
| otherwise = 1 + loopLength (facSum x)
facSum x = sum $ map (fac . digitToInt) (show x)
fac x = product [1..x]
problem75 = sum $ filter (==1) $ map length $ group $ sort $ allPerimiters
where allPerimiters = concatMap (\x -> [x,(2*x)..limit]) primativePerimiters
primativePerimiters = [2*m^2 + 2*m*n | m <-[1..mlimit], n<-[1..(m-1)],
(m-n) `mod` 2 == 1,
gcd m n == 1 ]
mlimit = ( fromIntegral . floor . sqrt ) (fromIntegral limit)
limit = 1500000
problem76 = partitions 100
where
partitions = (map partitions' [0..] !!)
partitions' n | n < 0 = 0
| n == 0 = 1
| otherwise = (sum pos) + (sum neg)
where pos = map kthTerm $ takeWhile (\x -> fst x <= n) $ pent_pos
neg = map kthTerm $ takeWhile (\x -> fst x <= n) $ pent_neg
kthTerm (p,k) = (-1)^(abs (k-1)) * partitions (n - p )
pent_pos = map (\k -> (k*(3*k-1) `div` 2, k) ) [1..]
pent_neg = map (\k -> (k*(3*k-1) `div` 2, k) ) [-1,-2..]
problem77 = head $ filter (\x -> numSumPrimes x > 5000) [2..]
where numSumPrimes :: Int -> Integer
numSumPrimes n = ways (takeWhile (<= n) primes') !! n
where primes' = map fromIntegral primes :: [Int]
ways [] = 1 : repeat 0
ways (x:xs) = y
where y = zipWith (+) (ways xs) (replicate x 0 ++ y)
{- Calculate the Partition function using Euler's recursion with
- memoization. This is still pretty slow (takes around ~1h to run on
- Core i5 Macbook). The issue is probably because I'm using a list
- based strategy. Try using a map to speed this up.
-}
problem78 = head $ filter (\x -> partitions x == 0) [0..]
where
partitions :: Int -> Int
partitions = (map partitions' [0..] !!)
partitions' n | n < 0 = 0
| n == 0 = 1
| otherwise = ((sum pos) + (sum neg)) `mod` 10^6
where pos = map kthTerm $ takeWhile (\x -> fst x <= n) $ pent_pos
neg = map kthTerm $ takeWhile (\x -> fst x <= n) $ pent_neg
kthTerm (p,k) = ((-1)^(abs (k-1)) * partitions (n - p ) ) `mod` 10^6
pent_pos = map (\k -> (k*(3*k-1) `div` 2, k) ) [1..]
pent_neg = map (\k -> (k*(3*k-1) `div` 2, k) ) [-1,-2..]
problem79 = 73162890 --By Hand!
problem80 = sum $ [sqrtSum x | x<-[1..100], x `notElem` squareNos]
where intSqrt' :: Integer -> Integer -> Integer -> Integer
--Computes the sqrt of a large integer by bisection
intSqrt' n lbound ubound = let guess = (lbound + ubound) `div` 2 in
if abs( lbound - guess ) < 1
then lbound
else
if guess*guess < n
then intSqrt' n guess ubound
else intSqrt' n lbound guess
sqrtSum x = let m =(show $ intSqrt' (x*10^(202)) 0 (x*10^204))
in sum $ map (digitToInt) $ take 100 m
squareNos = takeWhile (<101) $ map (^2) [1..]