mathxlab.nt.arithmetic

Arithmetic functions and factor-sieve helpers.

Stability

Status: Experimental.

This project treats the documented names as the public surface, but details may still evolve. If you need strict API guarantees, add __all__ = [...] to each module and version releases accordingly.

Design notes

• Functions are designed for experiment-scale inputs (not cryptographic workloads).

• Prefer explicit parameters (e.g., n_max) for reproducibility.

Examples

Factorize using a smallest-prime-factor sieve

from mathxlab.nt.arithmetic import build_factor_sieve, factorize
sieve = build_factor_sieve(100)
print(factorize(84, sieve=sieve))

Public API

Name	Kind	Summary
FactorSieve	class	Factor-sieve data for fast integer arithmetic.
build_factor_sieve	function	Build a linear-time smallest-prime-factor sieve.
factorize	function	Factorize n into prime powers using the SPF sieve.
lcm	function	Compute the least common multiple.
compute_phi	function	Compute φ(n) for 0..n_max via dynamic SPF recurrence.
compute_mobius	function	Compute μ(n) for 0..n_max using SPF recurrence.
compute_omega	function	Compute ω(n): number of distinct prime factors of n.
compute_big_omega	function	Compute Ω(n): number of prime factors of n with multiplicity.
compute_tau_sigma	function	Compute τ(n) and σ(n) for 0..n_max using SPF recurrences.
liouville	function	Compute Liouville function λ(n) from Ω(n).
carmichael_lambda_for_prime_power	function	Compute Carmichael’s λ(p^e).
carmichael_lambda	function	Compute Carmichael’s lambda function λ(n).
jordan_totient	function	Compute Jordan’s totient function J_k(n).
compute_von_mangoldt	function	Compute Λ(n) for n=0..n_max.
von_mangoldt	function	Compute the von Mangoldt function Λ(n).
chebyshev_psi	function	Compute Chebyshev’s ψ(x) for x=0..n_max.

Reference

Classes

class mathxlab.nt.arithmetic.FactorSieve(n_max, spf, primes)

Bases: object

Factor-sieve data for fast integer arithmetic.

n_max

Maximum integer covered by the sieve.

spf

Smallest prime factor for every n in [0..n_max]. For n < 2, the value is 0.

primes

List of primes up to n_max.

Examples

>>> from mathxlab.nt.arithmetic import FactorSieve
>>> FactorSieve

Functions

mathxlab.nt.arithmetic.build_factor_sieve(n_max)

Build a linear-time smallest-prime-factor sieve.

Parameters:

n_max – Maximum integer to cover (inclusive). Must be >= 2.

Returns:

FactorSieve instance.

Raises:

ValueError – If n_max < 2.

Examples

>>> from mathxlab.nt.arithmetic import build_factor_sieve
>>> sieve = build_factor_sieve(100)
>>> sieve.primes[:5]
[2, 3, 5, 7, 11]

mathxlab.nt.arithmetic.factorize(n, *, sieve)

Factorize n into prime powers using the SPF sieve.

Parameters:

• n – Integer to factorize (>= 1).

• sieve – Factor sieve.

Returns:

List of (prime, exponent) pairs. For n == 1 the list is empty.

Raises:

ValueError – If n is out of bounds for the sieve or n < 1.

Examples

>>> from mathxlab.nt.arithmetic import build_factor_sieve, factorize
>>> sieve = build_factor_sieve(1000)
>>> factorize(360, sieve=sieve)
[(2, 3), (3, 2), (5, 1)]

mathxlab.nt.arithmetic.lcm(a, b)

Compute the least common multiple.

Parameters:

• a – First integer.

• b – Second integer.

Returns:

lcm(a, b) with lcm(0, b) == 0.

Examples

>>> from mathxlab.nt.arithmetic import lcm
>>> lcm

mathxlab.nt.arithmetic.compute_phi(n_max, *, sieve)

Compute φ(n) for 0..n_max via dynamic SPF recurrence.

Parameters:

• n_max – Maximum n to compute (<= sieve.n_max).

• sieve – Factor sieve.

Returns:

List phi where phi[n] = φ(n). phi[0] = 0, phi[1] = 1.

Examples

>>> from mathxlab.nt.arithmetic import build_factor_sieve, compute_phi
>>> sieve = build_factor_sieve(20)
>>> compute_phi(10, sieve=sieve)[1:6]
[1, 1, 2, 2, 4]

mathxlab.nt.arithmetic.compute_mobius(n_max, *, sieve)

Compute μ(n) for 0..n_max using SPF recurrence.

Parameters:

• n_max – Maximum n to compute (<= sieve.n_max).

• sieve – Factor sieve.

Returns:

List mu where mu[n] = μ(n). mu[0]=0, mu[1]=1.

