Home

PureScript solution to Project Euler problem 47

2021-Aug-01 22:08
purescriptproject-euler

Problem details at Project Euler problem 47 page.

Test

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
module Euler047Test (euler47suite) where
 
import Prelude
 
import Data.List (fromFoldable)
import Data.Maybe (Maybe(..))
import Data.Set as S
import Euler047 (divisors, euler47, findConsFac, primes)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler47suite :: TestSuite
euler47suite =
  suite "Euler 47" do
    test "Warmup" do
      let ps = primes 646
          pss = S.fromFoldable ps
 
      Assert.equal (fromFoldable [2, 7]) (divisors ps pss 14)
      Assert.equal (fromFoldable [3, 5]) (divisors ps pss 15)
 
      Assert.equal (fromFoldable [2, 2, 7, 23]) (divisors ps pss 644)
      Assert.equal (fromFoldable [3, 5, 43])    (divisors ps pss 645)
      Assert.equal (fromFoldable [2, 17, 19])   (divisors ps pss 646)
 
      Assert.equal (Just 14)  (findConsFac 2 14)
      Assert.equal (Just 644) (findConsFac 3 644)
 
    test "Real" do
      Assert.equal (Just 134043) (euler47 unit)

Solution

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
module Euler047 where
 
import Prelude
 
import Data.List (List(..), drop, filter, head, range, snoc)
import Data.Maybe (Maybe(..))
import Data.Set (Set, member)
import Data.Set as S
 
isPrime :: Int -> Boolean
isPrime n =
  let go j
        | j * j > n      = true
        | n `mod` j == 0 = false
        | otherwise      = go (j + 1)
  in go 2
 
primes :: Int -> List Int
primes n = filter isPrime $ range 2 n
 
divisors :: List Int -> Set Int -> Int -> List Int
divisors psi pss ni =
  let go ps n ks =
        case head ps of
          Nothing -> Nil
          Just j  ->
            if j == n then ks `snoc` j
            else if n `member` pss then ks `snoc` n
            else if n `mod` j == 0 then go ps (n `div` j) (ks `snoc` j)
            else go (drop 1 ps) n ks
  in go psi ni Nil
 
isConsFac :: List Int -> Set Int -> Int -> Int -> Boolean
isConsFac ps pss fc n =
  let fcnt = S.size <<< S.fromFoldable <<< divisors ps pss
      go j
        | j == n + fc = true
        | fcnt j < fc = false
        | otherwise   = go (j + 1)
  in go n
 
findConsFac :: Int -> Int -> Maybe Int
findConsFac fc n =
  let ps = primes n
      pss = S.fromFoldable ps
      go j
        | j > n                 = Nothing
        | isConsFac ps pss fc j = Just j
        | otherwise             = go (j + 1)
  in go 1
 
euler47 :: Unit -> Maybe Int
euler47 _ = findConsFac 4 200000