-- | Prime number related functions.
module Music.Theory.Math.Prime where

import Data.List {- base -}
import Data.Maybe {- base -}
import Data.Ratio {- base -}

import qualified Data.Numbers.Primes as Primes {- primes -}

import qualified Music.Theory.Function as Function {- hmt -}
import qualified Music.Theory.List as List {- hmt -}
import qualified Music.Theory.Math as Math {- hmt -}
import qualified Music.Theory.Unicode as Unicode {- hmt -}

-- | Alias for 'Primes.primes'.
--
-- > take 12 primes_list == [2,3,5,7,11,13,17,19,23,29,31,37]
primes_list :: Integral i => [i]
primes_list :: forall i. Integral i => [i]
primes_list = forall i. Integral i => [i]
Primes.primes

-- | Give zero-index of prime, or Nothing if value is not prime.
--
-- > map prime_k [2,3,5,7,11,13,17,19,23,29,31,37] == map Just [0 .. 11]
-- > map prime_k [1,4,6,8,9,10,12,14,15,16,18,20,21,22] == replicate 14 Nothing
prime_k :: Integral a => a -> Maybe Int
prime_k :: forall a. Integral a => a -> Maybe Int
prime_k a
i = if forall int. Integral int => int -> Bool
Primes.isPrime a
i then forall a. a -> Maybe a
Just (forall a. (a -> Bool) -> [a] -> Int
List.findIndex_err (forall a. Eq a => a -> a -> Bool
== a
i) forall i. Integral i => [i]
primes_list) else forall a. Maybe a
Nothing

-- | 'maybe' 'error' of 'prime_k'
--
-- > prime_k_err 13 == 5
prime_k_err :: Integral a => a -> Int
prime_k_err :: forall a. Integral a => a -> Int
prime_k_err = forall a. a -> Maybe a -> a
fromMaybe (forall a. HasCallStack => [Char] -> a
error [Char]
"prime_k: not prime?") forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Integral a => a -> Maybe Int
prime_k

{- | Generate list of factors of /n/ from /x/.

> factor primes_list 315 == [3,3,5,7]
> Primes.primeFactors 315 == [3,3,5,7]

As a special case 1 gives the empty list.

> factor primes_list 1 == []
> Primes.primeFactors 1 == []
-}
factor :: Integral i => [i] -> i -> [i]
factor :: forall i. Integral i => [i] -> i -> [i]
factor [i]
x i
n =
    case [i]
x of
      [] -> forall a. HasCallStack => [Char] -> a
error [Char]
"factor: null primes_list input"
      i
i:[i]
x' -> if i
n forall a. Ord a => a -> a -> Bool
< i
i
              then [] -- ie. prime factors of 1...
              else if i
i forall a. Num a => a -> a -> a
* i
i forall a. Ord a => a -> a -> Bool
> i
n
                   then [i
n]
                   else if forall a. Integral a => a -> a -> a
rem i
n i
i forall a. Eq a => a -> a -> Bool
== i
0
                        then i
i forall a. a -> [a] -> [a]
: forall i. Integral i => [i] -> i -> [i]
factor [i]
x (forall a. Integral a => a -> a -> a
quot i
n i
i)
                        else forall i. Integral i => [i] -> i -> [i]
factor [i]
x' i
n

-- | 'factor' of 'primes_list'.
--
-- > map prime_factors [-1,0,1] == [[],[],[]]
-- > map prime_factors [1,4,231,315] == [[],[2,2],[3,7,11],[3,3,5,7]]
-- > map Primes.primeFactors [1,4,231,315] == [[],[2,2],[3,7,11],[3,3,5,7]]
prime_factors :: Integral i => i -> [i]
prime_factors :: forall i. Integral i => i -> [i]
prime_factors = forall i. Integral i => [i] -> i -> [i]
factor forall i. Integral i => [i]
primes_list

-- | 'maximum' of 'prime_factors'
--
-- > map prime_limit [243,125] == [3,5]
-- > map prime_limit [0,1] == [1,1]
prime_limit :: Integral i => i -> i
prime_limit :: forall i. Integral i => i -> i
prime_limit i
x = if i
x forall a. Ord a => a -> a -> Bool
< i
2 then i
1 else forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum (forall i. Integral i => i -> [i]
prime_factors i
x)

