Count the number of Abelian groups of order n.

An Abelian group is a commutative group of elements in Abstract Algebra; this function counts the number of Abelian groups of a certain size.

This implementation of size counting for Abelian groups of order n is based on finding the number of partitions (see partition_count/1) of the exponents of the prime factors of n. For instance, when n is 144, the prime factorization is 2^4 * 3^2, with exponents 4 and 2. Finding the product of the partitions of the exponents via p(4) * p(2) yields 5 * 2, or 10.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000688/1 - Number of Abelian groups of order n

Examples

iex> Math.abelian_groups_count(1)
1

iex> Math.abelian_groups_count(9984)
22

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.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a001065/1 - Aliquot sum of n

Examples

iex> Math.aliquot_sum(1)
0

iex> Math.aliquot_sum(10)
8

iex> Math.aliquot_sum(48)
76

Calculate the Bell Number of n, or the number of possible partitions of a set of size n.

This function implementation relies on caching for efficiency.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000110/1 - Bell or exponential numbers

Examples

iex> Math.bell_number(3)
5

iex> Math.bell_number(10)
115975

iex> Math.bell_number(15)
1382958545

iex> Math.bell_number(35)
281600203019560266563340426570

Calculate the n-th Bernoulli number, and return it as a Fraction.

Bernoulli numbers are used throughout number theory for analysis, series construction, and topology. While the odd Bernoulli numbers greater than B_1 are technically 0, this function returns a zero value fraction (the reduced value 0/1).

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a027642/1 - Denominator of Bernoulli numbers

Examples

iex> Math.bernoulli_number(1)
%Fraction{num: 1, den: 2}

iex> Math.bernoulli_number(4)
%Fraction{num: -1, den: 30}

iex> Math.bernoulli_number(7)
%Fraction{num: 0, den: 1}

iex> Math.bernoulli_number(8)
%Fraction{num: -1, den: 30}

iex> Math.bernoulli_number(20)
%Fraction{num: -174611, den: 330}

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

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

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a001222/1 - Number of prime divisors of n counting multiplicity

Examples

iex> Math.bigomega(3)
1

iex> Math.bigomega(15)
2

iex> Math.bigomega(25)
2

iex> Math.bigomega(99960)
8

Find the number of ways to partition 2 * n into powers of 2.

As this function is highly recursive, and uses a recurrence relationship, it uses a cache for efficiency.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000123/1 - Number of binary partitions

Examples

iex> Math.binary_partitions_count(1)
2

iex> Math.binary_partitions_count(5)
14

iex> Math.binary_partitions_count(12)
94

iex> Math.binary_partitions_count(37)
3074

Calculate the binomial coefficient (n k).

The binomial coefficient function determines the coefficient on the x^k term in the polynomial expansion of (1 + x)^n.

Rather than run a full expansion, this function relies on the simple formula:

As the factorial/1 function in Chunky.Math uses a cached speed up strategy, the calculation of the binomial by this method is fairly efficient.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000984/1 - Central binomial coefficients

Examples

iex> Math.binomial(7, 3)
35

iex> Math.binomial(20, 3)
1140

iex> Math.binomial(20, 10)
184756

iex> Math.binomial(100, 50)
100891344545564193334812497256

Find the Catalan number of n, C(n).

In combinatorial math, the Catalan numbers occur in a wide range of counting problems.

Rather than the factorial or binomial expansion, this implementation uses a product over fractional parts to avoid recursion and precision loss.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000108/1 - Catalan Numbers
• Chunky.Sequence.OEIS.Combinatorics.create_sequence_a159981/1 - Catalan numbers read modulo 4
• Chunky.Sequence.OEIS.Combinatorics.create_sequence_a159984/1 - Catalan numbers read modulo 5
• Chunky.Sequence.OEIS.Combinatorics.create_sequence_a159986/1 - Catalan numbers read modulo 7
• Chunky.Sequence.OEIS.Combinatorics.create_sequence_a159987/1 - Catalan numbers read modulo 8
• Chunky.Sequence.OEIS.Combinatorics.create_sequence_a159988/1 - Catalan numbers read modulo 11
• Chunky.Sequence.OEIS.Combinatorics.create_sequence_a159989/1 - Catalan numbers read modulo 12
• Chunky.Sequence.OEIS.Combinatorics.create_sequence_a289682/1 - Catalan numbers read modulo 16

Examples

iex> Math.catalan_number(2)
2

