Find the Aliquot Sum of n.

An Aliquot Sum of an integer n is the sum of the proper divisors (all divisors except n) of n.

Examples

iex> Math.aliquot_sum(1)
0

iex> Math.aliquot_sum(10)
8

iex> Math.aliquot_sum(48)
76

Calculate Ω(n) - number of distinct prime factors, with multiplicity.

See also omega/1 - number of distinct prime factors.

Examples

iex> Math.bigomega(3)
1

iex> Math.bigomega(15)
2

iex> Math.bigomega(25)
2

iex> Math.bigomega(99960)
8

Factorize an integer into all divisors.

This will find all divisors, prime and composite, of an integer. The algorithm used for factorization is not optimal for very large numbers, as it uses a multiple pass calculation for co-factors and composite factors.

Example

iex> Math.factors(2)
[1, 2]

iex> Math.factors(84)
[1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84]

iex> Math.factors(123456)
[1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 192, 643, 1286, 1929, 2572, 3858, 5144, 7716, 10288, 15432, 20576, 30864, 41152, 61728, 123456]

Find the gpf(n) or greatest prime factor.

Examples

iex> Math.greatest_prime_factor(1)
1

iex> Math.greatest_prime_factor(39)
13

iex> Math.greatest_prime_factor(99973)
389

Check if an integer n is 11-smooth.

See is_b_smooth?/2 for more details.

Examples

iex> Math.is_11_smooth?(3)
true

iex> Math.is_11_smooth?(40)
true

iex> Math.is_11_smooth?(107)
false

iex> Math.is_11_smooth?(2020)
false

Check if an integer n is 13-smooth.

See is_b_smooth?/2 for more details.

Examples

iex> Math.is_13_smooth?(3)
true

iex> Math.is_13_smooth?(40)
true

iex> Math.is_13_smooth?(107)
false

iex> Math.is_13_smooth?(2020)
false

Check if an integer n is 17-smooth.

See is_b_smooth?/2 for more details.

Examples

iex> Math.is_17_smooth?(3)
true

iex> Math.is_17_smooth?(40)
true

iex> Math.is_17_smooth?(107)
false

iex> Math.is_17_smooth?(2020)
false

Check if an integer n is 19-smooth.

See is_b_smooth?/2 for more details.

Examples

iex> Math.is_19_smooth?(3)
true

iex> Math.is_19_smooth?(40)
true

iex> Math.is_19_smooth?(107)
false

iex> Math.is_19_smooth?(2020)
false

Check if an integer n is 23-smooth.

See is_b_smooth?/2 for more details.

Examples

iex> Math.is_23_smooth?(3)
true

iex> Math.is_23_smooth?(40)
true

iex> Math.is_23_smooth?(107)
false

iex> Math.is_23_smooth?(2020)
false

Check if an integer n is 3-smooth.

See is_b_smooth?/2 for more details.

Examples

iex> Math.is_3_smooth?(3)
true

iex> Math.is_3_smooth?(40)
false

iex> Math.is_3_smooth?(107)
false

iex> Math.is_3_smooth?(2020)
false

Check if an integer n is 5-smooth.

See is_b_smooth?/2 for more details.

Examples

iex> Math.is_5_smooth?(3)
true

iex> Math.is_5_smooth?(40)
true

iex> Math.is_5_smooth?(107)
false

iex> Math.is_5_smooth?(2020)
false

Check if an integer n is 7-smooth.

See is_b_smooth?/2 for more details.

Examples

iex> Math.is_7_smooth?(3)
true

iex> Math.is_7_smooth?(40)
true

iex> Math.is_7_smooth?(107)
false

iex> Math.is_7_smooth?(2020)
false

Determine if an integer is abundant.

An abundant number is an integer n, such that the sum of all proper divisors of n (including itself) is greater than 2 * n.

Alternatively, an abundant number is a number that satisfies: 𝜎(n) > 2n

See also; is_deficient?/1, is_perfect?/1, is_highly_abundant?/1, next_abundant/1.

Examples

iex> Math.is_abundant?(3)
false

iex> Math.is_abundant?(12)
true

iex> Math.is_abundant?(945)
true

Check if a number is an Achilles Number.

