Created
October 17, 2018 18:45
-
-
Save tkmharris/4499069be0b4875da9acdd856a5a708b to your computer and use it in GitHub Desktop.
Haskell function for looking at next prime equivalence class bias, as described in https://arxiv.org/abs/1603.03720
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{-- | |
We provide a function 'nextPrimeBias' that when called as | |
nextPrimeBias a b n r | |
returns the probability that, among the first r primes, a prime that is equivalent to a mod n is followed by a prime that is equivalent to b mod n. | |
We see that these probabilities are not evenly distributed among equivalence classes, as described in https://arxiv.org/abs/1603.03720 : | |
nextPrimeBias 7 1 10 100000 = 0.25736558 | |
nextPrimeBias 7 3 10 100000 = 0.27695382 | |
nextPrimeBias 7 7 10 100000 = 0.144993 | |
nextPrimeBias 7 9 10 100000 = 0.3206876 | |
--} | |
-- get primes from optinised prime sieve | |
import Data.Numbers.Primes | |
-- reduce primes mod n | |
primesMod :: Integer -> [Integer] | |
primesMod n = map (\p -> mod p n) primes | |
-- quick 'n' dirty vectorisation | |
(+#) :: (Integer, Integer) -> (Integer, Integer) -> (Integer, Integer) | |
(a,b) +# (c,d) = (a+c,b+d) | |
-- main function | |
nextPrimeBias :: Integer -> Integer -> Integer -> Int -> Float | |
nextPrimeBias a b n r = ratio $ counts a b (take r $ primesModPairs) | |
where | |
primesModPairs = zip (primesMod n) $ tail (primesMod n) | |
counts a b [] = (0,0) | |
counts a b ((x,y):xys) | x /= a = counts a b xys | |
| y == b = (1,1) +# counts a b xys | |
| otherwise = (0,1) +# counts a b xys | |
ratio pair = (fromIntegral $ fst pair) / (fromIntegral $ snd pair) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment