A lot of functions and stuffs to deal the sigma_odd problem and related stuffs. More...

Classes
struct	FactorExp
	Structure to represent a factor with its exponent. More...

Typedefs
typedef uint64_t	nat_type
	Type for natural number used in all code, on 64 bits. More...

typedef unsigned __int128	tmp_uint128_type
	Type double size for some temporary calculation. More...

typedef uint32_t	prime_type
	Type for prime number, particularly for the table of primes. More...

Functions
std::vector< nat_type >	coprime_factors_ (nat_type a, nat_type b)
	Return a list of factors such that all factors are coprimes and divide a*b, and these factors are (possibly) sufficient for coprime_factor_exps(). More...

std::ostream &	operator<< (std::ostream &out, const FactorExp &factor_exp)
	Return "factor^exponent" representation of factor_exp. More...

std::vector< FactorExp >	coprime_factor_exps (nat_type a, nat_type b)
	Heuristic to return a list of factors with their exponents such that all factors are coprimes and the product == a*b. If failed to have a list at least two factors then return an empty list. More...

std::pair< nat_type, unsigned int >	divide_until_nb (nat_type n, nat_type d)
	Divide n by d until the result is not divisible by d, and return (result, number of divisions). More...

nat_type	first_divisor (nat_type n)
	Return the first divisor of n > 1 (or 1 if n <= 1) More...

bool	is_square (nat_type n)
	Return true iff n is a perfect square. More...

nat_type	pollard_rho (nat_type n)
	Return pollard_rho(n, rand() % n, floor square root of n). More...

nat_type	pollard_rho (nat_type n, nat_type random, nat_type max_iteration)
	Heuristic to find a proper divisor of n with the Pollard's rho heuristic. More...

nat_type	pollard_rho_repeat (nat_type n, nat_type nb_tries)
	Try pollard_rho(n) a maximum of nb_tries times and return 0 or the first divisor find. More...

nat_type	sum_divisors__factorize (nat_type n)
	Calculates the sum of all divisors of n by the factorization method and returns it. More...

nat_type	sum_divisors__naive (nat_type n)
	Calculates the sum of all divisors of n by the naive method and returns it. More...

nat_type	sum_odd_divisors__factorize (nat_type n)
	Calculates the sum of odd divisors of n by the factorization method and returns it. More...

nat_type	sum_odd_divisors__naive (nat_type n)
	Calculates the sum of odd divisors of n by the naive method and returns it. More...

nat_type	sum_odd_divisors_upper_bound (nat_type n)
	Return an upper bound of sum odd divisors. More...

nat_type	sum_odd_divisors_upper_bound__DeTemple (nat_type n)
	Return an upper bound of sum odd divisors of n using the DeTemple inequalities. More...

nat_type	sum_odd_divisors_upper_bound__DeTemple_ceil (nat_type n)
	Return an upper bound of sum odd divisors of n using the DeTemple inequalities. ??? More...

nat_type	sum_odd_divisors_upper_bound__DeTemple (nat_type n, nat_type k)
	Return an upper bound of sum odd divisors of n using the DeTemple inequalities and the knowledge that n have no divisors <= k. More...

nat_type	divide_until_odd (nat_type n)
	Return n divided by 2 until the result is odd. More...

std::pair< nat_type, unsigned int >	divide_until_odd_nb (nat_type n)
	Divide n by 2 until the result is odd, and return (result, number of divisions). More...

constexpr nat_type	gcd (nat_type a, nat_type b)
	Return the Greatest Common Divisor of a and b. More...

constexpr nat_type	is_coprime (nat_type a, nat_type b)
	Return true iff a and b are coprime (relatively prime). More...

constexpr bool	is_divide (nat_type d, nat_type n)
	Return true iff d divide n, i.e. if n is divisible by d. More...

constexpr bool	is_first_mersenne_prime_unitary_divide (nat_type n)
	Return true iff at least one of 3, 7, 31 or 127 is an unitary divisor of n. More...

constexpr bool	is_first_mersenne_prime_unitary_divide_or_square (nat_type n)
	Return true iff is_first_mersenne_prime_unitary_divide(n) or is_square(n). More...

constexpr bool	is_little_mersenne_prime_unitary_divide (nat_type n)
	Return true iff at least one of 3, 7, 31, 127, 8191, 131071 or 524287 is an unitary divisor of n. More...

constexpr bool	is_mersenne_prime_unitary_divide (nat_type n)
	Return true iff at least one of 3, 7, 31, 127, 8191, 131071, 524287, 2147483647 or 2305843009213693951 is an unitary divisor of n. More...

constexpr bool	is_unitary_divide (nat_type d, nat_type n)
	Return true iff (d divide n) and (d NOT divide n/d). More...

void	print_arrow_ (nat_type from, nat_type to, unsigned int length, bool circular)

void	print_varsigmaodd_dot (nat_type first, nat_type last, bool show_node=true, bool shortcut=false, bool circular=false)
	Print to std::cout in a DOT format, a graph of path of the sigma odd problem. More...

double	diff_half_harmonic_upper_bound (nat_type a, nat_type b)
	Return an upper bound of H_a - 1/2 H_b. More...

double	diff_half_harmonic_upper_bound (nat_type n)
	Return an upper bound of H_n - 1/2 H_k with k = floor(n/2). More...

double	diff_harmonic_upper_bound (nat_type a, nat_type b)
	Return an upper bound of H_a - H_b. More...

double	harmonic_lower_bound (nat_type n)
	Return a lower bound of H_n. More...

double	harmonic_upper_bound (nat_type n)
	Return an upper bound of H_n. More...

nat_type	sum_floor_n_harmonic_odd (nat_type n, nat_type to_n)
	Return floor(n/1) + floor(n/3) + floor(n/5) + floor(n/7) + ... + (n/to_n or floor(1/(to_n-1))). More...

constexpr double	harmonic (nat_type n)
	Return the harmonic number H_n = 1/1 + 1/2 + 1/3 + 1/4 + ... + 1/n. More...

constexpr double	harmonic_even (nat_type n)
	Return 1/2 + 1/4 + 1/6 + 1/8 + ... + (1/n or 1/(n-1)). More...

constexpr double	harmonic_odd (nat_type n)
	Return 1/1 + 1/3 + 1/5 + 1/7 + ... + (1/n or 1/(n-1)). More...

nat_type	floor_eighth_root (nat_type n)
	Return the eighth root of n rounded to below. More...

nat_type	floor_fourth_root (nat_type n)
	Return the fourth root of n rounded to below. More...

nat_type	floor_square_root (nat_type n)
	Return the square root of n rounded to below. More...

std::vector< nat_type >	load_bad_table (const std::string &filename, const std::vector< nat_type > &bad_table=std::vector< nat_type >())
	Read a file that contains list of bad numbers, add after bad_table, and return the result. More...

std::vector< nat_type >	load_numbers (const std::string &filename)
	Read the file and extract each natural number begining a line. Return the list of these numbers. More...

nat_type	ceil_eighth_root (nat_type n)
	Return the eighth root of n rounded to above. More...

nat_type	ceilx_fourth_root (nat_type n)
	Return the fourth root of n rounded to above. More...

nat_type	ceil_square_root (nat_type n)
	Return the square root of n rounded to above. More...

constexpr bool	is_even (nat_type n)
	Return true iff n is even. More...

constexpr bool	is_odd (nat_type n)
	Return true iff n is odd. More...

constexpr nat_type	pow_nat (nat_type n, unsigned int k)
	Return x^k, x power k. More...

constexpr double	square (double x)
	Return x*x. More...

constexpr nat_type	square (nat_type n)
	Return n*n. More...

constexpr nat_type	sum_even (nat_type n)
	Return 2 + 4 + 6 + 8 + ... + (n or n-1) = k(k + 1) with k = floor(n/2). More...

constexpr nat_type	sum_geometric_progression (nat_type r, unsigned int k)
	Return the sum of the (k + 1) terms of the geometric progression of the common ratio r. More...

constexpr nat_type	sum_geometric_progression_strict (nat_type r, unsigned int k)
	Return sum_geometric_progression(r, k) but only for r > 1. More...

constexpr nat_type	sum_natural (nat_type n)
	Return 1 + 2 + 3 + 4 + ... + n = n(n + 1)/2. More...

constexpr nat_type	sum_odd (nat_type n)
	Return 1 + 3 + 5 + 7 + ... + (n or n-1) = k^2 with k floor((n+1)/2). More...

nat_type	ceil_fourth_root (nat_type n)

std::vector< nat_type >	sum_divisors__euler__table_ (sum_divisors__euler__table_nb_)

nat_type	sum_divisors_diff_ (nat_type n, nat_type pi)

nat_type	sum_divisors__euler (nat_type n)
	Calculates the sum of all divisors of n with the Euler formula about pentagonal numbers and returns it. More...

bool	sum_divisors__euler_cache_is_full ()
	Return true iff the cache used by sum_divisors__euler() is full. The function can clean space, but it is less efficient. More...

std::size_t	sum_divisors__euler_cache_nb ()
	Return the current number of items in the cache used by sum_divisors__euler() More...

std::size_t	sum_divisors__euler_table_nb ()
	Return the (constant) number of items in the table used by sum_divisors__euler() More...

constexpr nat_type	pentagonal (nat_type n)
	Return the pentagonal number of n. More...

constexpr nat_type	pentagonal_neg (nat_type n)
	Return the generalized pentagonal number of -n. More...

std::vector< FactorExp >	factorize (nat_type n)
	Return a list of prime factors with their exponents. More...

nat_type	factorization_to_n (std::vector< FactorExp > prime_exps)
	Return the number corresponding to the factorization. More...

nat_type	factorization_to_nu (std::vector< FactorExp > prime_exps)
	Return the number of all divisors of the number corresponding to the factorization. More...

nat_type	factorization_to_nu_odd (std::vector< FactorExp > prime_exps)
	Return the number of odd divisors of the number corresponding to the factorization. More...

nat_type	factorization_to_sigma (std::vector< FactorExp > prime_exps)
	Return the sum of all divisors of the number corresponding to the factorization. More...

nat_type	factorization_to_sigma_odd (std::vector< FactorExp > prime_exps)
	Return the sum of odd divisors of the number corresponding to the factorization. More...

bool	is_prime (nat_type n)
	Return true iff n is a prime number. More...

bool	is_prime_in_odd_primes_table (nat_type n)
	Return true iff n is a prime number present in the precalculated table. More...

bool	read_primes_table ()
	Read the binary file prime_filename to fill the table with all primes < 2^28. This table must be read from the binary file big_data/prime28.bin. More...

prime_type	odd_primes_table_by_index (unsigned int i)
	Return the (i + 1)th odd prime number from the precalculated table. More...

prime_type	odd_primes_table_last ()
	Return the last odd prime number in the precalculated table. More...

constexpr unsigned int	odd_primes_table_nb ()
	Return the number of odd prime numbers in the precalculated table. More...

const prime_type *	odd_primes_table_ptr ()
	Return a pointer to the first number in the precalculated table. More...

void	exit_if_found_exception_ (nat_type start_n, unsigned int length, nat_type n)

void	exit_if_impossible_to_check_ (nat_type start_n, unsigned int length, nat_type n)

double	percent_ (nat_type n, nat_type d)

void	print_data_ (nat_type n, nat_type result, unsigned int length, bool print_only_longer, bool print_path)

void	print_lengths_ (nat_type lengths[])

void	print_path_ (nat_type n)

void	check_varsigma_odd (nat_type first_n, nat_type last_n)
	Iterate from first to last (included) and for each odd n such that is_little_mersenne_prime_unitary_divide(n) is false, iterate var_sum() until the result is <= n. More...

std::string	path_to_string (const std::vector< nat_type > &path)

void	print_long (nat_type first, nat_type last, bool print_path)
	Iterate from first to last (included) and for each odd n not square such that is_little_mersenne_prime_unitary_divide(n) is false, if varsum_odd(n) > n then print n and varsum_odd(n). More...

void	print_path (const std::vector< nat_type > &path, std::ostream &out=std::cout)
	Send to the stream a string representation of the path. All numbers are separated by the corresponding <, = or > symbol. More...

void	print_path (const std::vector< nat_type >::const_iterator &path_begin, const std::vector< nat_type >::const_iterator &path_end, std::ostream &out=std::cout)
	Send to the stream a string representation of the path, from path_begin to path_end (included). All numbers are separated by the corresponding <, = or > symbol. More...

void	print_path_infos (const std::vector< nat_type > &path, bool print_bad=true, bool print_all=false, bool print_category=true, bool print_lower=true, bool print_length=true, bool print_path=true, std::ostream &out=std::cout)
	Send (if the below condition is true) to the stream a string representation of the path with some information depending of the boolean parameters. More...

void	print_sigmaodd__factorize (nat_type first, nat_type last, bool print_only_longer, bool print_path)
	Iterate from first to last (included) and print result of the sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize(n) with some informations. More...

void	print_sigmaodd__factorize_bound (nat_type first, nat_type last, bool print_only_longer, bool print_path)
	Iterate from first to last (included) and print result of the sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize_bound(n) with some informations. More...

void	print_sigmaodd__naive (nat_type first, nat_type last, bool print_only_longer, bool print_path)
	Iterate from first to last (included) and print result of the sum_odd_divisors_divided_until_odd_iterate_until_lower__naive(n) with some informations. More...

void	print_square (nat_type first, nat_type last, bool print_path)

nat_type	sum_odd_divisors_divided_until_odd__euler (nat_type n)
	Calculates the sum of all odd divisors of n by the Euler formula method, divides the results by 2 until becomes odd, and returns it. More...

nat_type	sum_odd_divisors_divided_until_odd__factorize (nat_type n, bool skip_primes_table=false)
	Calculates the sum of all odd divisors of n by the factorization method, divides the results by 2 until becomes odd, and returns it. More...

nat_type	sum_odd_divisors_divided_until_odd__factorize_bound (nat_type n, nat_type start_n)
	Calculates the sum of all odd divisors of n by the factorization method, divides the results by 2 until becomes odd, and returns it. ??? with bound. More...

nat_type	sum_odd_divisors_divided_until_odd__naive (nat_type n)
	Calculates the sum of all odd divisors of n by the naive method, divides the results by 2 until becomes odd, and returns it. More...