Examples

>>> from mathxlab.nt.arithmetic import build_factor_sieve, compute_mobius
>>> sieve = build_factor_sieve(20)
>>> compute_mobius(10, sieve=sieve)[1:11]
[1, -1, -1, 0, -1, 1, -1, 0, 0, 1]

mathxlab.nt.arithmetic.compute_omega(n_max, *, sieve)

Compute ω(n): number of distinct prime factors of n.

Parameters:

• n_max – Maximum n to compute (<= sieve.n_max).

• sieve – Factor sieve.

Returns:

List omega with omega[0]=0, omega[1]=0.

Examples

>>> from mathxlab.nt.arithmetic import compute_omega
>>> compute_omega

mathxlab.nt.arithmetic.compute_big_omega(n_max, *, sieve)

Compute Ω(n): number of prime factors of n with multiplicity.

Parameters:

• n_max – Maximum n to compute (<= sieve.n_max).

• sieve – Factor sieve.

Returns:

List big_omega with big_omega[0]=0, big_omega[1]=0.

Examples

>>> from mathxlab.nt.arithmetic import compute_big_omega
>>> compute_big_omega

mathxlab.nt.arithmetic.compute_tau_sigma(n_max, *, sieve)

Compute τ(n) and σ(n) for 0..n_max using SPF recurrences.

Parameters:

• n_max – Maximum n to compute (<= sieve.n_max).

• sieve – Factor sieve.

Returns:

(tau, sigma) where – tau[n] = number of divisors of n (τ(n)), sigma[n] = sum of divisors of n (σ(n)).

Examples

>>> from mathxlab.nt.arithmetic import compute_tau_sigma
>>> compute_tau_sigma

mathxlab.nt.arithmetic.liouville(big_omega_n)

Compute Liouville function λ(n) from Ω(n).

Parameters:

big_omega_n – Ω(n).

Returns:

λ(n) = (-1)^{Ω(n)} as +1 or -1.

Examples

>>> from mathxlab.nt.arithmetic import liouville
>>> liouville

mathxlab.nt.arithmetic.carmichael_lambda_for_prime_power(p, e)

Compute Carmichael’s λ(p^e).

Parameters:

• p – Prime.

• e – Exponent (>= 1).

Returns:

λ(p^e) as integer.

Examples

>>> from mathxlab.nt.arithmetic import carmichael_lambda_for_prime_power
>>> carmichael_lambda_for_prime_power

mathxlab.nt.arithmetic.carmichael_lambda(n, *, sieve)

Compute Carmichael’s lambda function λ(n).

Parameters:

• n – Integer to evaluate (>= 1).

• sieve – Factor sieve.

Returns:

λ(n).

Raises:

ValueError – If n out of range.

Examples

>>> from mathxlab.nt.arithmetic import carmichael_lambda
>>> carmichael_lambda

mathxlab.nt.arithmetic.jordan_totient(n, k, *, sieve)

Compute Jordan’s totient function J_k(n).

J_k(n) = n^k ∏_{p|n} (1 - 1/p^k)

Parameters:

• n – Integer to evaluate (>= 1).

• k – Parameter k (>= 1).

• sieve – Factor sieve.

Returns:

J_k(n).

Examples

>>> from mathxlab.nt.arithmetic import jordan_totient
>>> jordan_totient

mathxlab.nt.arithmetic.compute_von_mangoldt(n_max, *, sieve)

Compute Λ(n) for n=0..n_max.

Λ(n) = log p if n is a prime power p^k (k>=1), else 0.

Parameters:

• n_max – Maximum n.

• sieve – Factor sieve.

Returns:

List lam where lam[n] = Λ(n) as float.

Examples

>>> from mathxlab.nt.arithmetic import compute_von_mangoldt
>>> compute_von_mangoldt

mathxlab.nt.arithmetic.von_mangoldt(n, *, sieve)

Compute the von Mangoldt function Λ(n).

Λ(n) = log p if n is a prime power p^k (k>=1), else 0.

Parameters:

• n – Integer to evaluate (>= 1).

• sieve – Factor sieve.

Returns:

Λ(n) as float (natural logarithm).

Examples

>>> from mathxlab.nt.arithmetic import von_mangoldt
>>> von_mangoldt

mathxlab.nt.arithmetic.chebyshev_psi(n_max, *, sieve)

Compute Chebyshev’s ψ(x) for x=0..n_max.

ψ(x) = ∑_{n<=x} Λ(n)

Parameters:

• n_max – Maximum x.

• sieve – Factor sieve.

Returns:

List psi where psi[x] = ψ(x).

Examples

>>> from mathxlab.nt.arithmetic import chebyshev_psi
>>> chebyshev_psi