Math Operations

Operations regarding number theory and related topics. More...

Functions
bool	tgen::math::is_prime (uint64_t n)
	Checks if a number is prime.
std::vector< uint64_t >	tgen::math::factor (uint64_t n)
	Factors a number into primes.
std::vector< std::pair< uint64_t, int > >	tgen::math::factor_by_prime (uint64_t n)
	Factors a number into primes and its powers.
uint64_t	tgen::math::modular_inverse (uint64_t a, uint64_t mod)
	Computes modular inverse.
uint64_t	tgen::math::totient (uint64_t n)
	Euler's totient function.
const std::pair< std::vector< uint64_t >, std::vector< uint64_t > > &	tgen::math::prime_gaps ()
	Fetches prime gaps.
std::pair< uint64_t, uint64_t >	tgen::math::prime_gap_upto (uint64_t r)
	Largest prime gap up to given number.
const std::vector< uint64_t > &	tgen::math::highly_composites ()
	Fetches highly composite numbers.
uint64_t	tgen::math::highly_composite_upto (uint64_t r)
	Largest highly composite number up to given number.
uint64_t	tgen::math::gen_prime (uint64_t l, uint64_t r)
	Generates a random prime in given range.
uint64_t	tgen::math::prime_from (uint64_t l)
	Computes smallest prime from given value.
uint64_t	tgen::math::prime_upto (uint64_t r)
	Computes largest prime up to given value.
int	tgen::math::num_divisors (uint64_t n)
	Computes the number of divisors of a given number.
uint64_t	tgen::math::gen_divisor_count (uint64_t l, uint64_t r, int divisor_count)
	Generates random number in range with a given prime number of divisors.
uint64_t	tgen::math::gen_congruent (uint64_t l, uint64_t r, std::vector< uint64_t > rems, std::vector< uint64_t > mods)
	Generates random number in range given modular congruences.
uint64_t	tgen::math::gen_congruent (uint64_t l, uint64_t r, uint64_t rem, uint64_t mod)
	Generates random number in range given a modular congruence.
uint64_t	tgen::math::gen_even (uint64_t l, uint64_t r)
	Generates random even number in a given range.
uint64_t	tgen::math::gen_odd (uint64_t l, uint64_t r)
	Generates random odd number in a given range.
const std::vector< uint64_t > &	tgen::math::fibonacci ()
	Fetches Fibonacci numbers.
std::vector< int >	tgen::math::gen_partition (int n, int part_l=1, int part_r=-1)
	Generates a random partition of a number.
std::vector< int >	tgen::math::gen_partition_fixed_size (int n, int k, int part_l=0, int part_r=-1)
	Generates a random partition with fixed size of a number.

Variables
constexpr int	tgen::math::FFT_MOD = 998244353
	FFT/NTT mod.

Detailed Description

Operations regarding number theory and related topics.

Examples

// Generates a random prime from 1 to 1e18.
auto p = tgen::math::gen_prime(1, 1e18);
 
// Prints primes from 100 to 200.
for (int p = tgen::math::prime_from(100); p <= 200; p = tgen::math::prime_from(p + 1)) {
    std::cout << p << std::endl;
}
 
// Computes largest prime gap up to 1e12.
auto [l, r] = tgen::math::prime_gap_upto(1e12);
 
// Prints random two-digit number that is even and congruent to 1 mod 3.
std::cout << tgen::math::gen_congruent(10, 99, {0, 1}, {2, 3}) << std::endl;
 
// Random partition of 10 into 4 parts in [2, 3].
auto part = tgen::math::gen_partition_fixed_size(10, 4, 2, 3);

Function Documentation

factor()

std::vector< uint64_t > tgen::math::factor ( uint64_t n )

inline

Factors a number into primes.

Parameters

n	Number to factor.

Precondition

n > 0.

Returns

List of prime factors of n, in non-decreasing order.

Complexity

O(n^(1/4) log n) expected.

Examples

auto fact = tgen::math::factor(24);
// {2, 2, 2, 3}

Definition at line 1375 of file tgen.h.

factor_by_prime()

std::vector< std::pair< uint64_t, int > > tgen::math::factor_by_prime ( uint64_t n )

inline

Factors a number into primes and its powers.

Parameters

n	Number to factor.

Precondition

n > 0.

Returns

List of prime factors of n, in increasing order, with its respective powers.

Complexity

O(n^(1/4) log n) expected.

Examples

auto fact = tgen::math::factor_by_prime(24);
// {{2, 3}, {3, 1}}

Definition at line 1385 of file tgen.h.

fibonacci()

const std::vector< uint64_t > & tgen::math::fibonacci ( )

inline

Fetches Fibonacci numbers.

Fetches Fibonacci numbers that fit in uint64_t (less than 2^64).

Examples

// Prints 5th fibonacci number.
std::cout << tgen::math::fibonacci()[5] << std::endl;

Definition at line 1805 of file tgen.h.

gen_congruent() [1/2]

uint64_t tgen::math::gen_congruent ( uint64_t l, uint64_t r, std::vector< uint64_t > rems, std::vector< uint64_t > mods )

inline