std::pair< nat_type, unsigned int >	sum_odd_divisors_divided_until_odd_iterate_until_lower__euler (nat_type n)
	Iterates the sum_odd_divisors_divided_until_odd__euler() function from n until have a result lower than n. More...

std::pair< nat_type, unsigned int >	sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize (nat_type n)
	Iterates the sum_odd_divisors_divided_until_odd__factorize() function from n until have a result lower than n. More...

std::pair< nat_type, unsigned int >	sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize_bound (nat_type n)
	Iterates the sum_odd_divisors_divided_until_odd__factorize() function from n until have a result lower than n. ??? with bound. More...

std::pair< nat_type, unsigned int >	sum_odd_divisors_divided_until_odd_iterate_until_lower__naive (nat_type n)
	Iterates the sum_odd_divisors_divided_until_odd__naive() function from n until have a result lower than n. More...

nat_type	varsum_odd (nat_type n)
	Calculates the sum of all odd divisors of n by the factorization method, divides the results by 2 until becomes odd, and returns it. ??? More...

nat_type	varsum_odd_big (nat_type n, nat_type sqrt_n)
	Calculates the sum of all odd divisors of n by the factorization method, divides the results by 2 until becomes odd, and returns it. ??? More...

Variables
const double	alpha = 0.425

const double	alpha_bis = 0.7

const double	beta = 0.40580406331047491619301581522449851

const double	euler_gamma = 0.577215664901532860606512090082402431042
	The Euler-Mascheroni constant 0.577215664901532860606512090082402431042... (rounded to an upper bound in double) http://mathworld.wolfram.com/Euler-MascheroniConstant.html. More...

constexpr nat_type	MAX_POSSIBLE_N = (static_cast<nat_type>(1) << 56) - 1
	Lower bound of the bigger number such that it is possible to compute the result of the sigma function. More...

size_t	sum_divisors__euler__cache_max_nb_ = 20000

size_t	sum_divisors__euler__table_nb_ = 1024*64

std::map< nat_type, nat_type >	sum_divisors__euler__cache_

const std::string	prime_filename = "big_data/prime28.bin"
	Default filename for the binary file "big_data/prime28.bin". More...

prime_type *	array_odd_primes_ = nullptr
	Array of all odd prime numbers < 2^28 with a final 0. (Or < 2^16 if the macro PRIME16 is defined.) More...

constexpr unsigned int	array_odd_primes_nb_ = 14630843u - 1
	Number of odd prime numbers in the table array_odd_primes_. More...

Detailed Description

A lot of functions and stuffs to deal the sigma_odd problem and related stuffs.

Typedef Documentation

◆ nat_type

typedef uint64_t sigmaodd::nat_type

Type for natural number used in all code, on 64 bits.

Definition at line 33 of file helper.hpp.

◆ prime_type

typedef uint32_t sigmaodd::prime_type

Type for prime number, particularly for the table of primes.

Definition at line 49 of file primes.hpp.

◆ tmp_uint128_type

typedef unsigned __int128 sigmaodd::tmp_uint128_type

Type double size for some temporary calculation.

Definition at line 42 of file helper.hpp.

Function Documentation

◆ ceil_eighth_root()

nat_type sigmaodd::ceil_eighth_root ( nat_type n )

inline

Return the eighth root of n rounded to above.

Definition at line 136 of file helper__inline.hpp.

◆ ceil_fourth_root()

nat_type sigmaodd::ceil_fourth_root ( nat_type n )

inline

Definition at line 147 of file helper__inline.hpp.

◆ ceil_square_root()

nat_type sigmaodd::ceil_square_root ( nat_type n )

inline

Return the square root of n rounded to above.

Definition at line 158 of file helper__inline.hpp.

◆ ceilx_fourth_root()

nat_type sigmaodd::ceilx_fourth_root ( nat_type n )

Return the fourth root of n rounded to above.

◆ check_varsigma_odd()

void sigmaodd::check_varsigma_odd	(	nat_type	first_n,
		nat_type	last_n
	)

Iterate from first to last (included) and for each odd n such that is_little_mersenne_prime_unitary_divide(n) is false, iterate var_sum() until the result is <= n.

If need more that one iteration then print n and the number of iterations.

Parameters

first_n	odd >= 3
last_n

Definition at line 164 of file sigmaodd.cpp.

◆ coprime_factor_exps()

std::vector< FactorExp > sigmaodd::coprime_factor_exps	(	nat_type	a,
		nat_type	b
	)

Heuristic to return a list of factors with their exponents such that all factors are coprimes and the product == a*b. If failed to have a list at least two factors then return an empty list.

Parameters

a	> 1
b	> 1

Definition at line 162 of file divisors.cpp.

◆ coprime_factors_()

std::vector< nat_type > sigmaodd::coprime_factors_	(	nat_type	a,
		nat_type	b
	)

Return a list of factors such that all factors are coprimes and divide a*b, and these factors are (possibly) sufficient for coprime_factor_exps().

Parameters

a	> 1
b	> 1

Definition at line 46 of file divisors.cpp.

◆ diff_half_harmonic_upper_bound() [1/2]

double sigmaodd::diff_half_harmonic_upper_bound	(	nat_type	a,
		nat_type	b
	)

Return an upper bound of H_a - 1/2 H_b.

Use Chen 2016 inequalities: https://link.springer.com/article/10.1007%2Fs11075-016-0116-9

H_a - 1/2 H_b < 1/2 ln( (2a+1)^2 / (2(2b+1)) ) + gamma/2 + 1/(24 (a^2 + a + beta)) - 1/(48 (b^2 + b + alpha))

Parameters

a	>= 1
b	>= 1

Returns: an upper bound of H_a - 1/2 H_b

Definition at line 42 of file harmonic.cpp.

◆ diff_half_harmonic_upper_bound() [2/2]

double sigmaodd::diff_half_harmonic_upper_bound ( nat_type n )

Return an upper bound of H_n - 1/2 H_k with k = floor(n/2).

Use Chen 2016 inequalities: https://link.springer.com/article/10.1007%2Fs11075-016-0116-9

H_n - 1/2 H_k < 1/2 ln( (2n+1)^2 / (2(n+1)) ) + gamma/2

1/(24 (n^2 + n + beta)) - 1/(12 ((n+1)^2 + alpha_bis)) if n even

H_n - 1/2 H_k < 1/2 ln( (2n+1)^2 / (2n)) ) + gamma/2

1/(24 (n^2 + n + beta)) - 1/(12 (n^2 + alpha_bis)) if n odd

Parameters

n >= 1

Returns: an upper bound of H_n - 1/2 H_{n/2}

Definition at line 64 of file harmonic.cpp.

◆ diff_harmonic_upper_bound()

double sigmaodd::diff_harmonic_upper_bound	(	nat_type	a,
		nat_type	b
	)

Return an upper bound of H_a - H_b.

Use Chen 2016 inequalities: https://link.springer.com/article/10.1007%2Fs11075-016-0116-9

H_a - H_b < ln((2a + 1)/(2b + 1)) + 1/(24 (a^2 + a + beta)) - 1/(24 (b^2 + b + alpha))

Parameters

a	>= 1
b	>= 1