-- | Collect number of occurences of each element of a sorted list.
--
-- > multiplicities [1,1,1,2,2,3] == [(1,3),(2,2),(3,1)]
multiplicities :: Eq t => [t] -> [(t,Int)]
multiplicities :: forall t. Eq t => [t] -> [(t, Int)]
multiplicities = forall i a.
Integral i =>
(a -> a -> Bool) -> Maybe (a -> a -> Ordering) -> [a] -> [(a, i)]
List.generic_histogram_by forall a. Eq a => a -> a -> Bool
(==) forall a. Maybe a
Nothing

-- | Pretty printer for histogram (multiplicites).
--
-- > multiplicities_pp [(3,2),(5,1),(7,1)] == "3×2 5×1 7×1"
multiplicities_pp :: Show t => [(t,Int)] -> String
multiplicities_pp :: forall t. Show t => [(t, Int)] -> [Char]
multiplicities_pp =
  let f :: (a, a) -> [Char]
f (a
x,a
y) = forall a. Show a => a -> [Char]
show a
x forall a. [a] -> [a] -> [a]
++ [Char]
"×" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> [Char]
show a
y
  in [[Char]] -> [Char]
unwords forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map forall {a} {a}. (Show a, Show a) => (a, a) -> [Char]
f

-- | 'multiplicities' of 'Primes.primeFactors'.
--
-- > prime_factors_m 1 == []
-- > prime_factors_m 315 == [(3,2),(5,1),(7,1)]
prime_factors_m :: Integral i => i -> [(i,Int)]
prime_factors_m :: forall i. Integral i => i -> [(i, Int)]
prime_factors_m = forall t. Eq t => [t] -> [(t, Int)]
multiplicities forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i. Integral i => i -> [i]
Primes.primeFactors

-- | 'multiplicities_pp' of 'prime_factors_m'.
prime_factors_m_pp :: (Show i,Integral i) => i -> String
prime_factors_m_pp :: forall i. (Show i, Integral i) => i -> [Char]
prime_factors_m_pp = forall t. Show t => [(t, Int)] -> [Char]
multiplicities_pp forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i. Integral i => i -> [(i, Int)]
prime_factors_m

-- | Prime factors of /n/ and /d/.
rat_prime_factors :: Integral i => (i,i) -> ([i],[i])
rat_prime_factors :: forall i. Integral i => (i, i) -> ([i], [i])
rat_prime_factors = forall t u. (t -> u) -> (t, t) -> (u, u)
Function.bimap1 forall i. Integral i => i -> [i]
Primes.primeFactors

-- | 'Ratio' variant of 'rat_prime_factors'
rational_prime_factors :: Integral i => Ratio i -> ([i],[i])
rational_prime_factors :: forall i. Integral i => Ratio i -> ([i], [i])
rational_prime_factors = forall i. Integral i => (i, i) -> ([i], [i])
rat_prime_factors forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. Integral t => Ratio t -> (t, t)
Math.rational_nd

{- | Variant that writes factors of numerator as positive and factors for denominator as negative.
     Sorted by absolute value.

> rat_prime_factors_sgn (3 * 5 * 7 * 11,1) == [3,5,7,11]
> rat_prime_factors_sgn (3 * 5,7 * 11) == [3,5,-7,-11]
> rat_prime_factors_sgn (3 * 7,5) == [3,-5,7]
-}
rat_prime_factors_sgn :: Integral i => (i,i) -> [i]
rat_prime_factors_sgn :: forall i. Integral i => (i, i) -> [i]
rat_prime_factors_sgn (i, i)
r = let ([i]
n,[i]
d) = forall i. Integral i => (i, i) -> ([i], [i])
rat_prime_factors (i, i)
r in forall b a. Ord b => (a -> b) -> [a] -> [a]
sortOn forall a. Num a => a -> a
abs ([i]
n forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
map forall a. Num a => a -> a
negate [i]
d)