Generates random number in range given modular congruences.

Parameters

l	Left endpoint of range.
r	Right endpoint of range.
rems	Remainders.
mods	Mods.

Precondition

|rems| = |mods|.
rems[i] < mods[i].

Returns

Uniformly random number in [l, r] that is congruent to rems[i] mod mods[i].

Exceptions

std::runtime_error

if there is no such number.

Complexity

O(|mods| + log r).

Examples

// Prints random two-digit number that is even and congruent to 1 mod 3.
std::cout << tgen::math::gen_congruent(10, 99, {0, 1}, {2, 3}) << std::endl;

Definition at line 1742 of file tgen.h.

gen_congruent() [2/2]

uint64_t tgen::math::gen_congruent ( uint64_t l, uint64_t r, uint64_t rem, uint64_t mod )

inline

Generates random number in range given a modular congruence.

Parameters

l	Left endpoint of range.
r	Right endpoint of range.
rem	Remainder.
mod	Mod.

Precondition

rem < mod.

Equivalent to tgen::math::gen_congruent(l, r, {rem}, {mod}).

Returns

Uniformly random number in [l, r] that is congruent to rem mod mod.

Exceptions

std::runtime_error

if there is no such number.

Complexity

O(1).

Examples

// Prints random two-digit number that is congruent to 1 mod 3.
std::cout << tgen::math::gen_congruent(10, 99, 1, 3) << std::endl;

Definition at line 1785 of file tgen.h.

gen_divisor_count()

uint64_t tgen::math::gen_divisor_count ( uint64_t l, uint64_t r, int divisor_count )

inline

Generates random number in range with a given prime number of divisors.

Parameters

l	Left endpoint of range.
r	Right endpoint of range.
divisor_count	Number of divisors.

Precondition

divisor_count is prime.

Returns

Uniformly random number with given prime number of divisors.

Complexity

O(log(r) log(divisor_count)).

Examples

// Generates a random number from 100 to 200 with 3 divisors (p^2).
auto n = tgen::math::num_divisors(100, 200, 3);

Definition at line 1659 of file tgen.h.

gen_even()

uint64_t tgen::math::gen_even ( uint64_t l, uint64_t r )

inline

Generates random even number in a given range.

Parameters

l	Left endpoint of range.
r	Right endpoint of range.

Equivalent to tgen::math::gen_congruent(l, r, {0}, {2}).

Returns

Uniformly random even number in [l, r].

Exceptions

std::runtime_error

if there is no such number.

Complexity

O(log r).

Examples

// Prints random two-digit even number.
std::cout << tgen::math::gen_even(10, 99) << std::endl;

Definition at line 1792 of file tgen.h.

gen_odd()

uint64_t tgen::math::gen_odd ( uint64_t l, uint64_t r )

inline

Generates random odd number in a given range.

Parameters

l	Left endpoint of range.
r	Right endpoint of range.

Equivalent to tgen::math::gen_congruent(l, r, {1}, {2}).

Returns

Uniformly random odd number in [l, r].

Exceptions

std::runtime_error

if there is no such number.

Complexity

O(log r).

Examples

// Prints random two-digit odd number.
std::cout << tgen::math::gen_odd(10, 99) << std::endl;

Definition at line 1797 of file tgen.h.

gen_partition()

std::vector< int > tgen::math::gen_partition ( int n, int part_l = 1, int part_r = -1 )

inline

Generates a random partition of a number.

Parameters

n	Number to partition.
part_l	Minimum part value.
part_r	Maximum part value.

Precondition

n > 0.
part_l > 0.

Partition is ordered (so technically a composition). That is, (1, 1, 2) != (1, 2, 1). If part_r = -1, part_r is considered to be n (unbounded).

Returns

A uniformly random ordered partition of n with values in [part_l, part_r].

Exceptions

std::runtime_error

if there is no such partition.

Note

Distribution might be slighly biased because of floating point arithmetic.

Complexity

O(n).

Examples

// Random partition of 10 into parts in [2, 3].
auto part = tgen::math::partition(10, 2, 3);

Definition at line 1854 of file tgen.h.

gen_partition_fixed_size()

std::vector< int > tgen::math::gen_partition_fixed_size ( int n, int k, int part_l = 0, int part_r = -1 )

inline

Generates a random partition with fixed size of a number.

Parameters

n	Number to partition.
k	Number of parts.
part_l	Minimum part value.
part_r	Maximum part value.

Precondition

n >= k > 0.
part_l >= 0.

Partition is ordered (so technically a composition). That is, (1, 1, 2) != (1, 2, 1). If part_r = -1, part_r is considered to be n (unbounded).

Returns

A uniformly random ordered partition of n with length k and values in [part_l, part_r].

Exceptions

std::runtime_error

if there is no such partition.

Note

Distribution might be slighly biased because of floating point arithmetic.

Complexity

O(n) time/memory if part_r = -1;
O(n * k) time/memory otherwise.

Examples

// Random partition of 10 into 4 parts in [2, 3].
auto part = tgen::math::partition_fixed_size(10, 4, 2, 3);

Definition at line 1917 of file tgen.h.