Returns: an upper bound of H_a - H_b

Definition at line 94 of file harmonic.cpp.

◆ divide_until_nb()

std::pair< nat_type, unsigned int > sigmaodd::divide_until_nb	(	nat_type	n,
		nat_type	d
	)

Divide n by d until the result is not divisible by d, and return (result, number of divisions).

Parameters

n	!= 0
d	> 1

Returns: (result, number of divisions)

Definition at line 207 of file divisors.cpp.

◆ divide_until_odd()

nat_type sigmaodd::divide_until_odd ( nat_type n )

inline

Return n divided by 2 until the result is odd.

Parameters

n != 0

Definition at line 132 of file divisors__inline.hpp.

◆ divide_until_odd_nb()

std::pair< nat_type, unsigned int > sigmaodd::divide_until_odd_nb ( nat_type n )

inline

Divide n by 2 until the result is odd, and return (result, number of divisions).

Parameters

n != 0

Returns: (result, number of divisions)

Definition at line 142 of file divisors__inline.hpp.

◆ exit_if_found_exception_()

void sigmaodd::exit_if_found_exception_	(	nat_type	start_n,
		unsigned int	length,
		nat_type	n
	)

Definition at line 62 of file sigmaodd.cpp.

◆ exit_if_impossible_to_check_()

void sigmaodd::exit_if_impossible_to_check_	(	nat_type	start_n,
		unsigned int	length,
		nat_type	n
	)

Definition at line 74 of file sigmaodd.cpp.

◆ factorization_to_n()

nat_type sigmaodd::factorization_to_n ( std::vector< FactorExp > prime_exps )

Return the number corresponding to the factorization.

Parameters

prime_exps list of primes numbers with their exponent such that the corresponding number is not too big for nat_type

Definition at line 105 of file primes.cpp.

◆ factorization_to_nu()

nat_type sigmaodd::factorization_to_nu ( std::vector< FactorExp > prime_exps )

Return the number of all divisors of the number corresponding to the factorization.

Parameters

prime_exps list of distinct primes numbers with their exponent such that the corresponding number is not too big for nat_type

Definition at line 117 of file primes.cpp.

◆ factorization_to_nu_odd()

nat_type sigmaodd::factorization_to_nu_odd ( std::vector< FactorExp > prime_exps )

Return the number of odd divisors of the number corresponding to the factorization.

Parameters

prime_exps list of distinct primes numbers with their exponent such that the corresponding number is not too big for nat_type

Definition at line 129 of file primes.cpp.

◆ factorization_to_sigma()

nat_type sigmaodd::factorization_to_sigma ( std::vector< FactorExp > prime_exps )

Return the sum of all divisors of the number corresponding to the factorization.

Parameters

prime_exps list of distinct primes numbers with their exponent such that the corresponding number is not too big for nat_type

Definition at line 143 of file primes.cpp.

◆ factorization_to_sigma_odd()

nat_type sigmaodd::factorization_to_sigma_odd ( std::vector< FactorExp > prime_exps )

Return the sum of odd divisors of the number corresponding to the factorization.

Parameters

prime_exps list of distinct primes numbers with their exponent such that the corresponding number is not too big for nat_type

Definition at line 155 of file primes.cpp.

◆ factorize()

std::vector< FactorExp > sigmaodd::factorize ( nat_type n )

Return a list of prime factors with their exponents.

Parameters

n	!= 0 <= MAX_POSSIBLE_N

Definition at line 58 of file primes.cpp.

◆ first_divisor()

nat_type sigmaodd::first_divisor ( nat_type n )

Return the first divisor of n > 1 (or 1 if n <= 1)

Definition at line 223 of file divisors.cpp.

◆ floor_eighth_root()

nat_type sigmaodd::floor_eighth_root ( nat_type n )

Return the eighth root of n rounded to below.

Definition at line 27 of file helper.cpp.

◆ floor_fourth_root()

nat_type sigmaodd::floor_fourth_root ( nat_type n )

Return the fourth root of n rounded to below.

Definition at line 52 of file helper.cpp.

◆ floor_square_root()

nat_type sigmaodd::floor_square_root ( nat_type n )

Return the square root of n rounded to below.

Definition at line 76 of file helper.cpp.

◆ gcd()

constexpr nat_type sigmaodd::gcd	(	nat_type	a,
		nat_type	b
	)

Return the Greatest Common Divisor of a and b.

If a and b == 0, then return 0.

Return the Greatest Common Divisor of a and b

Definition at line 45 of file divisors__inline.hpp.

◆ harmonic()

constexpr double sigmaodd::harmonic ( nat_type n )

Return the harmonic number H_n = 1/1 + 1/2 + 1/3 + 1/4 + ... + 1/n.

H_0 = 0

http://mathworld.wolfram.com/HarmonicNumber.html

Returns: the harmonic number H_n

Definition at line 20 of file harmonic__inline.hpp.

◆ harmonic_even()

constexpr double sigmaodd::harmonic_even ( nat_type n )

Return 1/2 + 1/4 + 1/6 + 1/8 + ... + (1/n or 1/(n-1)).

Definition at line 33 of file harmonic__inline.hpp.

◆ harmonic_lower_bound()

double sigmaodd::harmonic_lower_bound ( nat_type n )

Return a lower bound of H_n.

Use Chen 2016 inequalities: https://link.springer.com/article/10.1007%2Fs11075-016-0116-9

ln(n + 1/2) + gamma + 1/(24 (n^2 + n + alpha)) < H_n

Returns: an upper bound of H_n

Definition at line 115 of file harmonic.cpp.

◆ harmonic_odd()

constexpr double sigmaodd::harmonic_odd ( nat_type n )

Return 1/1 + 1/3 + 1/5 + 1/7 + ... + (1/n or 1/(n-1)).

Definition at line 40 of file harmonic__inline.hpp.

◆ harmonic_upper_bound()

double sigmaodd::harmonic_upper_bound ( nat_type n )

Return an upper bound of H_n.

Use Chen 2016 inequalities: https://link.springer.com/article/10.1007%2Fs11075-016-0116-9

H_n <= ln(n + 1/2) + gamma + 1/(24 (n^2 + n + beta))

Returns: an upper bound of H_n

Definition at line 134 of file harmonic.cpp.

◆ is_coprime()

constexpr nat_type sigmaodd::is_coprime	(	nat_type	a,
		nat_type	b
	)

Return true iff a and b are coprime (relatively prime).

Definition at line 66 of file divisors__inline.hpp.

◆ is_divide()

constexpr bool sigmaodd::is_divide	(	nat_type	d,
		nat_type	n
	)

Return true iff d divide n, i.e. if n is divisible by d.

Parameters

d	!= 0
n

Definition at line 73 of file divisors__inline.hpp.

◆ is_even()

constexpr bool sigmaodd::is_even ( nat_type n )

Return true iff n is even.

Definition at line 25 of file helper__inline.hpp.

◆ is_first_mersenne_prime_unitary_divide()

constexpr bool sigmaodd::is_first_mersenne_prime_unitary_divide ( nat_type n )

Return true iff at least one of 3, 7, 31 or 127 is an unitary divisor of n.

These numbers are Mersenne primes.

