{- |
Description: Support functions for arithmetic problems.
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

These functions were written in support of specific arithmetic problems,
but which turn out to be useful for other problems as well.
-}
module Solutions.Arithmetic (dividesBy, primes, gaussianUnits, gaussianAdd, gaussianMultiply) where

import           Data.Complex

-- | Whether the first argument divides by the second argument.
--
-- Initially written to support "Problems.P31".
dividesBy :: Integral a => a -> a -> Bool
dividesBy :: forall a. Integral a => a -> a -> Bool
dividesBy a
a a
b = a
a a -> a -> a
forall a. Integral a => a -> a -> a
`mod` a
b a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0

-- | List of all prime numbers.
--
-- Computed with an Erastothenes sieve.  Unlike the classic sieve,
-- which strikes out multiples of prime numbers from subsequent numbers,
-- checks the primality of each integer against the prime numbers already determined.
--
-- Initially written to support "Problems.P31".
primes :: Integral a => [a]
primes :: forall a. Integral a => [a]
primes = a
2 a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
odds
  where odds :: [a]
odds = (a -> a) -> a -> [a]
forall a. (a -> a) -> a -> [a]
iterate (a -> a
next (a -> a) -> (a -> a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
2+)) a
3
        next :: a -> a
next a
n
          | (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (a
n `dividesBy`) (a -> [a]
candidates a
n) = a -> a
next (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ a
na -> a -> a
forall a. Num a => a -> a -> a
+a
2
          | Bool
otherwise                          = a
n
        candidates :: a -> [a]
candidates a
n = (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (\a
k -> a
ka -> a -> a
forall a. Num a => a -> a -> a
*a
k a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
n) [a]
odds

-- | List of Gaussian integer units.  I.e., \(1\), \(i\), \(-1\), and \(-i\).
gaussianUnits :: [Complex Integer]
gaussianUnits :: [Complex Integer]
gaussianUnits = [ Integer
1 Integer -> Integer -> Complex Integer
forall a. a -> a -> Complex a
:+ Integer
0, Integer
0 Integer -> Integer -> Complex Integer
forall a. a -> a -> Complex a
:+ Integer
1, (-Integer
1) Integer -> Integer -> Complex Integer
forall a. a -> a -> Complex a
:+ Integer
0, Integer
0 Integer -> Integer -> Complex Integer
forall a. a -> a -> Complex a
:+ (-Integer
1) ]

-- | Add two Gaussian integers.
gaussianAdd :: Complex Integer -> Complex Integer -> Complex Integer
gaussianAdd :: Complex Integer -> Complex Integer -> Complex Integer
gaussianAdd (Integer
a :+ Integer
b) (Integer
c :+ Integer
d) = (Integer
aInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
+Integer
c) Integer -> Integer -> Complex Integer
forall a. a -> a -> Complex a
:+ (Integer
bInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
+Integer
d)

-- | Multiply two Gaussian integers.
gaussianMultiply :: Complex Integer -> Complex Integer -> Complex Integer
gaussianMultiply :: Complex Integer -> Complex Integer -> Complex Integer
gaussianMultiply (Integer
a :+ Integer
b) (Integer
c :+ Integer
d) = (Integer
aInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
c Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
bInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
d) Integer -> Integer -> Complex Integer
forall a. a -> a -> Complex a
:+ (Integer
aInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
d Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
bInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
c)