iex> Math.catalan_number(20)
6564120420

iex> Math.catalan_number(100)
896519947090131496687170070074100632420837521538745909320

iex> Math.catalan_number(256)
1838728806050447178945542295919013188631170099776194095631629802153953581076132688111479765113051517392441367036708073775588228430597313880732554755142

Calculate Cayley's formula for n - the number of trees on n labeled vertices.

This formula also works for:

• number of spanning trees of a complete graph with labeled vertices
• number of transitive subtree acyclic digraphs on n-1 vertices
• counts parking functions
• the number of nilpotent partial bijections (of an n-element set)

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000272/1 - Number of trees on n labeled nodes

Examples

iex> Math.cayley_number(1)
1

iex> Math.cayley_number(5)
125

iex> Math.cayley_number(18)
121439531096594251776

iex> Math.cayley_number(37)  
7710105884424969623139759010953858981831553019262380893

Calculate Chebyshev's triangle of coefficients at S(n, k).

The coefficient triangle is used for diophantine polynomial analysis, spherical harmonics, series analysis, and other number theoretic applications.

While a recurrence relationship exists, this function uses a binomial expansion to find values.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a049310/1 - Triangle of coefficients of Chebyshev's polynomials

Examples

iex> Math.chebyshev_triangle_coefficient(0, 0)
1

iex> Math.chebyshev_triangle_coefficient(4, 2)
-3

iex> Math.chebyshev_triangle_coefficient(9, 4)
0

iex> Math.chebyshev_triangle_coefficient(11, 7)
36

Check if a number n contains the number m in it's decimal digit representation.

Examples

iex> Math.contains_number?(34, 3)
true

iex> Math.contains_number?(2048, 20)
true

iex> Math.contains_number?(2048, 49)
false

Find all positive coprimes of n, from 2 up to n.

Two numbers a and b are coprime if, and only if, the only positive integer factor that divides both of them is 1.

If you need comprimes of n greater than n, see coprimes/2. If you only need the count of coprimes of n, see totient/1.

Examples

iex> Math.coprimes(2)
[1]

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

iex> Math.coprimes(10)
[1, 3, 7, 9]

iex> Math.coprimes(36)
[1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35]

Find all positive coprimes of n from 2 up to d.

Two numbers a and b are coprime if, and only if, the only positive integer factor that divides both of them is 1.

If you only need the coprimes of n less than or equal to n, see coprimes/1.

Examples

iex> Math.coprimes(2, 10)
[1, 3, 5, 7, 9]

iex> Math.coprimes(3, 20)
[1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20]

iex> Math.coprimes(10, 30)
[1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29]

iex> Math.coprimes(38, 50)
[1, 3, 5, 7, 9, 11, 13, 15, 17, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49]

Find the number of derangements of a set of size n.

A derangement of a set is a permutation of the set, such that no element is in its original position. Also called the subfactorial of n, the recontres number, or de Montmor number.

This implementation uses the Euler recurrence, a(n) = n * a(n - 1) + -1^n.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000166/1 - Derangement, or recontres number

Examples

iex> Math.derangement_count(1)
0

iex> Math.derangement_count(8)
14833

iex> Math.derangement_count(17)
130850092279664

iex> Math.derangement_count(134)
733162663744579191293964143415001307906325722892139819974619962654978249255036185299413091417144999745154783570225783145979302466795277487832988219926200862943908125847693470304687165754228414941338831577093697357593753008645129

Count the number of specific digits in n.

Using the base option, you can select which base the number is converted to before counting digits.

The list of digits being counted can have one or more integers, allowing flexible counting of different combinations of digits (see examples).

Options

• base - Integer. Default 10. Numeric base to convert n to before counting.

Examples

Count how many 2s are in a number:

iex> Math.digit_count(200454232, [2])
3

Count the even digits in a number:

iex> Math.digit_count(123456789, [2, 4, 6, 8])
4

Count the 1s and 2s in the ternary expansion (base 3) of a number:

iex> Math.digit_count(245_987_340, [1, 2], base: 3)
12

Count the number of 25s in the base 60 expansion of a number:

iex> Math.digit_count(1173840858356, [25], base: 60)
2

Break apart n into runs of digits.

Optionally specify the base (default 10) in which to expand the number n. A run of digits is any grouping of identical digits. The groups of digits are returned as lists, so the final result is a list of lists.

Options

• base - Integer. Default 10.