List of prime Mersenne numbers: https://oeis.org/A000668

Definition at line 82 of file divisors__inline.hpp.

◆ is_first_mersenne_prime_unitary_divide_or_square()

constexpr bool sigmaodd::is_first_mersenne_prime_unitary_divide_or_square ( nat_type n )

Return true iff is_first_mersenne_prime_unitary_divide(n) or is_square(n).

Definition at line 92 of file divisors__inline.hpp.

◆ is_little_mersenne_prime_unitary_divide()

constexpr bool sigmaodd::is_little_mersenne_prime_unitary_divide ( nat_type n )

Return true iff at least one of 3, 7, 31, 127, 8191, 131071 or 524287 is an unitary divisor of n.

These numbers are Mersenne primes.

List of prime Mersenne numbers: https://oeis.org/A000668

Definition at line 99 of file divisors__inline.hpp.

◆ is_mersenne_prime_unitary_divide()

constexpr bool sigmaodd::is_mersenne_prime_unitary_divide ( nat_type n )

Return true iff at least one of 3, 7, 31, 127, 8191, 131071, 524287, 2147483647 or 2305843009213693951 is an unitary divisor of n.

These numbers are all the Mersenne primes < 2^64.

List of prime Mersenne numbers: https://oeis.org/A000668

Definition at line 109 of file divisors__inline.hpp.

◆ is_odd()

constexpr bool sigmaodd::is_odd ( nat_type n )

Return true iff n is odd.

Definition at line 32 of file helper__inline.hpp.

◆ is_prime()

bool sigmaodd::is_prime ( nat_type n )

Return true iff n is a prime number.

Definition at line 169 of file primes.cpp.

◆ is_prime_in_odd_primes_table()

bool sigmaodd::is_prime_in_odd_primes_table ( nat_type n )

Return true iff n is a prime number present in the precalculated table.

Definition at line 215 of file primes.cpp.

◆ is_square()

bool sigmaodd::is_square ( nat_type n )

Return true iff n is a perfect square.

Definition at line 267 of file divisors.cpp.

◆ is_unitary_divide()

constexpr bool sigmaodd::is_unitary_divide	(	nat_type	d,
		nat_type	n
	)

Return true iff (d divide n) and (d NOT divide n/d).

Parameters

d	!= 0
n

Definition at line 118 of file divisors__inline.hpp.

◆ load_bad_table()

std::vector< nat_type > sigmaodd::load_bad_table	(	const std::string &	filename,
		const std::vector< nat_type > &	bad_table
	)

Read a file that contains list of bad numbers, add after bad_table, and return the result.

Definition at line 100 of file helper.cpp.

◆ load_numbers()

std::vector< nat_type > sigmaodd::load_numbers ( const std::string & filename )

Read the file and extract each natural number begining a line. Return the list of these numbers.

Definition at line 115 of file helper.cpp.

◆ odd_primes_table_by_index()

prime_type sigmaodd::odd_primes_table_by_index ( unsigned int i )

inline

Return the (i + 1)th odd prime number from the precalculated table.

Parameters

i	0 <= i < odd_primes_table_nb()

Returns: the item of index i of the odd primes table

Definition at line 50 of file primes__inline.hpp.

◆ odd_primes_table_last()

prime_type sigmaodd::odd_primes_table_last ( )

inline

Return the last odd prime number in the precalculated table.

Definition at line 59 of file primes__inline.hpp.

◆ odd_primes_table_nb()

constexpr unsigned int sigmaodd::odd_primes_table_nb ( )

Return the number of odd prime numbers in the precalculated table.

Definition at line 20 of file primes__inline.hpp.

◆ odd_primes_table_ptr()

const prime_type * sigmaodd::odd_primes_table_ptr ( )

inline

Return a pointer to the first number in the precalculated table.

Definition at line 66 of file primes__inline.hpp.

◆ operator<<()

std::ostream & sigmaodd::operator<<	(	std::ostream &	out,
		const FactorExp &	factor_exp
	)

Return "factor^exponent" representation of factor_exp.

Definition at line 148 of file divisors.cpp.

◆ path_to_string()

std::string sigmaodd::path_to_string ( const std::vector< nat_type > & path )

Return a string representation of the path. All numbers are separated by the corresponding <, = or > symbol.

Definition at line 193 of file sigmaodd.cpp.

◆ pentagonal()

constexpr nat_type sigmaodd::pentagonal ( nat_type n )

Return the pentagonal number of n.

https://oeis.org/A000326

Returns: (3n - 1)n / 2

Definition at line 22 of file pentagonal__inline.hpp.

◆ pentagonal_neg()

constexpr nat_type sigmaodd::pentagonal_neg ( nat_type n )

Return the generalized pentagonal number of -n.

https://oeis.org/A005449

Returns: (3n + 1)n / 2

Definition at line 31 of file pentagonal__inline.hpp.

◆ percent_()

double sigmaodd::percent_	(	nat_type	n,
		nat_type	d
	)

Definition at line 86 of file sigmaodd.cpp.

◆ pollard_rho() [1/2]

nat_type sigmaodd::pollard_rho ( nat_type n )

Return pollard_rho(n, rand() % n, floor square root of n).

Parameters

n != 0

Definition at line 292 of file divisors.cpp.

◆ pollard_rho() [2/2]

nat_type sigmaodd::pollard_rho	(	nat_type	n,
		nat_type	random,
		nat_type	max_iteration
	)

Heuristic to find a proper divisor of n with the Pollard's rho heuristic.

random is the "random" number used by the heuristic and max_iteration the maximum number of iterations to find the divisor.

If a divisor is find then return it, else return 0.

Parameters

n	!= 0
random	< n
max_iteration

Returns: 0 or 1 < (divisor of n) < n

Definition at line 300 of file divisors.cpp.

◆ pollard_rho_repeat()

nat_type sigmaodd::pollard_rho_repeat	(	nat_type	n,
		nat_type	nb_tries
	)

Try pollard_rho(n) a maximum of nb_tries times and return 0 or the first divisor find.

Parameters

n	!= 0
nb_tries

Returns: 0 or 1 < (divisor of n) < n

Definition at line 341 of file divisors.cpp.

◆ pow_nat()

constexpr nat_type sigmaodd::pow_nat	(	nat_type	n,
		unsigned int	k
	)

Return x^k, x power k.

Definition at line 39 of file helper__inline.hpp.

◆ print_arrow_()

void sigmaodd::print_arrow_	(	nat_type	from,
		nat_type	to,
		unsigned int	length,
		bool	circular
	)

Definition at line 34 of file dot.cpp.

◆ print_data_()

void sigmaodd::print_data_	(	nat_type	n,
		nat_type	result,
		unsigned int	length,
		bool	print_only_longer,
		bool	print_path
	)

Definition at line 94 of file sigmaodd.cpp.

◆ print_lengths_()

void sigmaodd::print_lengths_ ( nat_type lengths[] )

Definition at line 118 of file sigmaodd.cpp.

◆ print_long()

void sigmaodd::print_long	(	nat_type	first,
		nat_type	last,
		bool	print_path
	)

Iterate from first to last (included) and for each odd n not square such that is_little_mersenne_prime_unitary_divide(n) is false, if varsum_odd(n) > n then print n and varsum_odd(n).

