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 right)
	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 right)
	Largest highly composite number up to given number.
uint64_t	tgen::math::gen_prime (uint64_t left, uint64_t right)
	Generates a random prime in given range.
uint64_t	tgen::math::prime_from (uint64_t left)
	Computes smallest prime from given value.
uint64_t	tgen::math::prime_upto (uint64_t right)
	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 left, uint64_t right, int divisor_count)
	Generates random number in range with a given prime number of divisors.
uint64_t	tgen::math::gen_congruent (uint64_t left, uint64_t right, 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 left, uint64_t right, uint64_t rem, uint64_t mod)
	Generates random number in range given a modular congruence.
uint64_t	tgen::math::congruent_from (uint64_t left, std::vector< uint64_t > rems, std::vector< uint64_t > mods)
	Computes smallest congruent from given value.
uint64_t	tgen::math::congruent_from (uint64_t left, uint64_t rem, uint64_t mod)
	Computes smallest congruent from given value.
uint64_t	tgen::math::congruent_upto (uint64_t right, std::vector< uint64_t > rems, std::vector< uint64_t > mods)
	Computes largest congruent up to given value.
uint64_t	tgen::math::congruent_upto (uint64_t right, uint64_t rem, uint64_t mod)
	Computes largest congruent up to given value.
const std::vector< uint64_t > &	tgen::math::fibonacci ()
	Fetches Fibonacci numbers.
std::vector< int >	tgen::math::gen_partition (int n, int part_left=1, std::optional< int > part_right=std::nullopt)
	Generates a random partition of a number.
std::vector< int >	tgen::math::gen_partition_fixed_size (int n, int k, int part_left=0, std::optional< int > part_right=std::nullopt)
	Generates a random partition with fixed size of a number.
std::vector< uint64_t >	tgen::math::gen_partition_fixed_size_fast (uint64_t n, int k, uint64_t part_left=0, std::optional< uint64_t > part_right=std::nullopt)
	Generates a fast non-uniform partition with fixed size.
template<typename T>
std::vector< std::vector< T > >	tgen::math::partition_elements (std::vector< T > elements, int k, int min_size=0, std::optional< uint64_t > max_size=std::nullopt)
	Partitions a vector into k ordered groups.

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.

std::cout << tgen::math::gen_prime(1, 1e18) << std::endl;

104297037245455381

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;
}

101
103
...
199

Largest prime gap up to 1e12.

auto [l, r] = tgen::math::prime_gap_upto(1e12);
std::cout << l << " " << r << " " << r - l << std::endl;

738832927928 738832928466 538

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;

34

Random partition of 10 into 4 parts in [2, 3].

std::cout << tgen::print(tgen::math::gen_partition_fixed_size(10, 4, 2, 3)) << std::endl;

3 3 2 2

Function Documentation

congruent_from() [1/2]

uint64_t tgen::math::congruent_from ( uint64_t left, std::vector< uint64_t > rems, std::vector< uint64_t > mods )

inline

Computes smallest congruent from given value.

Parameters

left	Bound.
rems	Remainders.
mods	Mods.

Precondition

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

Returns

Smallest congruent larger than or equal to left.

Exceptions

std::runtime_error

if there is no such number or if it does not fit in uint64_t.

Complexity

O(|mods| + log(lcm)), if lcm is the least common multiple of the mods.

Examples

// Prints congruent from 10.
std::cout << tgen::math::congruent_from(10, {0, 1}, {2, 3}) << std::endl;

Definition at line 2982 of file tgen.h.

congruent_from() [2/2]

uint64_t tgen::math::congruent_from ( uint64_t left, uint64_t rem, uint64_t mod )

inline

Computes smallest congruent from given value.

Parameters

left	Bound.
rem	Remainder.
mod	Mod.

Precondition

rem < mod.

Equivalent to tgen::math::congruent_from(left, {rem}, {mod}).

Returns

Smallest congruent larger than or equal to left.

Exceptions

std::runtime_error

if there is no such number or if it does not fit in uint64_t.

Complexity

O(log mod).

Examples

// Prints even number from 10.
std::cout << tgen::math::congruent_from(10, 0, 2) << std::endl;

Definition at line 3021 of file tgen.h.

congruent_upto() [1/2]

