Documentation

runFunctionOverBlock f x l 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 runFunction.

This is a thin wrapper over sieveBlock, read more details there.

>>> import Math.NumberTheory.ArithmeticFunctions
>>> runFunctionOverBlock carmichaelA 1 10
[1,1,2,2,4,2,6,2,6,4]

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               = (*)
  }

Create a config for a multiplicative function from its definition on prime powers.

Create a config for an additive function from its definition on prime powers.

Evaluate 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 Parity 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+ε)).

sieveBlock is similar to sieveBlockUnboxed up to flavour of Vector, but is typically 7x-10x slower and consumes 3x memory. Use unboxed version whenever possible.

For example, following code lists smallest prime factors:

>>> sieveBlock (SieveBlockConfig maxBound (\p _ -> unPrime p) min) 2 10
[2,3,2,5,2,7,2,3,2,11]

And this is how to factorise all numbers in a block:

>>> sieveBlock (SieveBlockConfig [] (\p k -> [(unPrime p, k)]) (++)) 2 10
[[(2,1)],[(3,1)],[(2,2)],[(5,1)],[(2,1),(3,1)],[(7,1)],[(2,3)],[(3,2)],[(2,1),(5,1)],[(11,1)]]

Evaluate 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 Parity 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+ε)).

For example, here is an analogue of divisor function tau:

>>> sieveBlockUnboxed (SieveBlockConfig 1 (\_ a -> a + 1) (*)) 1 10
[1,2,2,3,2,4,2,4,3,4]

Evaluate the Möbius 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 Computations of the Mertens function and improved bounds on the Mertens conjecture by G. Hurst. It is approximately 5x faster than sieveBlockUnboxed.

>>> sieveBlockMoebius 1 10
[MoebiusP,MoebiusN,MoebiusN,MoebiusZ,MoebiusN,MoebiusP,MoebiusN,MoebiusZ,MoebiusZ,MoebiusP]