Achilles numbers are n that are powerful (see is_powerful_number?/1 but not perfect powers (see is_perfect_power?/1).

See Chunky.Sequence.OEIS.Factor, sequence A052486.

Examples

iex> Math.is_achilles_number?(70)
false

iex> Math.is_achilles_number?(72)
true

iex> Math.is_achilles_number?(2700)
true

iex> Math.is_achilles_number?(784)
false

Determine if an integer is an arithmetic number.

An arithmetic number n such that the average of the sum of the proper divisors of n is a whole integer. Alternatively, n that satisfy 𝜎(n) / 𝜏(n) == 0.

Examples

iex> Math.is_arithmetic_number?(11)
true

iex> Math.is_arithmetic_number?(32)
false

iex> Math.is_arithmetic_number?(12953)
true

Determine if an integer n is b-smooth, a composite of prime factors less than or equal to b.

Numbers can be b-smooth for any b that is prime. For instance, the number 8 is 3-smooth, as it's factors would be: 1^1 * 2^3 * 3^0, whereas 15 is not 3-smooth, as it's factors would be 1^1 * 2^0 * 3^1 * 5^1 - it has prime factors whose value is greater than 3.

Shortcut Functions

There are a collection of pre-defined predicate functions for checking b-smooth for the primes 3 to 23:

- [`is_3_smooth?/1`](#is_3_smooth?/1)
- [`is_5_smooth?/1`](#is_5_smooth?/1)
- [`is_7_smooth?/1`](#is_7_smooth?/1)
- [`is_11_smooth?/1`](#is_11_smooth?/1)
- [`is_13_smooth?/1`](#is_13_smooth?/1)
- [`is_17_smooth?/1`](#is_17_smooth?/1)
- [`is_19_smooth?/1`](#is_19_smooth?/1)
- [`is_23_smooth?/1`](#is_23_smooth?/1)

Examples

iex> Math.is_b_smooth?(1944, 3)
true

iex> Math.is_b_smooth?(101, 5)
false

iex> Math.is_b_smooth?(705, 47)
true

Determine if two numbers, a and b, are co-prime.

From Wikipedia:

In number theory, two integers a and b are said to be relatively prime, mutually prime,[1] or coprime (also written co-prime) if the only positive integer (factor) that divides both of them is 1

Examples

iex> Math.is_coprime?(14, 15)
true

iex> Math.is_coprime?(14, 21)
false

iex> Math.is_coprime?(17, 2048)
true

Check if an integer n has no factors greater than 1 that are perfect cubes.

Examples

iex> Math.is_cubefree?(3)
true

iex> Math.is_cubefree?(64)
false

iex> Math.is_cubefree?(2744)
false

Determine if an integer is deficient.

A deficient number is an integer n, such that the sum of all proper divisors of n (including itself) is less than 2 * n.

Alternatively, a deficient number is a number that satisfies: 𝜎(n) < 2n

See also; is_abundant?/1, is_highly_abundant?/1, is_perfect?/1, next_deficient/1.

Examples

iex> Math.is_deficient?(1)
true

iex> Math.is_deficient?(71)
true

iex> Math.is_deficient?(33550336)
false

iex> Math.is_deficient?(60)
false

Check if a number n is highly abundant.

A number n is highly abundant when the sum of the proper factors of n is greater than the sum of the proper factors of any number m that is in 0 < m < n.

Alternatively, for all natural numbers, m < n ; 𝜎(m) < 𝜎(n).

See also; is_deficient?/1, is_perfect?/1, is_abundant?/1.

Examples

iex> Math.is_highly_abundant?(1)
true

iex> Math.is_highly_abundant?(5)
false

iex> Math.is_highly_abundant?(30)
true

iex> Math.is_highly_abundant?(2099)
false

iex> Math.is_highly_abundant?(2100)
true

Check if a number n is a highly powerful number.

Highly powerful numbers are similar in concept to highly abundant numbers. For highly powerful numbers, the product of the exponents of prime factors of the number n need to be greater than the same property for any number m, such that 0 < m < n.

If you need a sequence of highly powerful numbers, use the A005934 sequence in Chunky.Sequence.OEIS.Factors, which uses an max/compare method for building the sequence, which is vastly more efficient than repeated calls to is_highly_powerful_number?/1.

See also is_powerful_number?/1, and Highly powerful number.

Examples

iex> Math.is_highly_powerful_number?(4)
true

iex> Math.is_highly_powerful_number?(256)
false

iex> Math.is_highly_powerful_number?(62208)
true

Determine if an integer is a perfect number.

A perfect integer is an n where the sum of the proper divisors of n is equal to n. Alternatively, an n that satisfies 𝜎(n) == 2n.

See also; is_abundant?/1, is_highly_abundant?/1, is_deficient?/1.

Examples

iex> Math.is_perfect?(5)
false

iex> Math.is_perfect?(6)
true

iex> Math.is_perfect?(20)
false

iex> Math.is_perfect?(33550336)
true

Check if n is a perfect cube.

Perfect cubes are n such that there exists an m where m * m * m == n or m^3 == n.

Examples

iex> Math.is_perfect_cube?(6)
false

iex> Math.is_perfect_cube?(8000)
true

iex> Math.is_perfect_cube?(1879080904)
true

Check if n is a perfect power.

Perfect powers are n where positive integers m and k exist, such that m^k == n.

Examples

iex> Math.is_perfect_power?(4)
true

iex> Math.is_perfect_power?(100)
true

iex> Math.is_perfect_power?(226)
false

Check if n is a perfect square.

Perfect squares are n such that there exists an m where m * m == n.

Examples

iex> Math.is_perfect_square?(3)
false

iex> Math.is_perfect_square?(25)
true

iex> Math.is_perfect_square?(123456)
false

Check if n is a power of m.

This is partially the inverse of is_root_of?/2.

Examples

iex> Math.is_power_of?(8, 2)
true

iex> Math.is_power_of?(243, 3)
true

iex> Math.is_power_of?(9, 2)
false

iex> Math.is_power_of?(2, 2)
true

iex> Math.is_power_of?(1, 17)
true

Determine if an integer n is a powerful number.

A powerful number is an integer n such that for all prime factors m of n, m^2 also evenly divides n. Alternatively, a powerful number n can be written as n = a^2 * b^3 for positive integers a and b; n is the product of a square and a cube.

Examples

iex> Math.is_powerful_number?(8)
true

iex> Math.is_powerful_number?(10)
false

iex> Math.is_powerful_number?(800)
true

iex> Math.is_powerful_number?(970)
false

Determine if a positive integer is prime.

This function uses a Miller-Rabin primality test, with 40 iterations.

Examples

iex> Math.is_prime?(13)
true

iex> Math.is_prime?(233*444*727*456)
false

iex> Math.is_prime?(30762542250301270692051460539586166927291732754961)
true

Check if n is any k-th root of m, where k > 2.

This function uses a repeated multiplication method to test if n has any power k such that n^k == m.

Examples

iex> Math.is_root_of?(2, 8)
true

iex> Math.is_root_of?(2, 2048)
true

iex> Math.is_root_of?(7, 16807)
true

iex> Math.is_root_of?(5, 16808)
false

Check if n is a sphenic number, the product of three distinct primes.

Example

iex> Math.is_sphenic_number?(4)
false

iex> Math.is_sphenic_number?(66)
true

iex> Math.is_sphenic_number?(51339)
true

Check if an integer n has no factors greater than 1 that are perfect squares.

Examples

iex> Math.is_squarefree?(3)
true

iex> Math.is_squarefree?(8)
false

iex> Math.is_squarefree?(99935)
true

Jordan totient function Jk(n).

The Jordan totient is a generalized form of the Euler totient function, where J1(n) = Φ(n). The Jordan totient is a positive integer m of k-tuples that are co-prime to n.

Calculating the totient is a semi-closed form of a Dirichlet series/Euler product, and is dependent on the size of n for factorization and k for exponentiation.

Examples

Finding J2(3):

  iex> Math.jordan_totient(3, 2)
  8

Finding J9(7):

  iex> Math.jordan_totient(7, 9)
  40353606

Finding J10(9999):

  iex> Math.jordan_totient(9999, 10)
  9989835316811664782653775044519099200000

Find the lpf(n) or least prime factor.

Examples

iex> Math.least_prime_factor(1)
1

iex> Math.least_prime_factor(39)
3

iex> Math.least_prime_factor(99973)
257

The classical Möbius function μ(n).

From Möbius Function on Wikipedia:

For any positive integer n, define μ(n) as the sum of the primitive nth roots of unity. It has values in {−1, 0, 1} depending on the factorization of n into prime factors:

• μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
• μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
• μ(n) = 0 if n has a squared prime factor.

Examples

iex> Math.mobius_function(1)
1

iex> Math.mobius_function(24)
0

iex> Math.mobius_function(99999)
0

Find the next abundant number after n.

See is_abundant?/1.

Examples

iex> Math.next_abundant(1)
12

iex> Math.next_abundant(12)
18

iex> Math.next_abundant(60)
66

iex> Math.next_abundant(264)
270

Find the next deficient number after n.

See is_deficient?/1.

Examples

iex> Math.next_deficient(0)
1

iex> Math.next_deficient(5)
7

iex> Math.next_deficient(41)
43

Apply a number theoretic property test to integers to find the next number in a sequence.

Examples

iex> Math.next_number(&Math.is_powerful_number?/1, 49)
64

iex> Math.next_number(&Math.is_abundant?/1, 60)
66

Calculate ω(n) - the number of distinct prime factors of n.

See also bigomega/1 - number of total prime factors of n.

Examples

iex> Math.omega(3)
1

iex> Math.omega(15)
2

iex> Math.omega(25)
1

iex> Math.omega(99960)
5

Integer exponentiation, x^y.

This function uses pure integer methods to bypass issues with floating point precision trucation in large values using the built-in :math exponentiation functions.

Example

iex> Math.pow(2, 10)
1024

iex> Math.pow(17, 14)
168377826559400929

Integer power/exponentiation in Modular Arithmetic.

Examples

iex> Math.pow(5, 3, 13)
8

iex> Math.pow(67930, 32319, 103969)
6582

Count the exponents of the prime factors of n.

This function counts the exponents on the prime factors of n, for example the number 2,025,000 can be factored to: [2, 2, 2, 3, 3, 3, 3, 5, 5, 5, 5, 5] or 2^3 * 3^4 * 5^5, hence the exponent of 2 is 3, the exponent of 3 is 4, and the exponent of 5 is 5.

As a simpler example, the prime factors of 49 are [7, 7], or 7^2, so the result of prime_factor_exponents(49) would be %{7 => 2}

Examples

iex> Math.prime_factor_exponents(2)
%{2 => 1}

iex> Math.prime_factor_exponents(8)
%{2 => 3}

iex> Math.prime_factor_exponents(2025000)
%{2 => 3, 3 => 4, 5 => 5}

iex> Math.prime_factor_exponents(49)
%{7 => 2}

Decompose an integer to prime factors.

This is not an exhaustive factorization, but a reduction to all prime factors for an integer.

Examples

iex> Math.prime_factors(12)
[1, 2, 2, 3]

iex> Math.prime_factors(101)
[1, 101]

iex> Math.prime_factors(79170)
[1, 2, 3, 5, 7, 13, 29]

iex> Math.prime_factors(233*444*727*456)
[1, 2, 2, 2, 2, 2, 3, 3, 19, 37, 233, 727]

Find the product of the exponents of the prime factors of n.

This function takes the prime factors of n, such as the factors of 8 = {1, 2, 2, 2}, groups the factors and to find the exponents, such as 8 = 1^1 * 2^3, and then finds the product of the exponents, like 1 * 3. Here the product of prime factorization exponents for 8 is 3.

The numbers generated by this function are related to the OEIS Sequence A005361, and the prodex function.

Examples

iex> Math.product_of_prime_factor_exponents(8)
3

iex> Math.product_of_prime_factor_exponents(100000)
25

Find the radical of an integer n.

Also called the square-free kernel, or written as rad(n), the radical of an integer is the product of the distinct primes of n.

Examples

iex> Math.radical(1)
1

iex> Math.radical(504)
42

iex> Math.radical(99960)
3570

Calculate the sigma-1 (or σ1(n)), also known as sum-of-divisors of an integer.

This is all of the divisors of n summed.

Example

iex> Math.sigma(70)
144

iex> Math.sigma(408)
1080

iex> Math.sigma(100000)
246078

Calculate a sigma function of an integer, for any p-th powers.

This is a generalized Sigma function of the form σp(n), so the Sigma-0 of a number σ0(n) would be sigma(n, 0), while the Sigma-4 (σ4(n)) would be sigma(n, 4).

For a faster version of σ1(n) (or the sum-of-divisors) see sigma/1.

Examples

iex> Math.sigma(12, 2)
210

iex> Math.sigma(19, 4)
130322

iex> Math.sigma(24, 0)
8

The tau (number of divisors) function.

Also written as 𝜏(n) or sigma(n, 0), this is a shortcut to sigma/2.

Examples

iex> Math.tau(9)
3

iex> Math.tau(34)
4

iex> Math.tau(50)
6

iex> Math.tau(3402)
24

Euler's totient function for n.

Also called phi or written as Φ(n), the Eulerian totient function counts the positive integers up to n that are relatively prime or coprime to n. The method used for calculating this function relies on a partially closed form of Euler's product formula that grows relative to the number of prime factors of n.

Examples

iex> Math.totient(36)
12

iex> Math.totient(101)
100

iex> Math.totient(99999)
64800