uint64_t tgen::math::congruent_upto ( uint64_t right, std::vector< uint64_t > rems, std::vector< uint64_t > mods )

inline

Computes largest congruent up to given value.

Parameters

right	Bound.
rems	Remainders.
mods	Mods.

Precondition

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

Returns

Largest congruent smaller than or equal to right.

Exceptions

std::runtime_error

if there is no such number.

Complexity

O(|mods| + log right).

Examples

// Prints congruent up to 1e3.
std::cout << tgen::math::congruent_upto(1e3, {0, 1}, {2, 3}) << std::endl;

Definition at line 3030 of file tgen.h.

congruent_upto() [2/2]

uint64_t tgen::math::congruent_upto ( uint64_t right, uint64_t rem, uint64_t mod )

inline

Computes largest congruent up to given value.

Parameters

right	Bound.
rem	Remainder.
mod	Mod.

Precondition

rem < mod.

Equivalent to tgen::math::congruent_upto(right, {rem}, {mod}).

Returns

Largest congruent smaller than or equal to right.

Exceptions

std::runtime_error

if there is no such number.

Complexity

O(log right).

Examples

// Prints odd number up to 1e3.
std::cout << tgen::math::congruent_upto(1e3, 1, 2) << std::endl;

Definition at line 3070 of file tgen.h.

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 2715 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 2725 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; // Prints "5".

Definition at line 3079 of file tgen.h.

gen_congruent() [1/2]

uint64_t tgen::math::gen_congruent ( uint64_t left, uint64_t right, std::vector< uint64_t > rems, std::vector< uint64_t > mods )

inline

Generates random number in range given modular congruences.

Parameters

left	Left endpoint of range.
right	Right endpoint of range.
rems	Remainders.
mods	Mods.

Precondition

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

Returns

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

Exceptions

std::runtime_error

if there is no such number.

Complexity

O(|mods| + log right).

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 2928 of file tgen.h.

gen_congruent() [2/2]

uint64_t tgen::math::gen_congruent ( uint64_t left, uint64_t right, uint64_t rem, uint64_t mod )

inline

Generates random number in range given a modular congruence.

Parameters

left	Left endpoint of range.
right	Right endpoint of range.
rem	Remainder.
mod	Mod.

Precondition

rem < mod.

Equivalent to tgen::math::gen_congruent(left, right, {rem}, {mod}).

Returns

Uniformly random number in [left, right] that is congruent to rem mod mod.

Exceptions

std::runtime_error

if there is no such number.

Complexity

O(log right).

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 2972 of file tgen.h.

gen_divisor_count()

uint64_t tgen::math::gen_divisor_count ( uint64_t left, uint64_t right, int divisor_count )

inline

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

Parameters

left	Left endpoint of range.
right	Right endpoint of range.
divisor_count	Number of divisors.

Precondition

divisor_count must be prime.

Returns

Uniformly random number with given prime number of divisors.

Complexity

O(log(right) log(divisor_count)).

Examples

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

Definition at line 2915 of file tgen.h.

gen_partition()

std::vector< int > tgen::math::gen_partition ( int n, int part_left = 1, std::optional< int > part_right = std::nullopt )

inline

Generates a random partition of a number.

Parameters

n	Number to partition.
part_left	Minimum part value.
part_right	Maximum part value.

Precondition

n > 0.
part_left > 0.

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

Returns

A uniformly random ordered partition of n with values in [part_left, part_right].

Exceptions

std::runtime_error

if there is no such partition.

Note

Distribution might be slightly biased because of floating point arithmetic.

Complexity

O(n).

Examples

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

Definition at line 3095 of file tgen.h.

gen_partition_fixed_size()

std::vector< int > tgen::math::gen_partition_fixed_size ( int n, int k, int part_left = 0, std::optional< int > part_right = std::nullopt )

inline

Generates a random partition with fixed size of a number.

Parameters

n	Number to partition.
k	Number of parts.
part_left	Minimum part value.
part_right	Maximum part value.

Precondition

n >= k > 0.
part_left >= 0.

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

Returns

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

Exceptions

std::runtime_error

if there is no such partition.

Note

Distribution might be slightly biased because of floating point arithmetic.

Complexity

O(n) time/memory if part_right is not set;
O(n * k) time/memory otherwise.