-- | Rational variant.
--
-- > rational_prime_factors_sgn (2 * 2 * 2 * 1/3 * 1/3 * 1/3 * 1/3 * 5) == [2,2,2,-3,-3,-3,-3,5]
rational_prime_factors_sgn :: Integral i => Ratio i -> [i]
rational_prime_factors_sgn :: forall i. Integral i => Ratio i -> [i]
rational_prime_factors_sgn = forall i. Integral i => (i, i) -> [i]
rat_prime_factors_sgn forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. Integral t => Ratio t -> (t, t)
Math.rational_nd

-- | The largest prime factor of n/d.
rat_prime_limit :: Integral i => (i,i) -> i
rat_prime_limit :: forall i. Integral i => (i, i) -> i
rat_prime_limit = forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a. Ord a => a -> a -> a
max forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t u. (t -> u) -> (t, t) -> (u, u)
Function.bimap1 forall i. Integral i => i -> i
prime_limit

-- | The largest prime factor of /n/.
--
-- > rational_prime_limit (243/125) == 5
rational_prime_limit :: Integral i => Ratio i -> i
rational_prime_limit :: forall i. Integral i => Ratio i -> i
rational_prime_limit = forall i. Integral i => (i, i) -> i
rat_prime_limit forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. Integral t => Ratio t -> (t, t)
Math.rational_nd

-- | Merge function for 'rat_prime_factors_m'
rat_pf_merge :: Ord t => [(t,Int)] -> [(t,Int)] -> [(t,Int)]
rat_pf_merge :: forall t. Ord t => [(t, Int)] -> [(t, Int)] -> [(t, Int)]
rat_pf_merge [(t, Int)]
p [(t, Int)]
q =
  case ([(t, Int)]
p,[(t, Int)]
q) of
    ([(t, Int)]
_,[]) -> [(t, Int)]
p
    ([],[(t, Int)]
_) -> forall a b. (a -> b) -> [a] -> [b]
map (\(t
i,Int
j) -> (t
i,-Int
j)) [(t, Int)]
q
    ((t
a,Int
b):[(t, Int)]
p',(t
c,Int
d):[(t, Int)]
q') ->
      if t
a forall a. Ord a => a -> a -> Bool
< t
c
      then (t
a,Int
b) forall a. a -> [a] -> [a]
: forall t. Ord t => [(t, Int)] -> [(t, Int)] -> [(t, Int)]
rat_pf_merge [(t, Int)]
p' [(t, Int)]
q
      else if t
a forall a. Ord a => a -> a -> Bool
> t
c
           then (t
c,-Int
d) forall a. a -> [a] -> [a]
: forall t. Ord t => [(t, Int)] -> [(t, Int)] -> [(t, Int)]
rat_pf_merge [(t, Int)]
p [(t, Int)]
q'
           else if Int
b forall a. Eq a => a -> a -> Bool
/= Int
d
                then (t
a,Int
bforall a. Num a => a -> a -> a
-Int
d) forall a. a -> [a] -> [a]
: forall t. Ord t => [(t, Int)] -> [(t, Int)] -> [(t, Int)]
rat_pf_merge [(t, Int)]
p' [(t, Int)]
q'
                else forall t. Ord t => [(t, Int)] -> [(t, Int)] -> [(t, Int)]
rat_pf_merge [(t, Int)]
p' [(t, Int)]
q'

{- | Collect the prime factors in a rational number given as a
numerator/ denominator pair (n,m). Prime factors are listed in
ascending order with their positive or negative multiplicities,
depending on whether the prime factor occurs in the numerator or the
denominator (after cancelling out common factors).

> rat_prime_factors_m (1,1) == []
> rat_prime_factors_m (16,15) == [(2,4),(3,-1),(5,-1)]
> rat_prime_factors_m (10,9) == [(2,1),(3,-2),(5,1)]
> rat_prime_factors_m (81,64) == [(2,-6),(3,4)]
> rat_prime_factors_m (27,16) == [(2,-4),(3,3)]
> rat_prime_factors_m (12,7) == [(2,2),(3,1),(7,-1)]
> rat_prime_factors_m (5,31) == [(5,1),(31,-1)]
-}
rat_prime_factors_m :: Integral i => (i,i) -> [(i,Int)]
rat_prime_factors_m :: forall i. Integral i => (i, i) -> [(i, Int)]
rat_prime_factors_m (i
n,i
d) = forall t. Ord t => [(t, Int)] -> [(t, Int)] -> [(t, Int)]
rat_pf_merge (forall i. Integral i => i -> [(i, Int)]
prime_factors_m i
n) (forall i. Integral i => i -> [(i, Int)]
prime_factors_m i
d)