Examples

iex> Math.digit_runs(1233455)
[[1], [2], [3, 3], [4], [5, 5]]

iex> Math.digit_runs(847, base: 2)
[ [1, 1], [0], [1], [0, 0], [1, 1, 1, 1]]

iex> Math.digit_runs(1442792515, base: 16)
[ [5, 5], [15, 15], [4, 4, 4], [3]]

iex> Math.digit_runs(614482, base: 30)
[ [22, 22, 22, 22] ]

iex> Math.digit_runs(-100200)
[ [1], [0, 0], [2], [0, 0]]

Count the number of digit runs in n.

Optionally specify the base (default 10) in which to expand n. See digit_runs/2 for more details on how digit runs are constructed.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a005811/1 - Number of runs in binary expansion of n

Examples

iex> Math.digit_runs_count(1233455)
5

iex> Math.digit_runs_count(54321, base: 2)
9

iex> Math.digit_runs_count(1234567890987654321, base: 8)
18

Calculate the sum of the digits of n.

Examples

iex> Math.digit_sum(1234)
10

iex> Math.digit_sum(2048)
14

iex> Math.digit_sum(1234567890987654321)
90

Generate n digits of pi, as a single large integer.

This function uses a non-digit extraction version of Bailey-Borwein-Plouffe summation for generating accurate digits of Pi in base 10. This uses a summation over fractional values to maintain precision:

Using this formula, it is possible to create many hundreds of digits of Pi in less than a second. Generating 5,000 digits takes roughly 30 seconds.

Examples

iex> Math.digits_of_pi(3)
314

iex> Math.digits_of_pi(31)
3141592653589793238462643383279

iex> Math.digits_of_pi(45)
314159265358979323846264338327950288419716939

Find all divisors of n of the form mx + b.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a002654/1 - Number of ways of writing n as a sum of at most two nonzero squares

Examples

iex> Math.divisors_of_form_mx_plus_b(4, 1, 5)
[1, 5]

iex> Math.divisors_of_form_mx_plus_b(4, 1, 45)
[1, 5, 9, 45]

iex> Math.divisors_of_form_mx_plus_b(4, 3, 4)
[]

iex> Math.divisors_of_form_mx_plus_b(4, 3, 9975)
[3, 7, 15, 19, 35, 75, 95, 175, 399, 475, 1995, 9975]

Calculate the double factorial of n, n!!.

The double factorial steps down by 2 each iteration, with 0!! and 1!! both equal to 1. So the double factorial of 5 is

5!! == 5 * 3 * 1 == 15

This function uses a cache for efficiency.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a001147/1 - Double factorial of odd numbers
• Chunky.Sequence.OEIS.Core.create_sequence_a006882/1 - Double factorials of n

Examples

iex> Math.double_factorial(1)
1

iex> Math.double_factorial(5)
15

iex> Math.double_factorial(10)
3840

iex> Math.double_factorial(18)
185794560

iex> Math.double_factorial(29)
6190283353629375

Count the number of endofunctions (as endomorphisms) for a set of size n.

This counts endofunctions as an endomorphism over the set of size n, which is equivalent to n^n.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000312/1 - Number of endofunctions

Examples

iex> Math.endomorphism_count(0)
1

iex> Math.endomorphism_count(4)
256

iex> Math.endomorphism_count(40)
12089258196146291747061760000000000000000000000000000000000000000

iex> Math.endomorphism_count(123)
114374367934617190099880295228066276746218078451850229775887975052369504785666896446606568365201542169649974727730628842345343196581134895919942820874449837212099476648958359023796078549041949007807220625356526926729664064846685758382803707100766740220839267

Find the n-th Euler number. Also written EulerE.

This calculation of the n-th Euler number is based on the Euler Polynomial:

E_n(1/2) * 2^n

such that the 6th Euler Number would be:

E_6(1/2) * 2^6

or -61

Examples

iex> Math.euler_number(0)
1

iex> Math.euler_number(3)
0

iex> Math.euler_number(6)
-61

iex> Math.euler_number(16)
19391512145

iex> Math.euler_number(64)
45358103330017889174746887871567762366351861519470368881468843837919695760705

Calculate the Euler polynomial E_m(x).

This calculate is based on the explicit double summation:

In this implementation the value of x is always converted to a fraction before calculations begin.

Examples

iex> Math.euler_polynomial(6, Fraction.new(1, 2))
%Chunky.Fraction{den: 4096, num: -3904}