gen_prime()

uint64_t tgen::math::gen_prime ( uint64_t l, uint64_t r )

inline

Generates a random prime in given range.

Parameters

l	Left endpoint of range.
r	Right endpoint of range.

Precondition

n > 0.

Returns

A uniformly random prime in [l, r].

Complexity

O(log r) expected.

Examples

// Generates a random prime from 1 to 1e18.
auto p = tgen::math::gen_prime(1, 1e18);

Definition at line 1554 of file tgen.h.

highly_composite_upto()

uint64_t tgen::math::highly_composite_upto ( uint64_t r )

inline

Largest highly composite number up to given number.

Parameters

r

Bound.

Returns

Largest highly composite number no larger than r.

Examples

// Prints largest highly composite number up to 1e12.
std::cout << tgen::math::highly_composite_upto(1e12) << std::endl;

Definition at line 1544 of file tgen.h.

highly_composites()

const std::vector< uint64_t > & tgen::math::highly_composites ( )

inline

Fetches highly composite numbers.

Fetches highly composite numbers that fit in uint64_t (less than 2^64).

Returns

Highly composite numbers from wikipedia.

Examples

// Prints largest highly composite number that fits in 64 bits.
std::cout << tgen::math::highly_composites().back() << std::endl;

Definition at line 1504 of file tgen.h.

is_prime()

bool tgen::math::is_prime ( uint64_t n )

inline

Checks if a number is prime.

Parameters

n	Number to check.

Returns

If the number is prime.

Complexity

O(log^2 n).

Examples

bool is_prime = tgen::math::is_prime(17);
// true

Definition at line 1314 of file tgen.h.

modular_inverse()

uint64_t tgen::math::modular_inverse ( uint64_t a, uint64_t mod )

inline

Computes modular inverse.

Parameters

a	Number to compute the inverse of, mod mod.
mod	Mod.

Precondition

mod > a >= 0.
gcd(a, mod) = 1.

Returns

Inverse of a mod mod.

Complexity

O(log mod).

Examples

auto inv = tgen::math::modular_inverse(3, 10);
std::cout << 3 * inv % 10 << std::endl;
// "1"

Definition at line 1433 of file tgen.h.

num_divisors()

int tgen::math::num_divisors ( uint64_t n )

inline

Computes the number of divisors of a given number.

Parameters

n	Number to compute the ammount of divisors of.

Precondition

n > 0.

Returns

Number of divisors of n.

Complexity

O(n^(1/4) log n) expected.

Examples

std::cout << tgen::math::num_divisors(12) << std::endl;
// "6"

Definition at line 1650 of file tgen.h.

prime_from()

uint64_t tgen::math::prime_from ( uint64_t l )

inline

Computes smallest prime from given value.

Parameters

l

Bound.

Precondition

l <= 2^64 - 59.

Returns

Smallest prime larger than or equal to l.

Complexity

O(log^3 l) expected.

Examples

// Prints primes from 100 to 200.
for (int p = tgen::math::prime_from(100); p <= 200; p = tgen::math::prime_from(p + 1)) {
    std::cout << p << std::endl;
}

Definition at line 1578 of file tgen.h.

prime_gap_upto()

std::pair< uint64_t, uint64_t > tgen::math::prime_gap_upto ( uint64_t r )

inline

Largest prime gap up to given number.

Parameters

r

Bound.

Returns

Largest prime gap no larger than r.

Examples

// Computes largest prime gap up to 1e12.
auto [l, r] = tgen::math::prime_gap_upto(1e12);

Definition at line 1485 of file tgen.h.

prime_gaps()

const std::pair< std::vector< uint64_t >, std::vector< uint64_t > > & tgen::math::prime_gaps ( )

inline

Fetches prime gaps.

Fetches maximal prime gaps for numbers that fit in uint64_t (less than 2^64).

Returns

Columns p_n and g_n from wikipedia.

Examples

const auto &[p, g] = tgen::math::prime_gaps();

Definition at line 1451 of file tgen.h.

prime_upto()

uint64_t tgen::math::prime_upto ( uint64_t r )

inline

Computes largest prime up to given value.

Parameters

r

Bound.

Returns

Largest prime smaller than or equal to r.

Complexity

O(log^3 r) expected.

Examples

// Prints primes from 100 to 200 in reverse.
for (int p = tgen::math::prime_upto(200); p >= 100; p = tgen::math::prime_upto(p - 1)) {
    std::cout << p << std::endl;
}

Definition at line 1587 of file tgen.h.

totient()

uint64_t tgen::math::totient ( uint64_t n )

inline

Euler's totient function.

Parameters

n	Number to compute the totient of.

Precondition

n > 0.

Returns

Totient of n.

Complexity

O(n^(1/4) log n) expected.

Examples

std::cout << tgen::math::totient(10) << std::endl;
// "4"

Definition at line 1439 of file tgen.h.

Variable Documentation

FFT_MOD

int tgen::math::FFT_MOD = 998244353

inlineconstexpr

FFT/NTT mod.

Examples

int fft_mod = tgen::math::FFT_MOD;

Definition at line 1802 of file tgen.h.