SNAPKITTYWEST's picture
montrepol: exact mathematics in Haskell, with proofs and a certifying solver
5316c4e verified
Raw History Blame Contribute Delete
2.21 kB
-- SPDX-License-Identifier: AGPL-3.0-or-later
-- | Primes, the von Mangoldt function and Chebyshev's psi.
--
-- @psi(x) = sum_{n <= x} Lambda(n)@, where @Lambda(p^k) = log p@ and is zero
-- off prime powers. Exponentiating, @e^psi(x) = lcm(1, ..., x)@, which is an
-- identity between integers and is what the tests check: it pins down
-- 'primePowerBase' without any floating point.
module MP.Primes
( primesUpTo
, isPrimeTrial
, primePowerBase
, vonMangoldt
, chebyshevPsi
, primePowerProduct
, primeCount
) where
import Control.Monad (forM_, when)
import Data.Array.ST (newArray, readArray, runSTUArray, writeArray)
import Data.Array.Unboxed (UArray, assocs)
-- | Sieve of Eratosthenes.
primesUpTo :: Int -> [Int]
primesUpTo n
| n < 2 = []
| otherwise = [i | (i, True) <- assocs sieve]
where
sieve :: UArray Int Bool
sieve = runSTUArray $ do
arr <- newArray (2, n) True
forM_ (takeWhile (\i -> i * i <= n) [2 ..]) $ \i -> do
isP <- readArray arr i
when isP $ forM_ [i * i, i * i + i .. n] $ \j -> writeArray arr j False
pure arr
-- | Trial division: slow, obviously correct, the oracle for the sieve.
isPrimeTrial :: Int -> Bool
isPrimeTrial n = n >= 2 && all (\d -> n `mod` d /= 0) (takeWhile (\d -> d * d <= n) [2 ..])
-- | @Just p@ when @n = p^k@ for a prime @p@ and @k >= 1@.
primePowerBase :: Int -> Maybe Int
primePowerBase n
| n < 2 = Nothing
| otherwise =
let p = smallestFactor n
in if strip p n == 1 then Just p else Nothing
where
smallestFactor m = case [d | d <- takeWhile (\d -> d * d <= m) [2 ..], m `mod` d == 0] of
(d : _) -> d
[] -> m
strip p m = if m `mod` p == 0 then strip p (m `div` p) else m
vonMangoldt :: Int -> Double
vonMangoldt = maybe 0 (log . fromIntegral) . primePowerBase
-- | @psi(x)@ for real @x@: the sum over @n <= floor x@.
chebyshevPsi :: Double -> Double
chebyshevPsi x = sum (map vonMangoldt [2 .. floor x])
-- | @prod_{p^k <= x} p@, exactly; equal to @lcm(1, ..., x)@.
primePowerProduct :: Int -> Integer
primePowerProduct x = product [toInteger p | n <- [2 .. x], Just p <- [primePowerBase n]]
primeCount :: Int -> Int
primeCount = length . primesUpTo