-- | 'Ratio' variant of 'rat_prime_factors_m'
rational_prime_factors_m :: Integral i => Ratio i -> [(i,Int)]
rational_prime_factors_m :: forall i. Integral i => Ratio i -> [(i, Int)]
rational_prime_factors_m = forall i. Integral i => (i, i) -> [(i, Int)]
rat_prime_factors_m forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. Integral t => Ratio t -> (t, t)
Math.rational_nd

-- | Variant of 'rat_prime_factors_m' giving results in a list.
--
-- > rat_prime_factors_l (1,1) == []
-- > rat_prime_factors_l (2^5,9) == [5,-2]
-- > rat_prime_factors_l (2*2*3,7) == [2,1,0,-1]
-- > rat_prime_factors_l (3*3,11*13) == [0,2,0,0,-1,-1]
rat_prime_factors_l :: Integral i => (i,i) -> [Int]
rat_prime_factors_l :: forall i. Integral i => (i, i) -> [Int]
rat_prime_factors_l (i, i)
x =
  case forall i. Integral i => (i, i) -> [(i, Int)]
rat_prime_factors_m (i, i)
x of
    [] -> []
    [(i, Int)]
r -> let lm :: i
lm = forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum (forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> a
fst [(i, Int)]
r)
         in forall a b. (a -> b) -> [a] -> [b]
map (\i
i -> forall a. a -> Maybe a -> a
fromMaybe Int
0 (forall a b. Eq a => a -> [(a, b)] -> Maybe b
lookup i
i [(i, Int)]
r)) (forall a. (a -> Bool) -> [a] -> [a]
List.take_until (forall a. Eq a => a -> a -> Bool
== i
lm) forall i. Integral i => [i]
primes_list)

-- | 'Ratio' variant of 'rat_prime_factors_l'
--
-- > map rational_prime_factors_l [1/31,256/243] == [[0,0,0,0,0,0,0,0,0,0,-1],[8,-5]]
rational_prime_factors_l :: Integral i => Ratio i -> [Int]
rational_prime_factors_l :: forall i. Integral i => Ratio i -> [Int]
rational_prime_factors_l = forall i. Integral i => (i, i) -> [Int]
rat_prime_factors_l forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. Integral t => Ratio t -> (t, t)
Math.rational_nd

-- | Variant of 'rational_prime_factors_l' padding table to /k/ places.
--   It is an error for /k/ to indicate a prime less than the limit of /x/.
--
-- > map (rat_prime_factors_t 6) [(5,13),(12,7)] == [[0,0,1,0,0,-1],[2,1,0,-1,0,0]]
-- > rat_prime_factors_t 3 (9,7) == undefined
rat_prime_factors_t :: (Integral i,Show i) => Int -> (i,i) -> [Int]
rat_prime_factors_t :: forall i. (Integral i, Show i) => Int -> (i, i) -> [Int]
rat_prime_factors_t Int
k = forall t. t -> Int -> [t] -> [t]
List.pad_right_err Int
0 Int
k forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i. Integral i => (i, i) -> [Int]
rat_prime_factors_l

-- | 'Ratio' variant of 'rat_prime_factors_t'
rational_prime_factors_t :: (Integral i,Show i) => Int -> Ratio i -> [Int]
rational_prime_factors_t :: forall i. (Integral i, Show i) => Int -> Ratio i -> [Int]
rational_prime_factors_t Int
n = forall i. (Integral i, Show i) => Int -> (i, i) -> [Int]
rat_prime_factors_t Int
n forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. Integral t => Ratio t -> (t, t)
Math.rational_nd