Examples

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

Definition at line 3161 of file tgen.h.

gen_partition_fixed_size_fast()

std::vector< uint64_t > tgen::math::gen_partition_fixed_size_fast ( uint64_t n, int k, uint64_t part_left = 0, std::optional< uint64_t > part_right = std::nullopt )

inline

Generates a fast non-uniform partition with fixed size.

Parameters

n	Number to partition.
k	Number of parts.
part_left	Minimum part value.
part_right	Maximum part value.

Precondition

n >= k > 0.
part_left >= 0.

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

Inspired by jngen: draw k - 1 random delimiters with replacement, sort them, and recover part sizes from the gaps.

Returns

A random ordered partition of n with length k and values in [part_left, part_right].

Exceptions

std::runtime_error

if there is no such partition.

Note

This operation is not uniformly random.

Complexity

O(k log k).

Examples

// Fast partition of 10^18 into 10^6 parts.
auto part = tgen::math::gen_partition_fixed_size_fast(1e18, 1e6);

Definition at line 3259 of file tgen.h.

gen_prime()

uint64_t tgen::math::gen_prime ( uint64_t left, uint64_t right )

inline

Generates a random prime in given range.

Parameters

left	Left endpoint of range.
right	Right endpoint of range.

Returns

A uniformly random prime in [left, right].

Exceptions

std::runtime_error

if there is no prime in the given range.

Complexity

O(log^3 right) expected.

Examples

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

Definition at line 2861 of file tgen.h.

highly_composite_upto()

uint64_t tgen::math::highly_composite_upto ( uint64_t right )

inline

Largest highly composite number up to given number.

Parameters

right

Bound.

Returns

Largest highly composite number no larger than right.

Examples

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

Definition at line 2851 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 OEIS A002182.

Examples

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

Definition at line 2811 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 2463 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; // Prints "1".

Definition at line 2740 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 amount 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; // Prints "6".

Definition at line 2905 of file tgen.h.

partition_elements()

template<typename T>

std::vector< std::vector< T > > tgen::math::partition_elements	(	std::vector< T >	elements,
		int	k,
		int	min_size = 0,
		std::optional< uint64_t >	max_size = std::nullopt )

Partitions a vector into k ordered groups.

Parameters

elements	Values to partition (order preserved; not shuffled).
k	Number of groups.
min_size	Minimum size of each group.
max_size	Maximum size of each group (defaults to unbounded).

Returns

k groups whose sizes form a random composition of elements.size() with the given bounds. Elements keep their relative order within the concatenation of the groups.

If max_size is not set, group sizes are drawn uniformly via gen_partition_fixed_size. If max_size is set, sizes use the faster non-uniform gen_partition_fixed_size_fast instead. Only the group sizes are random; element order is unchanged.

Note

This function is not always uniform: group sizes are uniform only when max_size is not set.

Complexity

O(n) if max_size is not set (uniform, via gen_partition_fixed_size);
O(n + k log k) if max_size is set (fast, via gen_partition_fixed_size_fast).

Examples

// Uniform group sizes (minimum 1 per group).
auto uniform = tgen::math::partition_elements({1, 2, 3, 4, 5}, 2, 1);
// Bounded group sizes (fast, non-uniform).
auto bounded = tgen::math::partition_elements({1, 2, 3, 4, 5}, 2, 1, 4);

Definition at line 3350 of file tgen.h.

prime_from()

uint64_t tgen::math::prime_from ( uint64_t left )

inline

Computes smallest prime from given value.

Parameters

left

Bound.

Precondition

left <= 2^64 - 59.

Returns

Smallest prime larger than or equal to left.

Complexity

O(log^3 left) 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 2886 of file tgen.h.

prime_gap_upto()

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

inline

Largest prime gap up to given number.

Parameters

right

Bound.

Returns

Largest prime gap no larger than right.

Examples

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

Definition at line 2792 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 2758 of file tgen.h.

prime_upto()

uint64_t tgen::math::prime_upto ( uint64_t right )

inline

Computes largest prime up to given value.

Parameters

right

Bound.

Returns

Largest prime smaller than or equal to right.

Complexity

O(log^3 right) 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 2895 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; // Prints "4".

Definition at line 2746 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 3076 of file tgen.h.