Home

PureScript solution to Project Euler problem 46

2021-Jul-30 21:42
purescriptproject-euler

Problem details at Project Euler problem 46 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
module Euler046Test (euler46suite) where
 
import Prelude
 
import Data.Maybe (Maybe(..))
import Euler046 (euler46, isGoldbach, primes)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler46suite :: TestSuite
euler46suite =
  suite "Euler 46" do
    test "Warmup" do
      let isGoldbachT :: Int -> Boolean
          isGoldbachT n = isGoldbach (primes n) n
 
      Assert.equal true (isGoldbachT 9)
      Assert.equal true (isGoldbachT 15)
      Assert.equal true (isGoldbachT 21)
      Assert.equal true (isGoldbachT 25)
      Assert.equal true (isGoldbachT 27)
      Assert.equal true (isGoldbachT 33)
 
    test "Real" do
      Assert.equal (Just 5777) (euler46 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
module Euler046 where
 
import Prelude
 
import Data.Array (filter, head, range)
import Data.Int (even, fromNumber, toNumber)
import Data.Maybe (Maybe, maybe)
import Data.Set (Set, fromFoldable, member)
import Math (sqrt)
 
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 -> Set Int
primes n = fromFoldable <<< filter isPrime $ range 2 n
 
isSquare :: Int -> Boolean
isSquare = maybe false (const true) <<< fromNumber <<< sqrt <<< toNumber
 
isDoubleSquare :: Int -> Boolean
isDoubleSquare n = even n && isSquare (n `div` 2)
 
goldbach :: Set Int -> Int -> Int -> Boolean
goldbach ps j n = (n - 2 * j * j) `member` ps
 
isGoldbach :: Set Int -> Int -> Boolean
isGoldbach ps n =
  let go j
        | j > n - 2       = false
        | goldbach ps j n = true
        | otherwise       = go (j + 1)
  in go 1
 
euler46 :: Unit -> Maybe Int
euler46 _ =
  let n = 10000
      ps = primes n
      odds = map (\j -> 2 * j + 1) (range 1 n)
      cands = filter (\j -> not (j `member` ps)) odds
  in head $ filter (not <<< isGoldbach ps) cands