iex> Math.euler_polynomial(6, 4) |> Fraction.get_whole()
1332

iex> Math.euler_polynomial(2, 15) |> Fraction.get_whole()
210

iex> Math.euler_polynomial(8, Fraction.new(1, 3))
%Chunky.Fraction{den: 1679616, num: 7869952}

Find the n-th Euler zig number.

Values for this function are based on the relation of the zig numbers to Euler Numbers, of the form ezig(n) = abs(EulerE(2n))

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000364/1 - Euler secant (or zig) numbers

Examples

iex> Math.euler_zig(0)
1

iex> Math.euler_zig(2)
5

iex> Math.euler_zig(10)
370371188237525

Calculate the Euler zig zag, or up/down, number for n.

The zig zag set is used in combinatorics to count the size of alternating sets of permutations.

Other noted uses of the zig zag numbers (via OEIS A000111):

• Number of linear extensions of the "zig-zag" poset.
• Number of increasing 0-1-2 trees on n vertices.
• ... the number of refinements of partitions.
• For n >= 2, a(n-2) = number of permutations w of an ordered n-set
• The number of binary, rooted, unlabeled histories with n+1 leaves

As the calculation of the Euler Zig Zag is multiply recursive, this implementation uses a cache for efficiency.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000111/1 - Euler or up/down numbers

Examples

iex> Math.euler_zig_zag(1)
1

iex> Math.euler_zig_zag(10)
50521

iex> Math.euler_zig_zag(20)
370371188237525

iex> Math.euler_zig_zag(99)
45608516616801111821043829531451697185581949239892414478770427720660171869441004793654782298700276817088804993740898668991870306963423232

Calculate the Eulerian Number A(n, m), the number of permutations of the numbers 1 to n in which exactly m elements are greater than the previous element.

The Eulerian numbers form the Euler triangle:

                 1                              
             1       1                          
          1      4       1                      
       1     11      11     1                   
    1     26     66     26    1
  1    57    302    302    57   1   

Where n is the row (starting at 1) and m is the offset in the row (starting at 0). So the value 66 is at row 5, offset 2:

iex> Math.eulerian_number(5, 2)
66

The sum of values at row n is n!

This implementation of Eulerian Number calculation uses a recursive algorithm with caching for efficiency.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a008292/1 - Triangle of Eulerian numbers

Examples

iex> Math.eulerian_number(5, 4)
1

iex> Math.eulerian_number(7, 4)
1191

iex> Math.eulerian_number(9, 3)
88234

iex> Math.eulerian_number(25, 13)
3334612565134607644610436

Extend a Kolakoski sequence by one iteration.

Each iteration of the sequence will add one, or more, elements to the sequence.

See start_kolakoski_sequence/1 and extend_kolakoski_sequence_to_length/2.

Examples

iex> Math.start_kolakoski_sequence() |> Math.extend_kolakoski_sequence()
{[1], 1, {1, 2}}

Extend a Kolakoski sequence by successive iterations until the sequence is at least the given length.

As each iteration of the sequence will add one or more elements to the sequence, the best guarantee that can be made is that the newly extended sequence will have at least a certain number of elements.

Examples

iex> Math.start_kolakoski_sequence() |> Math.extend_kolakoski_sequence_to_length(23)
{[1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1], 15, {1, 2}}

iex> {seq, _, _} = Math.start_kolakoski_sequence() |> Math.extend_kolakoski_sequence_to_length(26)
iex> length(seq)
27

Find all pairs of factors of n, with or without duplicates.

This is a variant of the factors/1 function, in that it builds the full pairs of factors of n in tuple form.

Options

• duplicates - Boolean. Default false. If true, include the ordered duplicates of factors (see examples)

Examples

iex> Math.factor_pairs(8)
[{1, 8}, {2, 4}]

iex> Math.factor_pairs(8, duplicates: true)
[{1, 8}, {2, 4}, {4, 2}, {8, 1}]

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

The factorial of n, or n!.

A factorial of n is the product of n * (n - 1) * (n - 2) * ... 1.

This implementation uses a cache to speed up efficiency.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000142/1 - Factorial of n

Examples

iex> Math.factorial(4)
24

iex> Math.factorial(1)
1

iex> Math.factorial(10)
3628800

iex> Math.factorial(20)
2432902008176640000

iex> Math.factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Count the number of possible factorizations of n.