If varsum_odd(n) is not divisible by 3, 5, 7 or 9 then after n print '!' follow by this number.

If varsum_odd(n) is a perfect square then after varsum_odd(n) print '#'.

Parameters

first	odd >= 3
last
print_path

Definition at line 213 of file sigmaodd.cpp.

◆ print_path() [1/2]

void sigmaodd::print_path	(	const std::vector< nat_type > &	path,
		std::ostream &	out = `std::cout`
	)

Send to the stream a string representation of the path. All numbers are separated by the corresponding <, = or > symbol.

Parameters

path	must be a correct complete path from a number n to the number 1
out

Definition at line 251 of file sigmaodd.cpp.

◆ print_path() [2/2]

void sigmaodd::print_path	(	const std::vector< nat_type >::const_iterator &	path_begin,
		const std::vector< nat_type >::const_iterator &	path_end,
		std::ostream &	out = `std::cout`
	)

Send to the stream a string representation of the path, from path_begin to path_end (included). All numbers are separated by the corresponding <, = or > symbol.

Parameters

path_begin	with path_end must be a correct piece of a correct path
path_end
out

Definition at line 260 of file sigmaodd.cpp.

◆ print_path_()

void sigmaodd::print_path_ ( nat_type n )

Definition at line 140 of file sigmaodd.cpp.

◆ print_path_infos()

void sigmaodd::print_path_infos	(	const std::vector< nat_type > &	path,
		bool	print_bad = `true`,
		bool	print_all = `false`,
		bool	print_category = `true`,
		bool	print_lower = `true`,
		bool	print_length = `true`,
		bool	print_path = `true`,
		std::ostream &	out = `std::cout`
	)

Send (if the below condition is true) to the stream a string representation of the path with some information depending of the boolean parameters.

Print only if print_all or if print_bad and the path start from a bad number (i.e. odd and not perfect square and partial length > 1).

List of information (maybe) printed, separated by tabulations:

n
Category of n ('E': even, 'F': fixed point, 'S': odd perfect square, 'B': bad number or 'G': gentle number)
First number < n
Length of the partial path
Partial path (beginning of the path, until the first number < n, included)
Length of the path
Path

If n is a bad number but is not divisible by 9 then print " *" after n.

If length > n then print a " *" after the partial length.

If the partial path is the complete path then do not repeat the length and the path.

Parameters

path	must be a correct complete path from a number n to the number 1 or a correct partial path from a number to the first number < n
print_bad
print_all
print_category
print_lower
print_length
print_path
out

Definition at line 279 of file sigmaodd.cpp.

◆ print_sigmaodd__factorize()

void sigmaodd::print_sigmaodd__factorize	(	nat_type	first,
		nat_type	last,
		bool	print_only_longer,
		bool	print_path
	)

Iterate from first to last (included) and print result of the sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize(n) with some informations.

If print_only_longer then for each n print only the longer found.

If print_path then for each n print also the complete path (recalculate by iteration of sum_odd_divisors_divided_until_odd__factorize(n)).

Parameters

first	odd >= 3
last
print_only_longer
print_path

Definition at line 357 of file sigmaodd.cpp.

◆ print_sigmaodd__factorize_bound()

void sigmaodd::print_sigmaodd__factorize_bound	(	nat_type	first,
		nat_type	last,
		bool	print_only_longer,
		bool	print_path
	)

Iterate from first to last (included) and print result of the sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize_bound(n) with some informations.

If print_only_longer then for each n print only the longer found.

If print_path then for each n print also the complete path (recalculate by iteration of sum_odd_divisors_divided_until_odd__factorize(n)).

Parameters

first	odd >= 3
last
print_only_longer
print_path

Definition at line 382 of file sigmaodd.cpp.

◆ print_sigmaodd__naive()

void sigmaodd::print_sigmaodd__naive	(	nat_type	first,
		nat_type	last,
		bool	print_only_longer,
		bool	print_path
	)

Iterate from first to last (included) and print result of the sum_odd_divisors_divided_until_odd_iterate_until_lower__naive(n) with some informations.

If print_only_longer then for each n print only the longer found.

If print_path then for each n print also the complete path (recalculate by iteration of sum_odd_divisors_divided_until_odd__factorize(n)).

Parameters

first	odd >= 3
last
print_only_longer
print_path

Definition at line 407 of file sigmaodd.cpp.

◆ print_square()

void sigmaodd::print_square	(	nat_type	first,
		nat_type	last,
		bool	print_path
	)

Definition at line 432 of file sigmaodd.cpp.

◆ print_varsigmaodd_dot()

void sigmaodd::print_varsigmaodd_dot	(	nat_type	first,
		nat_type	last,
		bool	show_node = `true`,
		bool	shortcut = `false`,
		bool	circular = `false`
	)

Print to std::cout in a DOT format, a graph of path of the sigma odd problem.

If show_node then plot nodes with number, else plot only points.

If shortcut then do not print bigger step, else print complete path until 1.

If circular then plot circular graph, else plot tree graph.

See https://en.wikipedia.org/wiki/DOT_(graph_description_language)

Parameters

first	odd
last
show_node
shortcut
circular

Definition at line 76 of file dot.cpp.

◆ read_primes_table()

bool sigmaodd::read_primes_table ( )

Read the binary file prime_filename to fill the table with all primes < 2^28. This table must be read from the binary file big_data/prime28.bin.

If prime_filename is not available in the same directory then search it in parents directories.

If the macro PRIME16 is defined the this function do nothing.

Returns: true iff the file was completely loaded

Definition at line 241 of file primes.cpp.

◆ square() [1/2]

constexpr double sigmaodd::square ( double x )

Return x*x.

Definition at line 59 of file helper__inline.hpp.

◆ square() [2/2]

constexpr nat_type sigmaodd::square ( nat_type n )

Return n*n.

Definition at line 66 of file helper__inline.hpp.

◆ sum_divisors__euler()

nat_type sigmaodd::sum_divisors__euler ( nat_type n )

Calculates the sum of all divisors of n with the Euler formula about pentagonal numbers and returns it.

Parameters

n != 0

Returns: the sum of all divisors of n

Definition at line 70 of file pentagonal.cpp.

◆ sum_divisorseulertable_()

std::vector<nat_type> sigmaodd::sum_divisors__euler__table_ ( sum_divisors__euler__table_nb_ )

◆ sum_divisors__euler_cache_is_full()

bool sigmaodd::sum_divisors__euler_cache_is_full ( )

Return true iff the cache used by sum_divisors__euler() is full. The function can clean space, but it is less efficient.

Definition at line 152 of file pentagonal.cpp.

◆ sum_divisors__euler_cache_nb()

std::size_t sigmaodd::sum_divisors__euler_cache_nb ( )

Return the current number of items in the cache used by sum_divisors__euler()

Definition at line 158 of file pentagonal.cpp.

◆ sum_divisors__euler_table_nb()

std::size_t sigmaodd::sum_divisors__euler_table_nb ( )

Return the (constant) number of items in the table used by sum_divisors__euler()

Definition at line 164 of file pentagonal.cpp.

◆ sum_divisors__factorize()

nat_type sigmaodd::sum_divisors__factorize ( nat_type n )