-- | Condense factors list to include only indicated places.
--   It is an error if a deleted factor has a non-zero entry in the table.
--
-- > rat_prime_factors_l (12,7) == [2,1,0,-1]
-- > rat_prime_factors_c [2,3,5,7] (12,7) == [2,1,0,-1]
-- > rat_prime_factors_c [2,3,7] (12,7) == [2,1,-1]
rat_prime_factors_c :: (Integral i,Show i) => [i] -> (i,i) -> [Int]
rat_prime_factors_c :: forall i. (Integral i, Show i) => [i] -> (i, i) -> [Int]
rat_prime_factors_c [i]
fc (i, i)
r =
  let t :: [Int]
t = forall i. Integral i => (i, i) -> [Int]
rat_prime_factors_l (i, i)
r
      k :: [Int]
k = forall a b. (a -> b) -> [a] -> [b]
map forall a. Integral a => a -> Int
prime_k_err [i]
fc
      f :: (Int, a) -> Maybe a
f (Int
ix,a
e) = if Int
ix forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` [Int]
k
                 then (if a
e forall a. Ord a => a -> a -> Bool
> a
0 then forall a. HasCallStack => [Char] -> a
error [Char]
"rat_prime_factors_c: non-empty factor" else forall a. Maybe a
Nothing)
                 else forall a. a -> Maybe a
Just a
e
  in forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe forall {a}. (Ord a, Num a) => (Int, a) -> Maybe a
f (forall a b. [a] -> [b] -> [(a, b)]
zip [Int
0..] [Int]
t)

-- | 'Ratio' variant of 'rat_prime_factors_t'
--
-- > map (rational_prime_factors_c [3,5,31]) [3,5,31]
rational_prime_factors_c :: (Integral i,Show i) => [i] -> Ratio i -> [Int]
rational_prime_factors_c :: forall i. (Integral i, Show i) => [i] -> Ratio i -> [Int]
rational_prime_factors_c [i]
fc = forall i. (Integral i, Show i) => [i] -> (i, i) -> [Int]
rat_prime_factors_c [i]
fc forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. Integral t => Ratio t -> (t, t)
Math.rational_nd

-- | Pretty printer for prime factors.  sup=superscript ol=overline
prime_factors_pp :: [Integer] -> String
prime_factors_pp :: [Integer] -> [Char]
prime_factors_pp = forall a. [a] -> [[a]] -> [a]
intercalate [Char
Unicode.middle_dot] forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map forall a. Show a => a -> [Char]
show

{- | Pretty printer for prime factors.  sup=superscript ol=overline

> prime_factors_pp_sup_ol True [2,2,-3,5] == "2²·3̅·5"
> prime_factors_pp_sup_ol False [-2,-2,-2,3,3,5,5,5,5] == "-2³·3²·5⁴"
-}
prime_factors_pp_sup_ol :: Bool -> [Integer] -> String
prime_factors_pp_sup_ol :: Bool -> [Integer] -> [Char]
prime_factors_pp_sup_ol Bool
ol =
  let mk :: a -> [Char]
mk a
x = if a
x forall a. Ord a => a -> a -> Bool
< a
0 Bool -> Bool -> Bool
&& Bool
ol then [Char] -> [Char]
Unicode.overline (forall a. Show a => a -> [Char]
show (- a
x)) else forall a. Show a => a -> [Char]
show a
x
      f :: [a] -> [Char]
f [a]
x = let x0 :: a
x0 = forall a. [a] -> a
head [a]
x
                n :: Int
n = forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
x
            in if Int
n forall a. Eq a => a -> a -> Bool
== Int
1 then forall {a}. (Ord a, Num a, Show a) => a -> [Char]
mk a
x0 else forall {a}. (Ord a, Num a, Show a) => a -> [Char]
mk a
x0 forall a. [a] -> [a] -> [a]
++ Int -> [Char]
Unicode.int_show_superscript Int
n
  in forall a. [a] -> [[a]] -> [a]
intercalate [Char
Unicode.middle_dot] forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map forall {a}. (Ord a, Num a, Show a) => [a] -> [Char]
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Eq a => [a] -> [[a]]
group