This counts a number as a factor of itself, as well as multi-set factorizations. So 8 has 3 factorizations; 8, 2*4, and 2*2*2.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a001055/1 - The multiplicative partition

Examples

iex> Math.factorization_count(1)
1

iex> Math.factorization_count(30)
5

iex> Math.factorization_count(286)
5

iex> Math.factorization_count(9984)
254

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]

Calculate the falling factorial (n)m.

Also called the descending factorial, falling sequential product, or lower factorial, this is the polynomial expansion:

Examples

iex> Math.falling_factorial(4, 0)
1

iex> Math.falling_factorial(6, 3)
120

iex> Math.falling_factorial(8, 10)
0

iex> Math.falling_factorial(21, 7)
586051200

Compare two floating points number using an epsilon error boundary.

Example

iex> Math.floats_equal?(3.11, 3.1)
false

iex> Math.floats_equal?(3.11, 3.1, 0.05)
true

iex> Math.floats_equal?(104.9999999, 104.9999996)
true

Find the n-th Fubini number, the number of ordered partitions of a set size n.

The Fubini numbers are also useful as (via OEIS A000670):

• the number of preferential arrangements of n labeled elements
• the number of weak orders on n labeled elements
• the number of ways n competitors can rank in a competition, allowing for the possibility of ties
• the number of chains of subsets starting with the empty set and ending with a set of n distinct objects
• the number of 'factor sequences' of N for the case in which N is a product of n distinct primes

This implementation is recursive and relies on binomial/2, so it uses a cache for efficiency.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000670/1 - Fubini numbers

Examples

iex> Math.fubini_number(0)
1

iex> Math.fubini_number(3)
13

iex> Math.fubini_number(19)
92801587319328411133

iex> Math.fubini_number(52)
11012069943086163504795579947992458193990796847590859607173763880168176185195

Find the bases for which n is a Rhonda number.

Via OEIS:

An integer n is a Rhonda number to base b if the product of its digits in base b equals b*Sum of prime factors of n (including multiplicity).

Numbers can be Rhonda to more than one base, see OEIS A100988. By default the get_rhonda_to/1 function evaluates all bases from 4 to 500. You can specify an alternate set of bases with the :bases option.

Options

• :bases - List of Integer. Bases to evaluate.

Examples

iex> Math.get_rhonda_to(1000)
[16, 36]

iex> Math.get_rhonda_to(5670)
[36, 106, 108, 196]

iex> Math.get_rhonda_to(5670, bases: 100..150 |> Enum.to_list())
[106, 108]

Find the gpf(n) or greatest prime factor.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a006530/1 - Greatest prime factor of n

Examples

iex> Math.greatest_prime_factor(1)
1

iex> Math.greatest_prime_factor(39)
13

iex> Math.greatest_prime_factor(99973)
389

Find the Hamming Weight of n in a specific numeric base.

By default, the Hamming Weight is calculated in Base 2.

Hamming weight, binary weight, population count, or (in binary) bit summation, is the number of symbols in a given base representation of an integer that are not 0. See Hamming Weight.

OEIS References:

• Chunky.Sequence.OEIS.Core.create_sequence_a000120/1 - Number of 1's in binary expansion of n

Examples

iex> Math.hamming_weight(29)
4

iex> Math.hamming_weight(29, 10)
2

iex> Math.hamming_weight(100)
3

iex> Math.hamming_weight(100, 10)
1

Does a list of numbers contain any subset that sums to n?

The subset sum solution is an NP-Complete problem. For this implementation a series of heuristics is used to quickly eliminate edge cases, and then an exponential time exact combinatoric algorithm is used to search for solutions. This algoritm is a fast pass recursion - as soon as a valid solution is found, the algorithm terminates. The best case running time is O(1), while the worst case (a full search of all solutions, with no valid sum) is exponential to the size of the list of numbers, or approximates O(2^N*N).

Examples

iex> Math.has_subset_sum?([1, 2, 3, 5, 11], 9)
true

iex> Math.has_subset_sum?([1, 2, 3, 5, 11], 11)
true

iex> Math.has_subset_sum?([1, 2, 3, 5, 11], 23)
false

iex> Math.has_subset_sum?([-3, 2, 4, 11], -1)
true

iex> Math.has_subset_sum?([-3, 2, 4, 11], 14)
true

iex> Math.has_subset_sum?([-3, 2, 4, 11], 10)
true