Calculates the sum of all divisors of n by the factorization method and returns it.

Parameters

n != 0

Returns: the sum of all divisors of n

Definition at line 357 of file divisors.cpp.

◆ sum_divisors__naive()

nat_type sigmaodd::sum_divisors__naive ( nat_type n )

Calculates the sum of all divisors of n by the naive method and returns it.

Parameters

n != 0

Returns: the sum of all divisors of n

Definition at line 422 of file divisors.cpp.

◆ sum_divisors_diff_()

nat_type sigmaodd::sum_divisors_diff_	(	nat_type	n,
		nat_type	pi
	)

Definition at line 55 of file pentagonal.cpp.

◆ sum_even()

constexpr nat_type sigmaodd::sum_even ( nat_type n )

Return 2 + 4 + 6 + 8 + ... + (n or n-1) = k(k + 1) with k = floor(n/2).

https://oeis.org/A110660

Returns: 2 + 4 + 6 + 8 + ... + (n or n-1)

Definition at line 73 of file helper__inline.hpp.

◆ sum_floor_n_harmonic_odd()

nat_type sigmaodd::sum_floor_n_harmonic_odd	(	nat_type	n,
		nat_type	to_n
	)

Return floor(n/1) + floor(n/3) + floor(n/5) + floor(n/7) + ... + (n/to_n or floor(1/(to_n-1))).

Definition at line 153 of file harmonic.cpp.

◆ sum_geometric_progression()

constexpr nat_type sigmaodd::sum_geometric_progression	(	nat_type	r,
		unsigned int	k
	)

Return the sum of the (k + 1) terms of the geometric progression of the common ratio r.

If r is prime then the result is equal to the sum of the divisors of r.

In fact calculates (r^k - 1) / (r - 1) + r^k to avoid some overflow.

Returns: 1 + r + r^2 + r^3 + ... + r^k = (r^(k + 1) - 1) / (r - 1)

Definition at line 84 of file helper__inline.hpp.

◆ sum_geometric_progression_strict()

constexpr nat_type sigmaodd::sum_geometric_progression_strict	(	nat_type	r,
		unsigned int	k
	)

Return sum_geometric_progression(r, k) but only for r > 1.

In fact calculates (r^k - 1) / (r - 1) + r^k to avoid some overflow.

Parameters

r	> 1
k

Returns: 1 + r + r^2 + r^3 + ... + r^k = (r^(k + 1) - 1) / (r - 1)

Definition at line 95 of file helper__inline.hpp.

◆ sum_natural()

constexpr nat_type sigmaodd::sum_natural ( nat_type n )

Return 1 + 2 + 3 + 4 + ... + n = n(n + 1)/2.

https://oeis.org/A000217

Returns: 1 + 2 + 3 + 4 + ... + n

Definition at line 108 of file helper__inline.hpp.

◆ sum_odd()

constexpr nat_type sigmaodd::sum_odd ( nat_type n )

Return 1 + 3 + 5 + 7 + ... + (n or n-1) = k^2 with k floor((n+1)/2).

sum_odd(n - 1) = https://oeis.org/A008794

Returns: 1 + 3 + 5 + 7 + ... + (n or n-1)

Definition at line 120 of file helper__inline.hpp.

◆ sum_odd_divisors__factorize()

nat_type sigmaodd::sum_odd_divisors__factorize ( nat_type n )

Calculates the sum of odd divisors of n by the factorization method and returns it.

https://oeis.org/A000593

Parameters

n != 0

Returns: the sum of all odd divisors of n

Definition at line 444 of file divisors.cpp.

◆ sum_odd_divisors__naive()

nat_type sigmaodd::sum_odd_divisors__naive ( nat_type n )

Calculates the sum of odd divisors of n by the naive method and returns it.

Parameters

n != 0

Returns: the sum of all odd divisors of n

Definition at line 507 of file divisors.cpp.

◆ sum_odd_divisors_divided_until_odd__euler()

nat_type sigmaodd::sum_odd_divisors_divided_until_odd__euler ( nat_type n )

Calculates the sum of all odd divisors of n by the Euler formula method, divides the results by 2 until becomes odd, and returns it.

Parameters

n != 0

Returns: the sum of all odd divisors of n

Definition at line 468 of file sigmaodd.cpp.

◆ sum_odd_divisors_divided_until_odd__factorize()

nat_type sigmaodd::sum_odd_divisors_divided_until_odd__factorize	(	nat_type	n,
		bool	skip_primes_table = `false`
	)

Calculates the sum of all odd divisors of n by the factorization method, divides the results by 2 until becomes odd, and returns it.

If skip_primes_table then n must not be divisible by prime number in the primes precalculated table.

Parameters

n	!= 0
skip_primes_table

Returns: the sum of all odd divisors of n

Definition at line 476 of file sigmaodd.cpp.

◆ sum_odd_divisors_divided_until_odd__factorize_bound()

nat_type sigmaodd::sum_odd_divisors_divided_until_odd__factorize_bound	(	nat_type	n,
		nat_type	start_n
	)

Calculates the sum of all odd divisors of n by the factorization method, divides the results by 2 until becomes odd, and returns it. ??? with bound.

Parameters

n	!= 0
start_n

Returns: the sum of all odd divisors of n

Definition at line 565 of file sigmaodd.cpp.

◆ sum_odd_divisors_divided_until_odd__naive()

nat_type sigmaodd::sum_odd_divisors_divided_until_odd__naive ( nat_type n )

Calculates the sum of all odd divisors of n by the naive method, divides the results by 2 until becomes odd, and returns it.

Parameters

n != 0

Returns: the sum of all odd divisors of n

Definition at line 685 of file sigmaodd.cpp.

◆ sum_odd_divisors_divided_until_odd_iterate_until_lower__euler()

std::pair< nat_type, unsigned int > sigmaodd::sum_odd_divisors_divided_until_odd_iterate_until_lower__euler ( nat_type n )

Iterates the sum_odd_divisors_divided_until_odd__euler() function from n until have a result lower than n.

Parameters

n > 1

Definition at line 693 of file sigmaodd.cpp.

◆ sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize()

std::pair< nat_type, unsigned int > sigmaodd::sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize ( nat_type n )

Iterates the sum_odd_divisors_divided_until_odd__factorize() function from n until have a result lower than n.

Parameters

n > 1

Definition at line 712 of file sigmaodd.cpp.

◆ sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize_bound()

std::pair< nat_type, unsigned int > sigmaodd::sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize_bound ( nat_type n )

Iterates the sum_odd_divisors_divided_until_odd__factorize() function from n until have a result lower than n. ??? with bound.

Parameters

n > 1

Definition at line 731 of file sigmaodd.cpp.

◆ sum_odd_divisors_divided_until_odd_iterate_until_lower__naive()

std::pair< nat_type, unsigned int > sigmaodd::sum_odd_divisors_divided_until_odd_iterate_until_lower__naive ( nat_type n )

Iterates the sum_odd_divisors_divided_until_odd__naive() function from n until have a result lower than n.

Parameters

n > 1

Definition at line 750 of file sigmaodd.cpp.

◆ sum_odd_divisors_upper_bound()

nat_type sigmaodd::sum_odd_divisors_upper_bound ( nat_type n )

