h$J>      !"#$%&'()*+, - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e fghi j k l m n o p q r s t u v w x y z { | } ~                 9(c) 2017-2018 Andrew LelechenkoMIT/Andrew Lelechenko None parithmoi>A list of pairwise coprime numbers with their multiplicities.arithmoiUnwrap.arithmoi2Wrap a non-zero number with its multiplicity into .singleton 210 1!Coprimes {unCoprimes = [(210,1)]}arithmoi/Add a non-zero number with its multiplicity to .insert 360 1 (singleton 210 1)1Coprimes {unCoprimes = [(7,1),(5,2),(3,3),(2,4)]}4insert 2 4 (insert 7 1 (insert 5 2 (singleton 4 3))),Coprimes {unCoprimes = [(7,1),(5,2),(2,10)]}arithmoiThe input list is assumed to be a factorisation of some number into a list of powers of (possibly, composite) non-zero factors. The output list is a factorisation of the same number such that all factors are coprime. Such transformation is crucial to continue factorisation (lazily, in parallel or concurrent fashion) without having to merge multiplicities of primes, which occurs more than in one composite factor.&splitIntoCoprimes [(140, 1), (165, 1)]-Coprimes {unCoprimes = [(28,1),(33,1),(5,2)]}&splitIntoCoprimes [(360, 1), (210, 1)]1Coprimes {unCoprimes = [(7,1),(5,2),(3,3),(2,4)]}(c) 2017 Andrew LelechenkoMIT/Andrew Lelechenko None'( arithmoiThis type represents residues with unknown modulo and rational numbers. One can freely combine them in arithmetic expressions, but each operation will spend time on modulo's recalculation:2 `modulo` 10 + 4 `modulo` 15(1 `modulo` 5)!(2 `modulo` 10) * (4 `modulo` 15)(3 `modulo` 5)import Data.Ratio$2 `modulo` 10 + fromRational (3 % 7)(1 `modulo` 10)$2 `modulo` 10 * fromRational (3 % 7)(8 `modulo` 10)8If performance is crucial, it is recommended to extract Mod m4 for further processing by pattern matching. E. g., case modulo n m of SomeMod k -> process k -- Here k has type Mod m InfMod{} -> error "impossible"arithmoiCreate modular value by representative of residue class and modulo. One can use the result either directly (via functions from  and 5), or deconstruct it by pattern matching. Note that  never returns .arithmoi)Computes the inverse value, if it exists.Nonearithmoi (n1, m1) (n2, m2) returns (n, lcm m1 m2) such that n `mod` m1 == n1 and n `mod` m2 == n2, if exists. Moduli m1 and m2$ are allowed to have common factors.chinese (1, 2) (2, 3) Just (-1, 6)chinese (3, 4) (5, 6) Just (-1, 12)chinese (3, 4) (2, 6)NothingarithmoiSame as , but operates on residues.:set -XDataKindsimport Data.Mod.(1 `modulo` 2) `chineseSomeMod` (2 `modulo` 3)Just (5 `modulo` 6).(3 `modulo` 4) `chineseSomeMod` (5 `modulo` 6)Just (11 `modulo` 12).(3 `modulo` 4) `chineseSomeMod` (2 `modulo` 6)Nothing (c) 2011 Daniel FischerMIT1Daniel Fischer  Safe-InferredarithmoiFollowing property holds: approxPrimeCount n >= primeCount n || n >= approxPrimeCountOverestimateLimitarithmoi n gives an approximation of the number of primes not exceeding n'. The approximation is fairly good for n large enough.arithmoiFollowing property holds: nthPrimeApprox n <= nthPrime n || n >= nthPrimeApproxUnderestimateLimitarithmoi n gives an approximation to the n-th prime. The approximation is fairly good for n large enough.!(c) 2011 Daniel FischerMIT1Daniel Fischer None"(c) 2019 Andrew LelechenkoMIT/Andrew Lelechenko None#"(c) 2018 Alexandre Rodrigues BaldMIT4Alexandre Rodrigues Bald NonebarithmoiInfinite zero-based table of  https://oeis.org/A000041partition numbers.take 10 partition[1,1,2,3,5,7,11,15,22,30]:set -XDataKindsimport Data.Modpartition !! 1000 :: Mod 1000(991 `modulo` 1000)$(c) 2018 Bhavik MehtaMIT%Bhavik Mehta  Safe-InferredarithmoiA representation of  +https://en.wikipedia.org/wiki/Root_of_unityroots of unity: complex numbers z for which there is n such that z^n=1.arithmoi(Every root of unity can be expressed as  e^{2 \pi i q} for some rational q satisfying  0 \leq q < 1, this function extracts it.arithmoiGiven a rational q, produce the root of unity  e^{2 \pi i q}.arithmoiConvert a root of unity into an inexact complex number. Due to floating point inaccuracies, it is recommended to avoid use of this until the end of a calculation. Alternatively, with the  3http://hackage.haskell.org/package/cyclotomic-0.5.1 cyclotomic package, one can use  https://hackage.haskell.org/package/cyclotomic-0.5.1/docs/Data-Complex-Cyclotomic.html#v:polarRatpolarRat 1 . # to convert to a cyclotomic number.arithmoi&This Semigroup is in fact a group, so . can be called with a negative first argument.9(c) 2018 Frederick Schneider, 2018-2019 Andrew LelechenkoMIT7Frederick Schneider None?%^arithmoi-An abstract representation of a smooth basis. arithmoi"Unwrap elements of a smooth basis.!arithmoiBuild a  from a list of numbers, sanitizing it from duplicates, zeros and units.fromList [2, 3]#SmoothBasis {unSmoothBasis = [2,3]}fromList [2, 2]!SmoothBasis {unSmoothBasis = [2]}fromList [1, 3]!SmoothBasis {unSmoothBasis = [3]}"arithmoiA generalization of #, suitable for non-6 domains. The first argument must be an appropriate  (https://en.wikipedia.org/wiki/Ideal_norm Ideal norm function, like % or %.3This routine is more efficient than filtering with $.3import Math.NumberTheory.Quadratic.GaussianIntegers-take 10 (smoothOver' norm (fromList [1+,3]))#[1,1+,2,2+2*,3,4,3+3*,4+4*,6,8]#arithmoi(Generate an infinite ascending list of  +https://en.wikipedia.org/wiki/Smooth_numbersmooth numbers over a given smooth basis.3This routine is more efficient than filtering with $.&take 10 (smoothOver (fromList [2, 5]))[1,2,4,5,8,10,16,20,25,32]$arithmoi2Check that a given number is smooth under a given .isSmooth (fromList [2,3]) 12TrueisSmooth (fromList [2,3]) 15False"arithmoi (https://en.wikipedia.org/wiki/Ideal_norm Ideal norm !"#$ !$#"&(c) 2018 Andrew LelechenkoMIT/Andrew Lelechenko None&arithmoiLet as = sum_i k_ia_i^s and bs = sum_i l_ib_i^s be Dirichlet series, and all a_i and b_i are divisors of n. Return Dirichlet series cs, which contains all terms as * bs = sum_i m_i/c_i^s such that c_i divides n. '(c) 2017 Andrew LelechenkoMIT/Andrew Lelechenko  Safe-Inferred'Q((c) 2011 Daniel FischerMIT1Daniel Fischer None '(/+arithmoiRemove factors of 2 and count them. If  n = 2^k*m with m odd, the result is (k, m) . Precondition: argument not 0 (not checked).arithmoiRemove factors of 2. If  n = 2^k*m with m odd, the result is m . Precondition: argument not 0 (not checked).arithmoiShift argument right until the result is odd. Precondition: argument not 0, not checked.arithmoiLike ., but count the number of places to shift too.arithmoi3It is difficult to convince GHC to unbox output of  and  'splitOff.go', so we fallback to a specialized unboxed version to minimize allocations.arithmoiMerges two ordered lists into an ordered list. Checks for neither its precondition or postcondition.arithmoi Work around -https://ghc.haskell.org/trac/ghc/ticket/14085) Deprecated4(c) 2011 Daniel Fischer, 2017-2018 Andrew LelechenkoMIT/Andrew Lelechenko None.m&arithmoi%Represents three possible values of  +https://en.wikipedia.org/wiki/Jacobi_symbol Jacobi symbol.*arithmoi6Convenience function to convert out of a Jacobi symbol+arithmoi +https://en.wikipedia.org/wiki/Jacobi_symbol Jacobi symbol of two arguments. The lower argument ("denominator") must be odd and positive, this condition is checked.2If arguments have a common factor, the result is (, otherwise it is ' or ).5jacobi 1001 9911 -- arguments have a common factor 11Zerojacobi 1001 9907MinusOne&)('*+*/(c) 2011 Daniel Fischer, 2017 Andrew LelechenkoMIT1Daniel Fischer NoneA,arithmoi isPrime n tests whether n is a prime (negative or positive). It is a combination of trial division and Baillie-PSW test.If  isPrime n returns False then n is definitely composite. There is a theoretical possibility that  isPrime n is True, but in fact n is not prime. However, no such numbers are known and none exist below 2^64. If you have found one, please report it, because it is a major discovery.-arithmoiMiller-Rabin probabilistic primality test. It consists of the trial division test and several rounds of the strong Fermat test with different bases. The choice of trial divisors and bases are implementation details and may change in future silently.First argument stands for the number of rounds of strong Fermat test. If it is 0, only trial division test is performed.If millerRabinV k n returns False then n% is definitely composite. Otherwise n' may appear composite with probability 1/4^k..arithmoi. n b tests whether non-negative n/ is a strong Fermat probable prime for base b.Apart from primes, also some composite numbers have the tested property, but those are rare. Very rare are composite numbers having the property for many bases, so testing a large prime candidate with several bases can identify composite numbers with high probability. An odd number n > 3 is prime if and only if . n b holds for all b with 2 <= b <= (n-1)/2, but of course checking all those bases would be less efficient than trial division, so one normally checks only a relatively small number of bases, depending on the desired degree of certainty. The probability that a randomly chosen base doesn't identify a composite number n is less than 1/4, so five to ten tests give a reasonable level of certainty in general.Please consult  https://miller-rabin.appspot.com9Deterministic variants of the Miller-Rabin primality test! for the best choice of bases./arithmoi/ n b tests whether n, is a Fermat probable prime for the base b, that is, whether b^(n-1)  n == 1. This is a weaker but simpler condition. However, more is lost in strength than is gained in simplicity, so for primality testing, the strong check should be used. The remarks about the choice of bases to test from .( apply with the modification that if a and b are Fermat bases for n, then a*b always is a Fermat base for n too. A Charmichael number is a composite number n3 which is a Fermat probable prime for all bases b coprime to n. By the above, only primes p <= n/2 not dividing n need to be tested to identify Carmichael numbers (however, testing all those primes would be less efficient than determining Carmichaelness from the prime factorisation; but testing an appropriate number of prime bases is reasonable to find out whether it's worth the effort to undertake the prime factorisation).0arithmoiPrimality test after Baillie, Pomerance, Selfridge and Wagstaff. The Baillie-PSW test consists of a strong Fermat probable primality test followed by a (strong) Lucas primality test. This implementation assumes that the number n to test is odd and larger than 3. Even and small numbers have to be handled before. Also, before applying this test, trial division by small primes should be performed to identify many composites cheaply (although the Baillie-PSW test is rather fast, about the same speed as a strong Fermat test for four or five bases usually, it is, for large numbers, much more costly than trial division by small primes, the primes less than 1000, say, so eliminating numbers with small prime factors beforehand is more efficient).The Baillie-PSW test is very reliable, so far no composite numbers passing it are known, and it is known (Gilchrist 2010) that no Baillie-PSW pseudoprimes exist below 2^64. However, a heuristic argument by Pomerance indicates that there are likely infinitely many Baillie-PSW pseudoprimes. On the other hand, according to  :http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html there is reason to believe that there are none with less than several thousand digits, so that for most use cases the test can be considered definitive.arithmoiThe Lucas-Selfridge test, including square-check, but without the Fermat test. For package-internal use only.,-./0+(c) 2017 Andrew LelechenkoMIT/Andrew Lelechenko None '(/L arithmoiPoint on unknown curve.arithmoiWe use the Montgomery form of elliptic curve: b Y = X + a X + X (mod n). See Eq. (10.3.1.1) at p. 260 of  http://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866113-7/S0025-5718-1987-0866113-7.pdfSpeeding the Pollard and Elliptic Curve Methods of Factorization by P. L. Montgomery.Switching to projective space by substitutions Y = y / z, X = x / z, we get b y z = x + a x z + x z (mod n). The point on projective elliptic curve is characterized by three coordinates, but it appears that only x- and z-components matter for computations. By the same reason there is no need to store coefficient b.That said, the chosen curve is represented by a24 = (a + 2) / 4 and modulo n at type level, making points on different curves incompatible.arithmoiExtract x-coordinate.arithmoiExtract z-coordinate.arithmoiExtract (a + 2) / 4, where a is a coefficient in curve's equation.arithmoiExtract modulo of the curve.arithmoi s n- creates a point on an elliptic curve modulo n, uniquely determined by seed s. Some choices of s and n produce ill-parametrized curves, which is reflected by return value .We choose a curve by Suyama's parametrization. See Eq. (3)-(4) at p. 4 of  9http://www.hyperelliptic.org/tanja/SHARCS/talks06/Gaj.pdfImplementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware by K. Gaj, S. Kwon et al.arithmoiIf p0 + p1 = p2, then  p0 p1 p2 equals to p1 + p2-. It is also required that z-coordinates of p0, p1 and p2 are coprime with modulo of elliptic curve; and x-coordinate of p0 is non-zero. If preconditions do not hold, return value is undefined.*Remarkably such addition does not require  a24 constraint.,Computations follow Algorithm 3 at p. 4 of  9http://www.hyperelliptic.org/tanja/SHARCS/talks06/Gaj.pdfImplementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware by K. Gaj, S. Kwon et al.arithmoiMultiply by 2.,Computations follow Algorithm 3 at p. 4 of  9http://www.hyperelliptic.org/tanja/SHARCS/talks06/Gaj.pdfImplementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware by K. Gaj, S. Kwon et al.arithmoi1Multiply by given number, using binary algorithm.arithmoiFor debugging.arithmoiIn projective space s are equal, if they are both at infinity or if respective ratios  /  are equal. ,(c) 2017 Andrew LelechenkoMIT/Andrew Lelechenko None8?Sa1arithmoiWrapper for prime elements of a'. It is supposed to be constructed by  - /  .. and eliminated by 2.One can leverage ? instance to generate lists of primes. Here are some examples.(Generate primes from the given interval::set -XFlexibleContexts [nextPrime 101 .. precPrime 130]=[Prime 101,Prime 103,Prime 107,Prime 109,Prime 113,Prime 127]$Generate an infinite list of primes: [nextPrime 101 ..] [Prime 101,Prime 103,Prime 107,Prime 109,Prime 113,Prime 127...9Generate primes from the given interval of form p = 6k+5:/[nextPrime 101, nextPrime 107 .. precPrime 150]=[Prime 101,Prime 107,Prime 113,Prime 131,Prime 137,Prime 149]Get next prime:succ (nextPrime 101) Prime 103Get previous prime:pred (nextPrime 101)Prime 97+Count primes less than a given number (cf. /):fromEnum (precPrime 100)25Get 25-th prime number (cf. 0):toEnum 25 :: Prime IntPrime 972arithmoiUnwrap prime element.3arithmoiConvert between primes of different types, similar in spirit to .&A simpler version of this function is: toPrimeIntegral :: (Integral a, Integral b) => a -> Maybe b toPrimeIntegral (Prime a) | toInteger a == b = Just (Prime (fromInteger b)) | otherwise = Nothing where b = toInteger a The point of 3 is to avoid redundant conversions and conditions, when it is safe to do so, determining type sizes statically with . For example, 3 from 1  to 1  boils down to  . .1231(c) 2011 Daniel FischerMIT1Daniel Fischer None?[arithmoi!Compact store of primality flags.arithmoiSieve primes up to (and including) a bound (or 7, if bound is smaller). For small enough bounds, this is more efficient than using the segmented sieve.Since arrays are <-indexed, overflow occurs when the sieve size comes near  :: -, that corresponds to an upper bound near 15/8*. On 32-bit systems, that is often within memory limits, so don't give bounds larger than 8*10^9 there.arithmoi4Generate a list of primes for consumption from a .4arithmoiAscending list of primes.take 10 primes[Prime 2,Prime 3,Prime 5,Prime 7,Prime 11,Prime 13,Prime 17,Prime 19,Prime 23,Prime 29]4 is a polymorphic list, so the results of computations are not retained in memory. Make it monomorphic to take advantages of memoization. Compareprimes !! 1000000 :: Prime Int -- (5.32 secs, 6,945,267,496 bytes)Prime 15485867primes !! 1000000 :: Prime Int -- (5.19 secs, 6,945,267,496 bytes)Prime 15485867against#let primes' = primes :: [Prime Int]primes' !! 1000000 :: Prime Int -- (5.29 secs, 6,945,269,856 bytes)Prime 15485867=primes' !! 1000000 :: Prime Int -- (0.02 secs, 336,232 bytes)Prime 15485867arithmoi(List of primes in the form of a list of s, more compact than 4, thus it may be better to use  >>=  than keeping the list of primes alive during the entire run.arithmoiSieve up to bound in one go.arithmoi n creates the list of s starting roughly at n. Due to the organisation of the sieve, the list may contain a few primes less than n%. This form uses less memory than [], hence it may be preferable to use this if it is to be reused. 42(c) 2011 Daniel FischerMIT1Daniel Fischer None^`arithmoi Factorise an  using a given list of numbers considered prime. If the list is not a list of primes containing all relevant primes, the result could be surprising.arithmoi bound n produces a factorisation of n using the primes <= bound. If n has prime divisors > bound, the last entry in the list is the product of all these. If  n <= bound^24, this is a full factorisation, but very slow if n has large prime divisors.5arithmoi5 bound n tests whether n is coprime to all primes <= bound. If  n <= bound^2., this is a full prime test, but very slow if n has no small prime divisors.5 (c) 2020 Andrew LelechenkoMIT/Andrew Lelechenko None 3i(6arithmoi A set of 1 integers.7arithmoiConvert to a set of integers.8arithmoiBuild a singleton set.9arithmoi"Build a set from a list of primes.:arithmoiBuild a set from an ascending list of primes (the precondition is not checked).;arithmoiBuild a set from an ascending list of distinct primes (the precondition is not checked).<arithmoiInsert a prime into the set.=arithmoiDelete an integer from the set.>arithmoi5Check whether the given prime is a member of the set.?arithmoi9Check whether the given prime is not a member of the set.@arithmoiFind a prime in the set, equal to the given integer, if any exists.AarithmoiFind the largest prime in the set, smaller than the given integer, if any exists.BarithmoiFind the smallest prime in the set, greater than the given integer, if any exists.CarithmoiFind the largest prime in the set, smaller or equal to the given integer, if any exists.DarithmoiFind the smallest prime in the set, greater or equal to the given integer, if any exists.EarithmoiCheck whether the set is empty.FarithmoiCardinality of the set.Garithmoi?Check whether the first argument is a subset of the second one.HarithmoiCheck whether the first argument is a proper subset of the second one.Iarithmoi$Check whether two sets are disjoint.Jarithmoi9Difference between a set of primes and a set of integers.Karithmoi An alias to J.Larithmoi+Symmetric difference of two sets of primes.Marithmoi6Intersection of a set of primes and a set of integers.Narithmoi%Filter primes satisfying a predicate.Oarithmoi*Partition primes according to a predicate.ParithmoiSplit into primes strictly less and strictly greater than the first argument.Qarithmoi Simultaneous P and >.Rarithmoi Simultaneous P and @.SarithmoiDecompose a set into pieces based on the structure of the underlying tree.Tarithmoi6Fold a set using the given right-associative operator.Uarithmoi5Fold a set using the given left-associative operator.VarithmoiA strict version of T.WarithmoiA strict version of U.Xarithmoi%Delete the smallest prime in the set.Yarithmoi$Delete the largest prime in the set.Zarithmoi?Split a set into the smallest prime and the rest, if non-empty.[arithmoi>Split a set into the largest prime and the rest, if non-empty.\arithmoi.Convert the set to a list of ascending primes.]arithmoi/Convert the set to a list of descending primes.(6789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\](6789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]K9 3(c) 2011 Daniel FischerMIT1Daniel Fischer None /oparithmoi n% produces the prime factorisation of n.  0) is an error and the factorisation of 1 is empty. Uses a < produced in an arbitrary manner from the bit-pattern of n.Warning: there are no guarantees of any particular order of prime factors, do not expect them to be ascending.arithmoi n b1 b2 s tries to find a factor of n5 using the curve and point determined by the seed s ( 6 <= s < n-1), multiplying the point by the least common multiple of all numbers <= b1 and all primes between b1 and b2. The idea is that there's a good chance that the order of the point in the curve over one prime factor divides the multiplier, but the order over another factor doesn't, if b1 and b2 are appropriately chosen. If they are too small, none of the orders will probably divide the multiplier, if they are too large, all probably will, so they should be chosen to fit the expected size of the smallest factor.It is assumed that n has no small prime factors.,The result is maybe a nontrivial divisor of n.arithmoi n finds all prime divisors of n > 1 up to 2^16 by trial division and returns the list of these together with their multiplicities, and a possible remaining factor which may be composite.4(c) 2011 Daniel FischerMIT1Daniel Fischer None?sfarithmoiMaximal allowed argument of g. Currently 8e18.garithmoig n == (n)2 is the number of (positive) primes not exceeding n.For efficiency, the calculations are done on 64-bit signed integers, therefore n must not exceed f. Requires O(n^0.5)' space, the time complexity is roughly O(n^0.7). For small bounds, g n( simply counts the primes not exceeding n, for bounds from 30000 on, Meissel's algorithm is used in the improved form due to D.H. Lehmer, cf.  http://en.wikipedia.org/wiki/Prime_counting_function#Algorithms_for_evaluating_.CF.80.28x.29.harithmoih n calculates the n%-th prime. Numbering of primes is 1 -based, so h 1 == 2. Requires O((n*log n)^0.5)' space, the time complexity is roughly O((n*log n)^0.7,. The argument must be strictly positive.fgh(c) 2011 Daniel FischerMIT1Daniel Fischer Nonet fghgfh (c) 2016-2018 Andrew.LelechenkoMIT/Andrew Lelechenko None>ziarithmoi)A class for unique factorisation domains.jarithmoiFactorise a number into a product of prime powers. Factorisation of 0 is an undefined behaviour. Otherwise following invariants hold: abs n == abs (product (map (\(p, k) -> unPrime p ^ k) (factorise n))) all ((> 0) . snd) (factorise n)factorise (1 :: Integer)[]factorise (-1 :: Integer)[]factorise (6 :: Integer)[(Prime 2,1),(Prime 3,1)]factorise (-108 :: Integer)[(Prime 2,2),(Prime 3,3)]$This function is a replacement for 566. If you were looking for the latter, please import &Math.NumberTheory.Primes.Factorisation instead of this module.Warning: there are no guarantees of any particular order of prime factors, do not expect them to be ascending. E. g.,factorise 10251562501#[(Prime 101701,1),(Prime 100801,1)]karithmoiCheck whether an argument is prime. If it is then return an associated prime.isPrime (3 :: Integer)Just (Prime 3)isPrime (4 :: Integer)NothingisPrime (-5 :: Integer)Just (Prime 5)$This function is a replacement for  76. If you were looking for the latter, please import  Math.NumberTheory.Primes.Testing instead of this module.larithmoi(Restore a number from its factorisation.marithmoi-Smallest prime, greater or equal to argument. nextPrime (-100) == 2 nextPrime 1000 == 1009 nextPrime 1009 == 1009narithmoiLargest prime, less or equal to argument. Undefined, when argument < 2. 'precPrime 100 == 97 precPrime 97 == 97 1234ijklmn 123mnijkl4 (c) 2011 Daniel FischerMIT1Daniel Fischer Nonexyarithmoi(Infinite zero-based table of factorials.take 5 factorial [1,1,2,6,24] The time-and-space behaviour of y is similar to described in -Math.NumberTheory.Recurrences.Bilinear#memory.zarithmoiPrime factors of a factorial. 0factorialFactors n == factorise (factorial !! n)factorialFactors 101[(Prime 2,8),(Prime 3,4),(Prime 5,2),(Prime 7,1)]{arithmoi{ k calculates the k-th Fibonacci number in O( log (abs k)) steps. The index may be negative. This is efficient for calculating single Fibonacci numbers (with large index), but for computing many Fibonacci numbers in close proximity, it is better to use the simple addition formula starting from an appropriate pair of successive Fibonacci numbers.|arithmoi| k returns the pair (F(k), F(k+1)) of the k-th Fibonacci number and its successor, thus it can be used to calculate the Fibonacci numbers from some index on without needing to compute the previous. The pair is efficiently calculated in O( log (abs k)#) steps. The index may be negative.}arithmoi} k computes the k%-th Lucas number. Very similar to {.~arithmoi~ k computes the pair (L(k), L(k+1)) of the k7-th Lucas number and its successor. Very similar to |.arithmoi p q k calculates the quadruple (U(k), U(k+1), V(k), V(k+1)) where U(i)- is the Lucas sequence of the first kind and V(i)= the Lucas sequence of the second kind for the parameters p and q, where  p^2-4q /= 04. Both sequences satisfy the recurrence relation A(j+2) = p*A(j+1) - q*A(j), the starting values are U(0) = 0, U(1) = 1 and V(0) = 2, V(1) = p. The Fibonacci numbers form the Lucas sequence of the first kind for the parameters  p = 1, q = -1 and the Lucas numbers form the Lucas sequence of the second kind for these parameters. Here, the index must be non-negative, since the terms of the sequence for negative indices are in general not integers.yz{|}~yz{|}~ (c) 2016 Andrew LelechenkoMIT/Andrew Lelechenko NonearithmoiInfinite zero-based table of binomial coefficients (also known as Pascal triangle). (binomial !! n !! k == n! / k! / (n - k)! Note that * !! n !! k is asymptotically slower than  n !! k, but imposes only  constraint.take 6 binomial :: [[Int]]9[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]arithmoi'Pascal triangle, rotated by 45 degrees. binomialRotated !! n !! k == (n + k)! / n! / k! == binomial !! (n + k) !! k Note that * !! n !! k is asymptotically slower than  n !! k, but imposes only  constraint.0take 6 (map (take 6) binomialRotated) :: [[Int]][[1,1,1,1,1,1],[1,2,3,4,5,6],[1,3,6,10,15,21],[1,4,10,20,35,56],[1,5,15,35,70,126],[1,6,21,56,126,252]]arithmoiThe n-th (zero-based) line of  (and the n-th diagonal of ).binomialLine 5[1,5,10,10,5,1]arithmoi"The n-th (zero-based) diagonal of  (and the n-th line of ).take 6 (binomialDiagonal 5)[1,6,21,56,126,252]arithmoi(Prime factors of a binomial coefficient. 5binomialFactors n k == factorise (binomial !! n !! k)binomialFactors 10 41[(Prime 2,1),(Prime 3,1),(Prime 5,1),(Prime 7,1)]arithmoiInfinite zero-based table of  https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind"Stirling numbers of the first kind.take 5 (map (take 5) stirling1)*[[1],[0,1],[0,1,1],[0,2,3,1],[0,6,11,6,1]] Complexity: stirling1 !! n !! k is O(n ln n) bits long, its computation takes O(k n^2 ln n) time and forces thunks stirling1 !! i !! j for  0 <= i <= n and max(0, k - n + i) <= j <= k.One could also consider 89 from  +http://hackage.haskell.org/package/combinatcombinat' package to compute stand-alone values.arithmoiInfinite zero-based table of  https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Stirling numbers of the second kind.take 5 (map (take 5) stirling2))[[1],[0,1],[0,1,1],[0,1,3,1],[0,1,7,6,1]] Complexity: stirling2 !! n !! k is O(n ln n) bits long, its computation takes O(k n^2 ln n) time and forces thunks stirling2 !! i !! j for  0 <= i <= n and max(0, k - n + i) <= j <= k.One could also consider 8: from  +http://hackage.haskell.org/package/combinatcombinat' package to compute stand-alone values.arithmoiInfinite one-based table of  (https://en.wikipedia.org/wiki/Lah_number Lah numbers.  lah !! n !! k equals to lah(n + 1, k + 1).take 5 (map (take 5) lah)3[[1],[2,1],[6,6,1],[24,36,12,1],[120,240,120,20,1]] Complexity:  lah !! n !! k is O(n ln n) bits long, its computation takes O(k n ln n) time and forces thunks  lah !! n !! i for  0 <= i <= k.arithmoiInfinite zero-based table of  -https://en.wikipedia.org/wiki/Eulerian_number"Eulerian numbers of the first kind.take 5 (map (take 5) eulerian1)"[[],[1],[1,1],[1,4,1],[1,11,11,1]] Complexity: eulerian1 !! n !! k is O(n ln n) bits long, its computation takes O(k n^2 ln n) time and forces thunks eulerian1 !! i !! j for  0 <= i <= n and max(0, k - n + i) <= j <= k.arithmoiInfinite zero-based table of  https://en.wikipedia.org/wiki/Eulerian_number#Eulerian_numbers_of_the_second_kind#Eulerian numbers of the second kind.take 5 (map (take 5) eulerian2)#[[],[1],[1,2],[1,8,6],[1,22,58,24]] Complexity: eulerian2 !! n !! k is O(n ln n) bits long, its computation takes O(k n^2 ln n) time and forces thunks eulerian2 !! i !! j for  0 <= i <= n and max(0, k - n + i) <= j <= k.arithmoi Infinite zero-based sequence of  .https://en.wikipedia.org/wiki/Bernoulli_numberBernoulli numbers, computed via  https://en.wikipedia.org/wiki/Bernoulli_number#Connection_with_Stirling_numbers_of_the_second_kind connection with .take 5 bernoulli&[1 % 1,(-1) % 2,1 % 6,0 % 1,(-1) % 30] Complexity: bernoulli !! n is O(n ln n) bits long, its computation takes O(n^3 ln n) time and forces thunks stirling2 !! i !! j for  0 <= i <= n and  0 <= j <= i.One could also consider 8; from  +http://hackage.haskell.org/package/combinatcombinat' package to compute stand-alone values.arithmoi 3https://en.wikipedia.org/wiki/Faulhaber%27s_formulaFaulhaber's formula.sum (map (^ 10) [0..100])9599241424342419242508sum $ zipWith (*) (faulhaberPoly 10) (iterate (* 100) 1)959924142434241924250 % 1arithmoiThe same sequence as euler', but with type [a] instead of  [Ratio a] as the denominators in euler' are always 1.take 10 euler :: [Integer][1,0,-1,0,5,0,-61,0,1385,0]arithmoi Infinite zero-based list of the n)-th order Euler polynomials evaluated at 1'. The algorithm used was derived from  9http://www.emis.ams.org/journals/JIS/VOL4/CHEN/AlgBE2.pdf2Algorithms for Bernoulli numbers and Euler numbers by Kwang-Wu Chen, third formula of the Corollary in page 7. Element-by-element division of sequences  https://oeis.org/A198631A1986631 and  https://oeis.org/A006519A006519 in OEIS."take 10 eulerPolyAt1 :: [Rational][1 % 1,1 % 2,0 % 1,(-1) % 4,0 % 1,1 % 2,0 % 1,(-17) % 8,0 % 1,31 % 2]"(c) 2018 Alexandre Rodrigues BaldMIT4Alexandre Rodrigues Bald Noneyz{|}~<(c) 2011 Daniel FischerMIT1Daniel Fischer None&arithmoi n tests primality of n, first trial division by small primes is performed, then a Baillie PSW test and finally a prime certificate is constructed and verified, provided no step before found n to be composite. Constructing prime certificates can take a very" long time, so use this with care. (c) 2011 Daniel FischerMIT1Daniel Fischer None,-./05,0-./5(c) 2017 Andrew LelechenkoMIT/Andrew Lelechenko NonearithmoiA container for a number and its pairwise coprime (but not necessarily prime) factorisation. It is designed to preserve information about factors under multiplication. One can use this representation to speed up prime factorisation and computation of arithmetic functions.For instance, let p and q be big primes:2let p = 1000000000000000000000000000057 :: Integer2let q = 2000000000000000000000000000071 :: IntegerIt would be difficult to compute the totient function of their product as is, because once we multiplied them the information of factors is lost and = (p * q) would take ages. Things become different if we simply change types of p and q to prefactored ones:>let p = 1000000000000000000000000000057 :: Prefactored Integer>let q = 2000000000000000000000000000071 :: Prefactored IntegerNow the =% function can be computed instantly:,import Math.NumberTheory.ArithmeticFunctionsprefValue $ totient (p^2 * q^3)8000000000000000000000000001752000000000000000000000000151322000000000000000000000006445392000000000000000000000135513014000000000000000000001126361040)prefValue $ totient $ totient (p^2 * q^3)2133305798262843681544648472180210822742702690942899511234131900112583590230336435053688694839034890779375223070157301188739881477320529552945446912000Let us look under the hood:,import Math.NumberTheory.ArithmeticFunctions!prefFactors $ totient (p^2 * q^3)Coprimes {unCoprimes = [(1000000000000000000000000000057,1),(41666666666666666666666666669,1),(2000000000000000000000000000071,2),(111111111111111111111111111115,1),(2,4),(3,3)]}+prefFactors $ totient $ totient (p^2 * q^3)Coprimes {unCoprimes = [(39521,1),(227098769,1),(22222222222222222222222222223,1),(2000000000000000000000000000071,1),(361696272343,1),(85331809838489,1),(6046667,1),(199937,1),(5,3),(41666666666666666666666666669,1),(2,22),(3,8)]}Pairwise coprimality of factors is crucial, because it allows us to process them independently, possibly even in parallel or concurrent fashion.*Following invariant is guaranteed to hold: abs (prefValue x) = abs (product (map (uncurry (^)) (prefFactors x)))arithmoiNumber itself.arithmoiList of pairwise coprime (but not necessarily prime) factors, accompanied by their multiplicities.arithmoiCreate  from a given number. fromValue 123Prefactored {prefValue = 123, prefFactors = Coprimes {unCoprimes = [(123,1)]}}arithmoiCreate  from a given list of pairwise coprime (but not necessarily prime) factors with multiplicities.4fromFactors (splitIntoCoprimes [(140, 1), (165, 1)])Prefactored {prefValue = 23100, prefFactors = Coprimes {unCoprimes = [(28,1),(33,1),(5,2)]}}4fromFactors (splitIntoCoprimes [(140, 2), (165, 3)])Prefactored {prefValue = 88045650000, prefFactors = Coprimes {unCoprimes = [(28,2),(33,3),(5,5)]}}>(c) 2016 Andrew LelechenkoMIT/Andrew Lelechenko None'(arithmoiA typical arithmetic function operates on the canonical factorisation of a number into prime's powers and consists of two rules. The first one determines the values of the function on the powers of primes. The second one determines how to combine these values into final result.In the following definition the first argument is the function on prime's powers, the monoid instance determines a rule of combination (typically ?@ or ?A), and the second argument is convenient for unwrapping (typically, ?B or ?C).arithmoi3Convert to a function. The value on 0 is undefined.arithmoi-Convert to a function on prime factorisation.arithmoiFactorisation is expensive, so it is better to avoid doing it twice. Write 'runFunction (f + g) n' instead of 'runFunction f n + runFunction g n'.(c) 2017 Andrew LelechenkoMIT/Andrew Lelechenko NonearithmoipowMod b e m computes (b^e) `mod` m in effective way. An exponent e must be non-negative, a modulo m/ must be positive. Otherwise the behaviour of powMod is undefined. powMod 2 3 53"powMod 3 12345678901234567890 10011 See also D and E.For finite numeric types (, , etc.) modulo m should be such that m^2 does not overflow, otherwise the behaviour is undefined. If you need both to fit into machine word and to handle large moduli, take a look at  and .+powMod 3 101 (2^60-1 :: Integer) -- correct10181051671003793289powMod 3 101 (2^60-1 :: Int) -- incorrect due to overflow1115647832265427613*powModInt 3 101 (2^60-1 :: Int) -- correct1018105167100379328arithmoiSpecialised version of (, able to handle large moduli correctly.powModWord 3 101 (2^60-1)1018105167100379328arithmoiSpecialised version of (, able to handle large moduli correctly.powModInt 3 101 (2^60-1)1018105167100379328(c) 2012 Daniel FischerMIT1Daniel Fischer None?arithmoi totientSum n is, for n > 0 , the sum of otient k | k <- [1 .. n]]7, computed via generalised Mbius inversion. See  :http://mathworld.wolfram.com/TotientSummatoryFunction.html for the formula used for  totientSum.import Data.ProxytotientSum (Proxy :: Proxy Data.Vector.Unboxed.Vector) 100 :: Int3044=totientSum (Proxy :: Proxy Data.Vector.Vector) 100 :: Integer3044arithmoigeneralInversion g n/ evaluates the generalised Mbius inversion of g at the argument n.The generalised Mbius inversion implemented here allows an efficient calculation of isolated values of the function  f : N -> Z if the function g defined by , g n = sum [f (n `quot` k) | k <- [1 .. n]] can be cheaply computed. By the generalised Mbius inversion formula, then 8 f n = sum [moebius k * g (n `quot` k) | k <- [1 .. n]]  which allows the computation in O(n) steps, if the values of the Mbius function are known. A slightly different formula, used here, does not need the values of the Mbius function and allows the computation in O(n^0.75) steps, using O(n^0.5) memory.An example of a pair of such functions where the inversion allows a more efficient computation than the direct approach is  f n = number of reduced proper fractions with denominator <= n g n = number of proper fractions with denominator <= n (a proper fraction is a fraction  0 < n/d < 1). Then f n6 is the cardinality of the Farey sequence of order n (minus 1 or 2 if 0 and/or 1 are included in the Farey sequence), or the sum of the totients of the numbers  2 <= k <= n. f n0 is not easily directly computable, but then g n = n*(n-1)/2 is very easy to compute, and hence the inversion gives an efficient method of computing f n.Since the function arguments are used as array indices, the domain of f is restricted to . The value f n is then computed by generalInversion g n#. Note that when many values of f are needed, there are far more efficient methods, this method is only appropriate to compute isolated values of f.(c) 2019 Andrew LelechenkoMIT/Andrew Lelechenko None&'(./8>TarithmoiThis singleton data type establishes a correspondence between a modulo m on type level and a cyclic group of the same order on term level.arithmoiThis singleton data type establishes a correspondence between a modulo m4 on type level and its factorisation on term level.arithmoi Factors of m.arithmoi.Wrapper to hide an unknown type-level natural.arithmoi,Unidirectional pattern for residues modulo 2p^k for odd prime p.arithmoi+Unidirectional pattern for residues modulo p^k for odd prime p.arithmoi-Unidirectional pattern for residues modulo 4.arithmoi-Unidirectional pattern for residues modulo 2.arithmoi5Create a singleton from a type-level positive modulo m, passed in a constraint.:set -XDataKindssfactors :: SFactors Integer 13&SFactors {unSFactors = [(Prime 13,1)]}arithmoi#Create a singleton from factors of m-. Factors must be distinct, as in output of j.import Math.NumberTheory.PrimessomeSFactors (factorise 98)1SFactors {unSFactors = [(Prime 2,1),(Prime 7,2)]}arithmoi$Convert a singleton to a proof that m is known. Usage example: toModulo :: SFactors Integer m -> Natural toModulo t = case proofFromSFactors t of Sub Dict -> natVal tarithmoi5Create a singleton from a type-level positive modulo m, passed in a constraint.:set -XDataKindsimport Data.Maybe.cyclicGroup :: Maybe (CyclicGroup Integer 169)$Just (CGOddPrimePower' (Prime 13) 2)#:set -XTypeOperators -XNoStarIsTypeimport GHC.TypeNats6sfactorsToCyclicGroup (sfactors :: SFactors Integer 4) Just CG4'sfactorsToCyclicGroup (sfactors :: SFactors Integer (2 * 13 ^ 3))*Just (CGDoubleOddPrimePower' (Prime 13) 3)>sfactorsToCyclicGroup (sfactors :: SFactors Integer (4 * 13))NothingarithmoiCreate a singleton from factors. Factors must be distinct, as in output of j.arithmoi Similar to  . j, but much faster, because it but performes only one primality test instead of full factorisation.arithmoi'Convert a cyclic group to a proof that m is known. Usage example: toModulo :: CyclicGroup Integer m -> Natural toModulo t = case proofFromCyclicGroup t of Sub Dict -> natVal tarithmoiCheck whether a multiplicative group of residues, characterized by its modulo, is cyclic and, if yes, return its form.#:set -XTypeOperators -XNoStarIsTypeimport GHC.TypeNats6sfactorsToCyclicGroup (sfactors :: SFactors Integer 4) Just CG4'sfactorsToCyclicGroup (sfactors :: SFactors Integer (2 * 13 ^ 3))*Just (CGDoubleOddPrimePower' (Prime 13) 3)>sfactorsToCyclicGroup (sfactors :: SFactors Integer (4 * 13))NothingarithmoiInvert .import Data.MaybecyclicGroupToSFactors (fromJust (sfactorsToCyclicGroup (sfactors :: SFactors Integer 4)))%SFactors {unSFactors = [(Prime 2,2)]}(c) 2011 Daniel FischerMIT/Andrew Lelechenko None&ʔarithmoiList all modular square roots.:set -XDataKindssqrtsMod sfactors (1 :: Mod 60)[(1 `modulo` 60),(49 `modulo` 60),(41 `modulo` 60),(29 `modulo` 60),(31 `modulo` 60),(19 `modulo` 60),(11 `modulo` 60),(59 `modulo` 60)]arithmoiList all square roots modulo a number, the factorisation of which is passed as a second argument.&sqrtsModFactorisation 1 (factorise 60)[1,49,41,29,31,19,11,59]arithmoi2List all square roots modulo the power of a prime.import Data.Maybeimport Math.NumberTheory.Primes-sqrtsModPrimePower 7 (fromJust (isPrime 3)) 2[4,5]-sqrtsModPrimePower 9 (fromJust (isPrime 3)) 3[3,12,21,24,6,15]arithmoi&List all square roots by prime modulo.import Data.Maybeimport Math.NumberTheory.Primes&sqrtsModPrime 1 (fromJust (isPrime 5))[1,4]&sqrtsModPrime 0 (fromJust (isPrime 5))[0]&sqrtsModPrime 2 (fromJust (isPrime 5))[] &)('*+ &)('+*'(c) 2016 Chris Fredrickson, Google Inc.MIT1Chris Fredrickson None8΢arithmoiNone8 arithmoiAn Eisenstein integer is a + b, where a and b are both integers.arithmoi1The imaginary unit for Eisenstein integers, where , == (-1/2) + ((sqrt 3)/2) == exp(2*pi*/3)and " is the usual imaginary unit with  == -1.arithmoiList of all Eisenstein units, counterclockwise across all sextants, starting with 1.arithmoiProduce a list of an EisensteinInteger's associates.arithmoiConjugate a Eisenstein integer.arithmoi4The square of the magnitude of a Eisenstein integer.arithmoiFind an Eisenstein integer whose norm is the given prime number in the form 3k + 1.+import Math.NumberTheory.Primes (nextPrime)findPrime (nextPrime 7) Prime 3+2*arithmoi6An infinite list of Eisenstein primes. Uses primes in Z to exhaustively generate all Eisenstein primes in order of ascending norm.Every prime is in the first sextant, so the list contains no associates.Eisenstein primes from the whole complex plane can be generated by applying  to each prime in this list.take 10 primes[Prime 2+,Prime 2,Prime 3+2*,Prime 3+,Prime 4+3*,Prime 4+,Prime 5+3*,Prime 5+2*,Prime 5,Prime 6+5*]arithmoi1See the source code and Haddock comments for the  factorise and isPrime functions in this module (they are not exported) for implementation details.  6(c) 2018 Andrew LelechenkoMIT/Andrew Lelechenko None&׸arithmoi)Find all solutions of ax + b D 0 (mod m).:set -XDataKinds:solveLinear (6 :: Mod 10) 4 -- solving 6x + 4 D 0 (mod 10)![(1 `modulo` 10),(6 `modulo` 10)]arithmoi/Find all solutions of ax + bx + c D 0 (mod m).:set -XDataKindssolveQuadratic sfactors (1 :: Mod 32) 0 (-17) -- solving x - 17 D 0 (mod 32)[(9 `modulo` 32),(25 `modulo` 32),(7 `modulo` 32),(23 `modulo` 32)]arithmoiaarithmoibarithmoi list of xarithmoiaarithmoibarithmoicarithmoi list of xF(c) 2020 Bhavik MehtaMIT%Bhavik Mehta None!(c) 2017 Andrew LelechenkoMIT/Andrew Lelechenko None&arithmoi) m is a type which is only inhabited by  5https://en.wikipedia.org/wiki/Primitive_root_modulo_nprimitive roots of m.arithmoiExtract primitive root value.arithmoiThis type represents elements of the multiplicative group mod m, i.e. those elements which are coprime to m. Use  isMultElement to construct.arithmoiUnwrap a residue.arithmoi4Attempt to construct a multiplicative group element.arithmoiFor elements of the multiplicative group, we can safely perform the inverse without needing to worry about failure.arithmoi,Check whether a given modular residue is a  5https://en.wikipedia.org/wiki/Primitive_root_modulo_nprimitive root.:set -XDataKindsimport Data.Maybe4isPrimitiveRoot (fromJust cyclicGroup) (1 :: Mod 13)Nothing4isPrimitiveRoot (fromJust cyclicGroup) (2 :: Mod 13)Just (PrimitiveRoot {unPrimitiveRoot = MultMod {multElement = (2 `modulo` 13)}})arithmoiComputes the discrete logarithm. Currently uses a combination of the baby-step giant-step method and Pollard's rho algorithm, with Bach reduction.:set -XDataKindsimport Data.Maybe7let cg = fromJust cyclicGroup :: CyclicGroup Integer 13(let rt = fromJust (isPrimitiveRoot cg 2)$let x = fromJust (isMultElement 11)discreteLogarithm cg rt x7(c) 2017 Andrew LelechenkoMIT/Andrew Lelechenko None'(/arithmoi.Linking type and value levels: extract modulo m as a value.arithmoi.Linking type and value levels: extract modulo m as a value.arithmoiThe canonical representative of the residue class, always between 0 and m-1 inclusively.arithmoiThe canonical representative of the residue class, always between 0 and m-1 inclusively.arithmoi Synonym of .  G(c) 2011 Daniel FischerMIT1Daniel Fischer None5 &')(*+(c) 2020 Federico BongiornoMIT2Federico Bongiorno NonearithmoiRepresents the  https://en.wikipedia.org/wiki/Cubic_reciprocity#Cubic_residue_charactercubic residue character It is either 0, ,  or 1.arithmoi Converts a  https://en.wikipedia.org/wiki/Cubic_reciprocity#Cubic_residue_character cubic symbol to an Eisenstein Integer.arithmoi https://en.wikipedia.org/wiki/Cubic_reciprocity#Cubic_residue_character Cubic symbol of two Eisenstein Integers. The first argument is the numerator and the second argument is the denominator. The latter must be coprime to 3. This condition is checked.6If the arguments have a common factor, the result is , otherwise it is either ,  or .#cubicSymbol (45 + 23*) (11 - 30*)0cubicSymbol (31 - ) (1 +10*)arithmoi0The set of cubic symbols form a semigroup. Note  is allowed to take non-positive values. In other words, the set of non-zero cubic symbols is regarded as a group.import Data.Semigroupstimes (-1) Omega stimes 0 Zero1NoneFarithmoiFinds all primitive solutions (x,y) to the diophantine equation | x^2 + d*y^2 = m | when 1 <= d < m and gcd(d,m)=1 | Given m is square free these are all the positive integer solutionsarithmoiFinds all positive integer solutions (x,y) to the | diophantine equation: | x^2 + d*y^2 = m | when 1 <= d < m and gcd(d,m)=1"(c) 2018 Alexandre Rodrigues BaldMIT4Alexandre Rodrigues Bald None?Narithmoi Evaluate the H" function over a block. Value at 0), if zero falls into block, is undefined.This function should **not** be used with a negative lower bound. If it is, the result is undefined. Furthermore, do not: use a block length greater than maxBound :: Int.use a power that is either of 0, 1.None of these preconditions are checked, and if any occurs, the result is undefined, if the function terminates.sieveBlockNFree 2 1 106[True,True,True,False,True,True,True,False,False,True]arithmoi&For a given nonnegative integer power n, generate all n/-free numbers in ascending order, starting at 1.When n is 0 or 1, the resulting list is [1].arithmoi Generate n-free numbers in a block starting at a certain value. The length of the list is determined by the value passed in as the third argument. It will be lesser than or equal to this value.This function should not be used with a negative lower bound. If it is, the result is undefined.The block length cannot exceed maxBound :: Int$, this precondition is not checked.As with nFrees , passing n = 0, 1 results in an empty list.arithmoi Power whose n-freedom will be checked.arithmoiLower index of the block.arithmoiLength of the block.arithmoiVector of flags, where True at index i means the i-th element of the block is n-free.arithmoiPower n to be used to generate n-free numbers.arithmoiGenerated infinite list of n-free numbers.arithmoiPower n to be used to generate n-free numbers.arithmoiStarting number in the block.arithmoi,Maximum length of the block to be generated.arithmoiGenerated list of n-free numbers.(c) 2018 Andrew LelechenkoMIT/Andrew Lelechenko None arithmoi$Represents three possible values of  -https://en.wikipedia.org/wiki/Mbius_functionMbius function.arithmoi1arithmoi0arithmoi1arithmoiConvert to any numeric type.arithmoi5Evaluate the Mbius function over a block. Value of f. at 0, if zero falls into block, is undefined.,Based on the sieving algorithm from p. 3 of  $https://arxiv.org/pdf/1610.08551.pdfComputations of the Mertens function and improved bounds on the Mertens conjecture1 by G. Hurst. It is approximately 5x faster than I.sieveBlockMoebius 1 10[MoebiusP,MoebiusN,MoebiusN,MoebiusZ,MoebiusN,MoebiusP,MoebiusN,MoebiusZ,MoebiusZ,MoebiusP]J(c) 2016 Andrew LelechenkoMIT/Andrew Lelechenko None#arithmoiCreate a multiplicative function from the function on prime's powers. See examples below.arithmoiSee .arithmoi2The set of all (positive) divisors of an argument.arithmoiSee .arithmoiThe unsorted list of all (positive) divisors of an argument, produced in lazy fashion.arithmoiSee .arithmoiSame as :, but with better performance on cost of type restriction.arithmoiSee .arithmoi k + 1)arithmoiSee .arithmoiThe sum of the k1-th powers of (positive) divisors of an argument. sigmaA = multiplicative (\p k -> sum $ map (p ^) [0..k]) sigmaA 0 = tauAarithmoiSee .arithmoi,Calculates the totient of a positive number n, i.e. the number of k with  1 <= k <= n and  n k == 18, in other words, the order of the group of units in B/(n).arithmoiSee .arithmoi3Calculates the k-th Jordan function of an argument. jordanA 1 = totientAarithmoiSee .arithmoiCalculates the  4https://en.wikipedia.org/wiki/Ramanujan_tau_functionRamanujan tau function of a positive number n, using formulas given (http://www.numbertheory.org/php/tau.htmlherearithmoiSee .arithmoi.Calculates the Mbius function of an argument.arithmoiSee .arithmoi1Calculates the Liouville function of an argument.arithmoiSee .arithmoiCalculates the Carmichael function for a positive integer, that is, the (smallest) exponent of the group of units in B/(n).arithmoiCreate an additive function from the function on prime's powers. See examples below.arithmoiSee .arithmoi!Number of distinct prime factors. "smallOmegaA = additive (\_ _ -> 1)arithmoiSee .arithmoi3Number of prime factors, counted with multiplicity.  bigOmegaA = additive (\_ k -> k)arithmoiSee .arithmoi+The exponent of von Mangoldt function. Use log expMangoldtA) to recover von Mangoldt function itself.arithmoiSee .arithmoiCheck if an integer is n-free. An integer x is n-free if in its factorisation into prime factors, no factor has an exponent larger than or equal to n.*(c) 2016 Andrew LelechenkoMIT/Andrew Lelechenko NoneU..(c) 2018 Bhavik MehtaMIT%Bhavik Mehta None &'(/arithmoiSimilar to Maybe, but with different Semigroup and Monoid instances.arithmoi.Wrapper to hide an unknown type-level natural.arithmoi0A Dirichlet character is primitive if cannot be 3 from any character with strictly smaller modulus.arithmoi$Extract the character itself from a .arithmoi3A Dirichlet character is real if it is real-valued.arithmoi$Extract the character itself from a .arithmoiA Dirichlet character mod n is a group homomorphism from (\mathbb{Z}/n\mathbb{Z})^* to  \mathbb{C}^*, represented abstractly by . In particular, they take values at roots of unity and can be evaluated using . A Dirichlet character can be extended to a completely multiplicative function on  \mathbb{Z} by assigning the value 0 for a sharing a common factor with n, using .There are finitely many possible Dirichlet characters for a given modulus, in particular there are \phi(n) characters modulo n, where \phi refers to Euler's  function. This gives rise to  and  instances.arithmoi ( x)arithmoi arithmoi)For elements of the multiplicative group (\mathbb{Z}/n\mathbb{Z})^*6, a Dirichlet character evaluates to a root of unity.arithmoiA character can evaluate to a root of unity or zero: represented by Nothing.arithmoiGive the principal character for this modulus: a principal character mod n is 1 for a coprime to n, and 0 otherwise.arithmoi>We have a (non-canonical) enumeration of dirichlet characters.arithmoi:Give the dirichlet character from its number. Inverse of .arithmoiGive a collection of dirichlet characters from their numbers. This may be more efficient than  for multiple characters, as it prevents some internal recalculations.arithmoiList all characters for the modulus. This is preferred to using [minBound..maxBound].arithmoiTest if a given Dirichlet character is prinicpal for its modulus: a principal character mod n is 1 for a coprime to n, and 0 otherwise.arithmoi5Induce a Dirichlet character to a higher modulus. If d \mid n, then  a \bmod{n} can be reduced to  a \bmod{d}'. Thus, the multiplicative function on \mathbb{Z}/d\mathbb{Z}' induces a multiplicative function on \mathbb{Z}/n\mathbb{Z}.#:set -XTypeApplications -XDataKinds,chi = indexToChar 5 :: DirichletCharacter 459chi2 = induced @135 chi :: Maybe (DirichletCharacter 135)arithmoiThe  +https://en.wikipedia.org/wiki/Jacobi_symbol Jacobi symbol2 gives a real Dirichlet character for odd moduli.arithmoiTest if a given  is real, and if so give a .arithmoiEvaluate a real Dirichlet character, which can only take values -1,0,1.arithmoi;Test if the internal DirichletCharacter structure is valid.arithmoi)Get the order of the Dirichlet Character.arithmoi!Test if a Dirichlet character is  https://en.wikipedia.org/wiki/Dirichlet_character#Primitive_characters_and_conductor primitive.arithmoiThis function also provides access to the new modulus on type level, with a KnownNat instancearithmoi Interpret an  as a number, taking the  case to be 0.arithmoiIn general, evaluating a DirichletCharacter at a point involves solving the discrete logarithm problem, which can be hard: the implementations here are around O(sqrt n). However, evaluating a dirichlet character at every point amounts to solving the discrete logarithm problem at every point also, which can be done together in O(n) time, better than using a complex algorithm at each point separately. Thus, if a large number of evaluations of a dirichlet character are required,  will be better than $, since computations can be shared.arithmoiAttempt to construct a character from its table of values. An inverse to , defined only on its image.arithmoi We define  and + with more efficient implementations than  . (+1) . .arithmoi&This Semigroup is in fact a group, so stimes. can be called with a negative first argument.""(c) 2017 Andrew LelechenkoMIT/Andrew Lelechenko None arithmoi>A record, which specifies a function to evaluate over a block.>For example, here is a configuration for the totient function: SieveBlockConfig { sbcEmpty = 1 , sbcFunctionOnPrimePower = \p a -> (unPrime p - 1) * unPrime p ^ (a - 1) , sbcAppend = (*) }arithmoivalue of a function on 1arithmoi*how to evaluate a function on prime powersarithmoi8how to combine values of a function on coprime argumentsarithmoiCreate a config for a multiplicative function from its definition on prime powers.arithmoiCreate a config for an additive function from its definition on prime powers.arithmoi f x l8 evaluates an arithmetic function for integers between x and x+l-1 and returns a vector of length l. It completely avoids factorisation, so it is asymptotically faster than pointwise evaluation of f. Value of f. at 0, if zero falls into block, is undefined.Beware that for underlying non-commutative monoids the results may potentially differ from pointwise application via .This is a thin wrapper over , read more details there.,import Math.NumberTheory.ArithmeticFunctions%runFunctionOverBlock carmichaelA 1 10[1,1,2,2,4,2,6,2,6,4]arithmoiEvaluate a function over a block in accordance to provided configuration. Value of f. at 0, if zero falls into block, is undefined.Based on Algorithm M of  #https://arxiv.org/pdf/1305.1639.pdfParity of the number of primes in a given interval and algorithms of the sublinear summation by A. V. Lelechenko. See Lemma 2 on p. 5 on its algorithmic complexity. For the majority of use-cases its time complexity is O(x^(1+)).9For example, following code lists smallest prime factors:sieveBlock (SieveBlockConfig maxBound (\p _ -> unPrime p) min) 2 10 :: Data.Vector.Vector Word[2,3,2,5,2,7,2,3,2,11]4And this is how to factorise all numbers in a block:sieveBlock (SieveBlockConfig [] (\p k -> [(unPrime p, k)]) (++)) 2 10 :: Data.Vector.Vector [(Word, Word)][[(2,1)],[(3,1)],[(2,2)],[(5,1)],[(2,1),(3,1)],[(7,1)],[(2,3)],[(3,2)],[(2,1),(5,1)],[(11,1)]]arithmoiThis is  specialized to unboxed vectors.?sieveBlockUnboxed (SieveBlockConfig 1 (\_ a -> a + 1) (*)) 1 10[1,2,2,3,2,4,2,4,3,4]  (c) 2018 Andrew LelechenkoMIT/Andrew Lelechenko NonearithmoiCompute individual values of Mertens function in O(n^(2/3)) time and space.map (mertens . (10 ^)) [0..9]%[1,-1,1,2,-23,-48,212,1037,1928,-222],The implementation follows Theorem 3.1 from  $https://arxiv.org/pdf/1610.08551.pdfComputations of the Mertens function and improved bounds on the Mertens conjecture/ by G. Hurst, excluding segmentation of sieves.(c) 2018 Andrew LelechenkoMIT/Andrew Lelechenko None?,/ arithmoi#Wrapper to use in conjunction with  and -. Extracts the minimal preimage of function.arithmoi#Wrapper to use in conjunction with  and -. Extracts the maximal preimage of function.arithmoi#Wrapper to use in conjunction with  and -. Extracts the minimal preimage of function.arithmoi#Wrapper to use in conjunction with  and -. Extracts the maximal preimage of function.arithmoiThe inverse for  function.'The return value is parameterized by a , which allows various applications by providing different (multiplicative) embeddings. E. g., list all preimages (see a helper ):import qualified Data.Set as Simport Data.SemigroupS.mapMonotonic getProduct (inverseTotient (S.singleton . Product) 120)fromList [143,155,175,183,225,231,244,248,286,308,310,350,366,372,396,450,462]Count preimages:inverseTotient (const 1) 12017Sum preimages:inverseTotient id 1204904#Find minimal and maximal preimages:&unMinWord (inverseTotient MinWord 120)143&unMaxWord (inverseTotient MaxWord 120)462arithmoiThe inverse for  function.Generalizes the  function, which is  1.'The return value is parameterized by a , which allows various applications by providing different (multiplicative) embeddings. E. g., list all preimages (see a helper ):import qualified Data.Set as Simport Data.SemigroupS.mapMonotonic getProduct (inverseJordan 2 (S.singleton . Product) 192)fromList [15,16] Similarly to , it is possible to count and sum preimages, or get the maximum/minimum preimage.Note: it is the user's responsibility! to use an appropriate type for . Even low values of k with  or  will return invalid results due to over/underflow, or throw exceptions (i.e. division by zero).?asSetOfPreimages (inverseJordan 15) (jordan 15 19) :: S.Set Int fromList []asSetOfPreimages (inverseJordan 15) (jordan 15 19) :: S.Set Integer fromList [19]arithmoiThe inverse for  1 function.'The return value is parameterized by a , which allows various applications by providing different (multiplicative) embeddings. E. g., list all preimages (see a helper ):import qualified Data.Set as Simport Data.Semigroup:set -XFlexibleContextsS.mapMonotonic getProduct (inverseSigma (S.singleton . Product) 120)fromList [54,56,87,95]Count preimages:inverseSigma (const 1) 1204Sum preimages:inverseSigma id 120292#Find minimal and maximal preimages:$unMinWord (inverseSigma MinWord 120)54$unMaxWord (inverseSigma MaxWord 120)95arithmoiThe inverse for  function.Generalizes the  function, which is  1.'The return value is parameterized by a , which allows various applications by providing different (multiplicative) embeddings. E. g., list all preimages (see a helper ):import qualified Data.Set as Simport Data.Semigroup:set -XFlexibleContextsS.mapMonotonic getProduct (inverseSigmaK 2 (S.singleton . Product) 850)fromList [24,26] Similarly to , it is possible to count and sum preimages, or get the maximum/minimum preimage.Note: it is the user's responsibility! to use an appropriate type for . Even low values of k with  or  will return invalid results due to over/underflow, or throw exceptions (i.e. division by zero).>asSetOfPreimages (inverseSigmaK 17) (sigma 17 13) :: S.Set Int&fromList *** Exception: divide by zeroarithmoi)Helper to extract a set of preimages for  or .K(c) 2018 Andrew LelechenkoMIT/Andrew Lelechenko None.arithmoi"Division-free computation of [ n  x | x <- [hi, hi - 1 .. lo] ]. In other words, we compute y-coordinates of highest integral points under hyperbola  x * y = n between x = lo and x = hi in reverse order.(The implementation follows section 5 of  #https://arxiv.org/pdf/1206.3369.pdfA successive approximation algorithm for computing the divisor summatory function by R. Sladkey. It is 2x faster than a trivial implementation for .L"(c) 2018 Alexandre Rodrigues BaldMIT4Alexandre Rodrigues Bald  Safe-Inferred1_arithmoiJoins two lists element-by-element together into one, starting with the first one provided as argument.(take 10 (intertwine [0, 2 ..] [1, 3 ..])[0,1,2,3,4,5,6,7,8,9]arithmoiSkips every odd-indexed element from an infinite list. Do NOT use with finite lists.take 10 (skipOdds [0, 1 ..])[0,2,4,6,8,10,12,14,16,18]arithmoiSkips every even-indexed element from an infinite list. Do NOT use with finite lists.take 10 (skipEvens [0, 1 ..])[1,3,5,7,9,11,13,15,17,19]M"(c) 2018 Alexandre Rodrigues BaldMIT4Alexandre Rodrigues Bald None5garithmoi-Values of Hurwitz zeta function evaluated at (s, a) for  s D [0, 1 ..].The algorithm used was based on the Euler-Maclaurin formula and was derived from  %http://fredrikj.net/thesis/thesis.pdfFast and Rigorous Computation of Special Functions to High Precision by F. Johansson, chapter 4.8, formula 4.8.5. The error for each value in this recurrence is given in formula 4.8.9 as an indefinite integral, and in formula 4.8.12 as a closed form formula. It is the user's responsibility: to provide an appropriate precision for the type chosen.For instance, when using Double/s, it does not make sense to provide a number   < 1e-53 as the desired precision. For Floats, providing an   < 1e-24 also does not make sense. Example of how to call the function:zetaHurwitz 1e-15 0.25 !! 51024.3489745265808N(c) 2016 Andrew LelechenkoMIT/Andrew Lelechenko None9arithmoiInfinite sequence of exact values of Riemann zeta-function at even arguments, starting with (0)3. Note that due to numerical errors conversion to  may return values below 1:,approximateValue (zetasEven !! 25) :: Double0.9999999999999996Use your favorite type for long-precision arithmetic. For instance, OP works fine:import Data.Number.Fixed2approximateValue (zetasEven !! 25) :: Fixed Prec5041.00000000000000088817842111574532859293035196051773arithmoiInfinite sequence of approximate values of Riemann zeta-function at odd arguments, starting with (1).arithmoiInfinite sequence of approximate (up to given precision) values of Riemann zeta-function at integer arguments, starting with (0). take 5 (zetas 1e-14) :: [Double][-0.5,Infinity,1.6449340668482264,1.2020569031595942,1.0823232337111381]Beware to force evaluation of  zetas !! 1 if the type a2 does not support infinite values (for instance, OP).Q"(c) 2018 Alexandre Rodrigues BaldMIT4Alexandre Rodrigues Bald None=larithmoiInfinite sequence of exact values of Dirichlet beta-function at odd arguments, starting with (1).import Data.ExactPi+approximateValue (betasOdd !! 25) :: Double0.9999999999999987import Data.Number.Fixed1approximateValue (betasOdd !! 25) :: Fixed Prec5040.99999999999999999999999960726927497384196726751694arithmoi9Infinite sequence of approximate values of the Dirichlet = function at positive even integer arguments, starting with (0).arithmoiInfinite sequence of approximate (up to given precision) values of Dirichlet beta-function at integer arguments, starting with (0). take 5 (betas 1e-14) :: [Double][0.5,0.7853981633974483,0.9159655941772189,0.9689461462593694,0.9889445517411051]5(c) 2018 Alexandre Rodrigues Bald, Andrew LelechenkoMIT/Andrew Lelechenko None=RSTUVWUVXUVYZ[\]^_`abccdefEgh i / j 0#k$l$l$m$n$opqrstuv)w)x)y)z){)|*7*}*~**,,,12   \ r   ]                   k                      444  6 7  - .                            ;   <>>>>D%%Dyz{JJJJJJJJJJJJJJJ=JJJJJJJJJJJJJJJJJJJHJyIMNNQQRRR!!!"""$RR&&&&&&k&&&''''''''''''''''''''''''''(((((((((((((((R*+++++++R++++++RRRRR,11R11111112236333>FFRRRRRRRKRLLLNQ(arithmoi-0.12.0.2-1LBW47IaiR6Hp9NDnAlXclMath.NumberTheory.Moduli.Class$Math.NumberTheory.Euclidean.Coprimes Math.NumberTheory.Moduli.Chinese!Math.NumberTheory.Primes.CountingMath.NumberTheory.Recurrences%Math.NumberTheory.DirichletCharactersMath.NumberTheory.SmoothNumbersMath.NumberTheory.Moduli.Sqrt Math.NumberTheory.Primes.TestingMath.NumberTheory.PrimesMath.NumberTheory.Primes.IntSet$Math.NumberTheory.Recurrences.Linear&Math.NumberTheory.Recurrences.BilinearMath.NumberTheory.Prefactored%Math.NumberTheory.ArithmeticFunctions Math.NumberTheory.Powers.Modular"Math.NumberTheory.MoebiusInversion"Math.NumberTheory.Moduli.Singleton,Math.NumberTheory.Quadratic.GaussianIntegers.Math.NumberTheory.Quadratic.EisensteinIntegers"Math.NumberTheory.Moduli.Equations'Math.NumberTheory.Moduli.MultiplicativeMath.NumberTheory.Moduli.CbrtMath.NumberTheory.Diophantine.Math.NumberTheory.ArithmeticFunctions.NFreedom-Math.NumberTheory.ArithmeticFunctions.Moebius0Math.NumberTheory.ArithmeticFunctions.SieveBlock-Math.NumberTheory.ArithmeticFunctions.Mertens-Math.NumberTheory.ArithmeticFunctions.InverseMath.NumberTheory.Zeta Math.NumberTheory.Moduli.SomeMod-Math.NumberTheory.Primes.Counting.Approximate'Math.NumberTheory.Primes.Sieve.IndexingMath.NumberTheory.Primes.Small(Math.NumberTheory.Recurrences.PentagonalMath.NumberTheory.RootsOfUnitynorm'Math.NumberTheory.Utils.DirichletSeries$Math.NumberTheory.Utils.FromIntegralMath.NumberTheory.Utils%Math.NumberTheory.Moduli.JacobiSymbol.Math.NumberTheory.Primes.Testing.Probabilistic#Math.NumberTheory.Curves.MontgomeryMath.NumberTheory.Primes.Types nextPrime precPrimeapproxPrimeCountnthPrimeApprox+Math.NumberTheory.Primes.Sieve.Eratosthenes4Math.NumberTheory.Primes.Factorisation.TrialDivision1Math.NumberTheory.Primes.Factorisation.Montgomery&Math.NumberTheory.Primes.Counting.Impl&Math.NumberTheory.Primes.Factorisation factoriseisPrimeMath.Combinat.NumbersunsignedStirling1st stirling2nd bernoulli*Math.NumberTheory.Primes.Testing.Certifiedtotient+Math.NumberTheory.ArithmeticFunctions.ClassData.SemigroupProductSum getProductgetSumpowMod powSomeMod!Math.NumberTheory.Moduli.InternalMath.NumberTheory.ModuliisNFreesieveBlockUnboxed.Math.NumberTheory.ArithmeticFunctions.Standard!Math.NumberTheory.Utils.HyperbolaMath.NumberTheory.Zeta.UtilsMath.NumberTheory.Zeta.HurwitzMath.NumberTheory.Zeta.RiemannData.Number.FixedFixed Math.NumberTheory.Zeta.Dirichletbase GHC.TypeNatsKnownNat"mod-0.1.2.2-JoL2OL2sjtZ3pIOuCwINTnData.Mod^% invertModModCoprimes unCoprimes singletoninsertsplitIntoCoprimes$fMonoidCoprimes$fSemigroupCoprimes $fEqCoprimes$fShowCoprimesSomeModInfModmodulo invertSomeModchinesechineseSomeMod!approxPrimeCountOverestimateLimit nthPrimeApproxUnderestimateLimit partition RootOfUnityfromRootOfUnity toRootOfUnity toComplex SmoothBasis unSmoothBasisfromList smoothOver' smoothOverisSmooth$fShowSmoothBasis JacobiSymbolMinusOneZeroOne symbolToNumjacobi millerRabinVisStrongFermatPP isFermatPP bailliePSWPrimeunPrimetoPrimeIntegralprimestrialDivisionPrimeTo PrimeIntSet unPrimeIntSet fromAscListfromDistinctAscListdeletemember notMemberlookupEQlookupLTlookupGTlookupLElookupGEnullsize isSubsetOfisProperSubsetOfdisjoint difference\\symmetricDifference intersectionfiltersplit splitMember splitLookupEQ splitRootfoldrfoldlfoldr'foldl' deleteMin deleteMaxminViewmaxView toAscList toDescList$fIsListPrimeIntSet$fEqPrimeIntSet$fOrdPrimeIntSet$fDataPrimeIntSet$fShowPrimeIntSet$fSemigroupPrimeIntSet$fMonoidPrimeIntSet$fNFDataPrimeIntSetprimeCountMaxArg primeCountnthPrimeUniqueFactorisation factorBack$fBoundedPrime $fEnumPrime$fBoundedPrime0 $fEnumPrime0 $fEnumPrime1 $fEnumPrime2$fUniqueFactorisationNatural$fUniqueFactorisationInteger$fUniqueFactorisationWord$fUniqueFactorisationInt factorialfactorialFactors fibonacci fibonacciPairlucas lucasPair generalLucasbinomialbinomialRotated binomialLinebinomialDiagonalbinomialFactors stirling1 stirling2lah eulerian1 eulerian2 faulhaberPolyeuler eulerPolyAt1isCertifiedPrime Prefactored prefValue prefFactors fromValue fromFactors $fUniqueFactorisationPrefactored$fNumPrefactored$fSemiringPrefactored$fEqPrefactored$fShowPrefactoredArithmeticFunction runFunctionrunFunctionOnFactors powModWord powModInt totientSumgeneralInversion CyclicGroupSFactors unSFactorsSomeCGDoubleOddPrimePowerCGOddPrimePowerCG4CG2sfactors someSFactorsproofFromSFactors cyclicGroupcyclicGroupFromFactorscyclicGroupFromModuloproofFromCyclicGroupsfactorsToCyclicGroupcyclicGroupToSFactors $fNFDataSome $fShowSome $fOrdSome$fEqSome$fNFDataSFactors $fOrdSFactors $fEqSFactors $fNFDataSome0 $fShowSome0 $fOrdSome0 $fEqSome0$fNFDataCyclicGroup$fOrdCyclicGroup$fEqCyclicGroup$fShowCyclicGroup$fGenericCyclicGroup$fShowSFactors$fGenericSFactorssqrtsModsqrtsModFactorisationsqrtsModPrimePower sqrtsModPrimeGaussianInteger:+realimagι conjugate findPrime$$fUniqueFactorisationGaussianInteger$fEuclideanGaussianInteger$fGcdDomainGaussianInteger$fRingGaussianInteger$fSemiringGaussianInteger$fNumGaussianInteger$fShowGaussianInteger$fNFDataGaussianInteger$fEqGaussianInteger$fOrdGaussianInteger$fGenericGaussianIntegerEisensteinIntegerωids associates&$fUniqueFactorisationEisensteinInteger$fEuclideanEisensteinInteger$fGcdDomainEisensteinInteger$fRingEisensteinInteger$fSemiringEisensteinInteger$fNumEisensteinInteger$fShowEisensteinInteger$fNFDataEisensteinInteger$fEqEisensteinInteger$fOrdEisensteinInteger$fGenericEisensteinInteger solveLinearsolveQuadratic PrimitiveRootunPrimitiveRootMultMod multElement isMultElement invertGroupisPrimitiveRootdiscreteLogarithm$fBoundedMultMod$fMonoidMultMod$fSemigroupMultMod$fEqPrimitiveRoot$fShowPrimitiveRoot $fEqMultMod $fOrdMultMod $fShowMultModgetMod getNatModgetVal getNatVal CubicSymbolOmega OmegaSquare cubicSymbol$fShowCubicSymbol$fSemigroupCubicSymbol$fEqCubicSymbolcornacchiaPrimitive cornacchiasieveBlockNFreenFrees nFreesBlockMoebiusMoebiusNMoebiusZMoebiusP runMoebiussieveBlockMoebius$fMonoidMoebius$fSemigroupMoebius$fVectorVectorMoebius$fMVectorMVectorMoebius$fUnboxMoebius $fEqMoebius $fOrdMoebius $fShowMoebiusmultiplicativedivisors divisorsA divisorsList divisorsListA divisorsSmalldivisorsSmallA divisorsTo divisorsToA divisorCounttautauAsigmasigmaAtotientAjordanjordanA ramanujan ramanujanAmoebiusmoebiusA liouville liouvilleA carmichael carmichaelAadditive smallOmega smallOmegaAbigOmega bigOmegaA expMangoldt expMangoldtAisNFreeAOrZeroWithNatPrimitiveCharactergetPrimitiveChar RealCharacter getRealCharDirichletCharacterNonZeroeval evalGeneral principalCharcharacterNumber indexToCharindicesToCharsallChars isPrincipalinducedjacobiCharacterisRealCharactertoRealFunction validChar orderChar isPrimitive makePrimitive orZeroToNumevalAll fromTable$fEqDirichletFactor$fBoundedDirichletCharacter$fEnumDirichletCharacter$fMonoidDirichletCharacter$fSemigroupDirichletCharacter$fEqDirichletCharacter$fEqPrimitiveCharacter$fEqRealCharacterSieveBlockConfigsbcEmptysbcFunctionOnPrimePower sbcAppendmultiplicativeSieveBlockConfigadditiveSieveBlockConfigrunFunctionOverBlock sieveBlockmertens MinNaturalInfinity unMinNatural MaxNatural unMaxNaturalMinWord unMinWordMaxWord unMaxWordinverseTotient inverseJordan inverseSigma inverseSigmaKasSetOfPreimages$fShowPrimePowers$fSemiringMaxWord$fSemiringMinWord$fSemiringMaxNatural$fSemiringMinNatural$fEqMinNatural$fOrdMinNatural$fShowMinNatural$fEqMaxNatural$fOrdMaxNatural$fShowMaxNatural $fEqMinWord $fOrdMinWord $fShowMinWord $fEqMaxWord $fOrdMaxWord $fShowMaxWord zetaHurwitz zetasEvenzetasbetasOddbetasGHC.NumNumGHC.Real Fractional^$fFieldSomeMod$fEuclideanSomeMod$fGcdDomainSomeMod$fFractionalSomeModidxPrtoPrimrhosmallPrimesFromTosmallPrimesLengthsmallPrimesPtr$fSemigroupRootOfUnityGHC.BasestimesIntegral timesAndCropDirichletSerieslookupunionsunion wordToInt wordToInteger intToWord intToInt8 intToInt64 int8ToInt64 intToWord8 intToWord64 int8ToInt int64ToInt word8ToInt word64ToInt intToIntegerint16ToIntegerint64ToIntegerword64ToIntegernaturalToIntegerintegerToNatural integerToWordintegerToWord64 integerToIntintegerToInt64 intToNatural naturalToInt intToDouble fromIntegral'shiftToOddCount shiftToOdd shiftToOdd#shiftToOddCount# splitOff#splitOffmergeByrecipMod SomeKnownshiftToOddCountBigNat toWheel30 fromWheel30 withSomeKnownintValmod lucasTest SomePointPointpointXpointZpointA24pointNnewPoint GHC.MaybeNothingadddoublemultiply $fShowPoint $fEqPointGHC.EnumEnum Data.BitstoIntegralSized bitSizeMaybeghc-prim GHC.TypesIntWordJust fromIntegral PrimeSieve primeSievemaxBound primeList psieveListsieveTo psieveFrominteger-wired-inGHC.Integer.TypeIntegerPS sieveBits sieveRangetrialDivisionWithtrialDivisionTo%random-1.2.1.1-4yg3wqkjsQdBr0UpSZdkxvSystem.Random.InternalStdGenmontgomeryFactorisation smallFactors findParms$semirings-0.6-FyDe2N42BneIrzRyn3Jfk7 Data.SemiringSemiring$fNumArithmeticFunctionisPrimitiveRoot'discreteLogarithmPPgcdBounded Data.MonoidApsuccpredtoEnumfromEnumpointsUnderHyperbolaquot intertwineskipOdds skipEvensDoublezetasOdd betasEven