Return an upper bound of sum odd divisors.

Parameters

n != 0

Definition at line 531 of file divisors.cpp.

◆ sum_odd_divisors_upper_bound__DeTemple() [1/2]

nat_type sigmaodd::sum_odd_divisors_upper_bound__DeTemple ( nat_type n )

Return an upper bound of sum odd divisors of n using the DeTemple inequalities.

Parameters

n != 0

Definition at line 602 of file divisors.cpp.

◆ sum_odd_divisors_upper_bound__DeTemple() [2/2]

nat_type sigmaodd::sum_odd_divisors_upper_bound__DeTemple	(	nat_type	n,
		nat_type	k
	)

Return an upper bound of sum odd divisors of n using the DeTemple inequalities and the knowledge that n have no divisors <= k.

Parameters

n	!= 0
k	odd <= sqrt(n)

Definition at line 666 of file divisors.cpp.

◆ sum_odd_divisors_upper_bound__DeTemple_ceil()

nat_type sigmaodd::sum_odd_divisors_upper_bound__DeTemple_ceil ( nat_type n )

Return an upper bound of sum odd divisors of n using the DeTemple inequalities. ???

Parameters

n != 0

Definition at line 635 of file divisors.cpp.

◆ varsum_odd()

nat_type sigmaodd::varsum_odd ( nat_type n )

Calculates the sum of all odd divisors of n by the factorization method, divides the results by 2 until becomes odd, and returns it. ???

Parameters

n odd

Returns: the sum of all odd divisors of n

Definition at line 769 of file sigmaodd.cpp.

◆ varsum_odd_big()

nat_type sigmaodd::varsum_odd_big	(	nat_type	n,
		nat_type	sqrt_n
	)

Calculates the sum of all odd divisors of n by the factorization method, divides the results by 2 until becomes odd, and returns it. ???

Parameters

n	odd >= potential_prime_offsets_table_modulo()
sqrt_n	???

Returns: the sum of all odd divisors of n

Definition at line 801 of file sigmaodd.cpp.

Variable Documentation

◆ alpha

const double sigmaodd::alpha = 0.425

Definition at line 24 of file harmonic.cpp.

◆ alpha_bis

const double sigmaodd::alpha_bis = 0.7

Definition at line 25 of file harmonic.cpp.

◆ array_odd_primes_

prime_type * sigmaodd::array_odd_primes_ = nullptr

Array of all odd prime numbers < 2^28 with a final 0. (Or < 2^16 if the macro PRIME16 is defined.)

Definition at line 48 of file primes.cpp.

◆ array_odd_primes_nb_

constexpr unsigned int sigmaodd::array_odd_primes_nb_ = 14630843u - 1

Number of odd prime numbers in the table array_odd_primes_.

https://primes.utm.edu/nthprime/ 14630841th prime (with 2): 268435361 14630842th prime (with 2): 268435367 14630843th prime (with 2): 268435399 < 2^28 14630844th prime (with 2): 268435459 > 2^28

Definition at line 85 of file primes.hpp.

◆ beta

const double sigmaodd::beta = 0.40580406331047491619301581522449851

Definition at line 26 of file harmonic.cpp.

◆ euler_gamma

const double sigmaodd::euler_gamma = 0.577215664901532860606512090082402431042

The Euler-Mascheroni constant 0.577215664901532860606512090082402431042... (rounded to an upper bound in double) http://mathworld.wolfram.com/Euler-MascheroniConstant.html.

Definition at line 34 of file harmonic.cpp.

◆ MAX_POSSIBLE_N

constexpr nat_type sigmaodd::MAX_POSSIBLE_N = (static_cast<nat_type>(1) << 56) - 1

Lower bound of the bigger number such that it is possible to compute the result of the sigma function.

Definition at line 54 of file helper.hpp.

◆ prime_filename

const std::string sigmaodd::prime_filename = "big_data/prime28.bin"

Default filename for the binary file "big_data/prime28.bin".

Definition at line 35 of file primes.cpp.

◆ sum_divisorseulercache_

std::map<nat_type, nat_type> sigmaodd::sum_divisors__euler__cache_

Definition at line 36 of file pentagonal.cpp.

◆ sum_divisorseulercache_max_nb_

size_t sigmaodd::sum_divisors__euler__cache_max_nb_ = 20000

Definition at line 27 of file pentagonal.cpp.

◆ sum_divisorseulertable_nb_

size_t sigmaodd::sum_divisors__euler__table_nb_ = 1024*64

Definition at line 29 of file pentagonal.cpp.

Classes

Typedefs

Functions

Variables

Detailed Description

Typedef Documentation

◆ nat_type

◆ prime_type

◆ tmp_uint128_type

Function Documentation

◆ ceil_eighth_root()

◆ ceil_fourth_root()

◆ ceil_square_root()

◆ ceilx_fourth_root()

◆ check_varsigma_odd()

◆ coprime_factor_exps()

◆ coprime_factors_()

◆ diff_half_harmonic_upper_bound() [1/2]

◆ diff_half_harmonic_upper_bound() [2/2]

◆ diff_harmonic_upper_bound()

◆ divide_until_nb()

◆ divide_until_odd()

◆ divide_until_odd_nb()

◆ exit_if_found_exception_()

◆ exit_if_impossible_to_check_()

◆ factorization_to_n()

◆ factorization_to_nu()

◆ factorization_to_nu_odd()

◆ factorization_to_sigma()

◆ factorization_to_sigma_odd()

◆ factorize()

◆ first_divisor()

◆ floor_eighth_root()

◆ floor_fourth_root()

◆ floor_square_root()

◆ gcd()

◆ harmonic()

◆ harmonic_even()

◆ harmonic_lower_bound()

◆ harmonic_odd()

◆ harmonic_upper_bound()

◆ is_coprime()

◆ is_divide()

◆ is_even()

◆ is_first_mersenne_prime_unitary_divide()

◆ is_first_mersenne_prime_unitary_divide_or_square()

◆ is_little_mersenne_prime_unitary_divide()

◆ is_mersenne_prime_unitary_divide()

◆ is_odd()

◆ is_prime()

◆ is_prime_in_odd_primes_table()

◆ is_square()

◆ is_unitary_divide()

◆ load_bad_table()

◆ load_numbers()

◆ odd_primes_table_by_index()

◆ odd_primes_table_last()

◆ odd_primes_table_nb()

◆ odd_primes_table_ptr()

◆ operator<<()

◆ path_to_string()

◆ pentagonal()

◆ pentagonal_neg()

◆ percent_()

◆ pollard_rho() [1/2]

◆ pollard_rho() [2/2]

◆ pollard_rho_repeat()

◆ pow_nat()

◆ print_arrow_()

◆ print_data_()

◆ print_lengths_()

◆ print_long()

◆ print_path() [1/2]

◆ print_path() [2/2]

◆ print_path_()

◆ print_path_infos()

◆ print_sigmaodd__factorize()

◆ print_sigmaodd__factorize_bound()

◆ print_sigmaodd__naive()

◆ print_square()

◆ sum_divisorseulertable_()

◆ sum_divisorseulercache_

◆ sum_divisorseulercache_max_nb_

◆ sum_divisorseulertable_nb_