Discrete Math

discrete-math-ai999x

Number theory, modular arithmetic, combinatorics, graph theory and network algorithms, logic and the mathematics of cryptography.

Mathematics & Statistics Question Answering Token Classification Text Classification Sentence Similarity Feature Extraction

Hugging Face ↗PyPI ↗GitHub ↗See it on the capability orb

99capabilities

7topics

99formulas typeset

8worked examples below

1.0.0version

About this model

What Discrete Math does

Discrete Math (discrete-math-ai999x) is an offline Python package for discrete math. It covers number theory, modular arithmetic, combinatorics, graph theory and network algorithms, logic and the mathematics of cryptography.

It has 99 capabilities — 99 computational procedures — in 7 topics, the largest being Combinatorics, Graph theory, Number theory, Cryptography, Logic and Modular arithmetic. Ask a question in words with ask(), or call a capability by name with typed inputs with solve(). Every answer carries its value and unit, the steps that produced it and the formula in LaTeX.

When a question is not determined — a value is missing, an input is out of range, or the request is outside the package — it says so and names what it needs, instead of guessing. It runs on an ordinary CPU without a network connection (Python >=3.10), and the same question always gets the same answer.

Install

pip install discrete-math-ai999x
hf download AI999X/discrete-math-ai999x --local-dir discrete-math-ai999x

What it covers

Combinatorics25Bell numbers · Bernoulli numbers · Bracelets (rotations and reflections identified) …Cryptography9Affine cipher · Caesar (shift) cipher · Diffie-Hellman key exchange …Graph theory25Articulation points (cut vertices) · Bipartiteness test · Breadth-first search order …Logic9Contradiction test · Evaluate a propositional formula · Logical equivalence of two formulas …Modular arithmetic8Chinese remainder theorem · Discrete logarithm · Linear congruence ax ≡ b (mod m) …Number representations2Base (radix) conversion · Two's complement representation Number theory21Carmichael function · Continued fraction of a rational number · Continued fraction of a square root …

Try it

Worked examples

Each question below was put to discrete-math-ai999x and the answer shown is the one it returned, with the steps it took.

Modular arithmeticm.ask(…)

Find the inverse of 3 modulo 11.

inverse = 4

Show the steps

Modular multiplicative inverse
a x \equiv 1 \pmod m
with a = 3, m = 11
→ inverse = 4

Capability: Modular multiplicative inverse

Modular arithmeticm.ask(…)

Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).

x = 23

modulus = 105

Show the steps

Chinese remainder theorem
x \equiv r_i \pmod{m_i},\ i=1..k \;\Rightarrow\; x \bmod \operatorname{lcm}(m_1,\dots,m_k)
with residues = [2, 3, 2], moduli = [3, 5, 7]
→ x = 23, modulus = 105

Capability: Chinese remainder theorem

Combinatoricsm.ask(…)

How many derangements of 5 objects are there?

derangements = 44

probability = 0.3666666667

Show the steps

Derangements
!n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} = (n-1)\big(!(n-1) + !(n-2)\big)
with n = 5
→ derangements = 44, probability = 0.3666666667

Capability: Derangements

Graph theorym.solve(…)

m.solve("chromatic_number", edges="A-B, B-C, C-A, C-D")

chromatic_number = 3

colouring = {'A': 1, 'B': 2, 'C': 3, 'D': 1}

Show the steps

Chromatic number of a small graph
\chi(G) = \min\{k : G \text{ is } k\text{-colourable}\}
with edges = A-B, B-C, C-A, C-D
→ chromatic_number = 3, colouring = {'A': 1, 'B': 2, 'C': 3, 'D': 1}

Capability: Chromatic number of a small graph

Logicm.ask(…)

Is (p -> q) | (q -> p) a tautology?

tautology = True

false_rows = 0

counterexample = None

Show the steps

Tautology test
\models f \iff \forall v:\ f(v) = 1
with formula = (p -> q) | (q -> p)
→ tautology = True, false_rows = 0, counterexample = None

Capability: Tautology test

Cryptographym.ask(…)

Encrypt "AFFINE CIPHER" with the affine cipher a = 5, b = 8.

result = IHHWVCSWFRCP

Show the steps

Affine cipher
E(x) = (ax + b) \bmod 26,\ D(y) = a^{-1}(y - b) \bmod 26
with a = 5, b = 8, message = AFFINE CIPHER, mode = encrypt
→ result = IHHWVCSWFRCP

Capability: Affine cipher

Number representationsm.ask(…)

Convert 1011 from base 2 to base 10.

result = 11

decimal = 11

Show the steps

Base (radix) conversion
(d_k \dots d_0)_b = \sum_i d_i\, b^i
with digits = 1011, from_base = 2, to_base = 10
→ result = 11, decimal = 11

Capability: Base (radix) conversion

Number theorym.ask(…)

Compute the Carmichael function of 15.

lambda = 4

Show the steps

Carmichael function
\lambda(n) = \operatorname{lcm}\big(\lambda(p_1^{e_1}),\dots\big),\ \lambda(p^e)=p^{e-1}(p-1)
with n = 15
→ lambda = 4

Capability: Carmichael function

Use it

From Python or the command line

Every snippet was run as shown; the output under it is what it printed.

import discrete_math_ai999x as m

a = m.ask("Find the inverse of 3 modulo 11.")
print(a.outcome)
print(a.values)
for step in a.steps:
    print(step["name"])

Output

SOLVED
{'inverse': 4}
Modular multiplicative inverse

import discrete_math_ai999x as m

a = m.solve("chromatic_number", edges="A-B, B-C, C-A, C-D")
print(a.outcome)
print(a.values)

Output

SOLVED
{'chromatic_number': 3, 'colouring': {'A': 1, 'B': 2, 'C': 3, 'D': 1}}

import discrete_math_ai999x as m

# an input is missing: the answer says what it needs instead of guessing
a = m.solve("chromatic_number")
print(a.outcome)
print(a.message)

Output

NEEDS_INPUT
chromatic_number needs edges (the graph as a list of edges u-v (an optional third entry is the weight)). Example: solve('chromatic_number', edges='A-B, B-C, C-A, C-D').

discrete-math-ai999x "Find the inverse of 3 modulo 11."

Output

inverse = 4
1. Modular multiplicative inverse: extended Euclidean algorithm  with a = 3, m = 11  ->  inverse = 4
Assumptions: m >= 2; gcd(a, m) = 1 (otherwise no inverse exists)
…

Figures

Computed, not drawn by hand

Every value in these figures was computed by the package, each point a run of solve(); in a notebook, plot() and plot_relation() draw a capability's curves the same way.

A graph coloured with the fewest colours

\chi(G) = \min\{k : G \text{ is } k\text{-colourable}\}

A wheel graph on 7 vertices with the chord A–C (13 edges): the package finds the chromatic number 4 and the colouring drawn here — no edge joins two vertices of the same colour (colour 1: A, D; colour 2: B, E; colour 3: C, F; colour 4: G).

Breadth-first search, layer by layer

d(v) = d(u) + 1 \text{ when } v \text{ is first seen from } u

Breadth-first search from A on a graph of 9 vertices and 12 edges, each vertex placed in the column of its distance from A as returned by the package (visit order A, B, C, D, E, F, G, H, I; 9 reached); highlighted, one edge per vertex to a neighbour one layer closer.

Stirling numbers of the second kind

S(n,k) = k\,S(n-1,k) + S(n-1,k-1) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n

Stirling numbers of the second kind S(n, k) for n, k = 1 … 7 (row n, column k), each computed by the package: the ways to split n labelled objects into k non-empty groups; row 7 sums to the Bell number B(7) = 877, also computed by the package.

Integer partitions, all and into distinct parts

p(n) = \sum_{k \ne 0} (-1)^{k+1}\, p\!\left(n - \tfrac{k(3k-1)}{2}\right)

The number of ways to write n as a sum of positive integers, p(n), and as a sum of distinct ones, q(n), for n = 1 … 20, each counted by the package (logarithmic scale): p(10) = 42, q(10) = 10; marked: p(20) = 627 (q(20) = 64).

A labelled tree decoded from its Prüfer sequence

\deg(v) = 1 + \#\{i : a_i = v\}

The labelled tree that the package decodes from the Prüfer sequence (3, 3, 3, 7, 7, 8, 8): 9 vertices, edges 1–3, 2–3, 3–4, 3–7, 5–7, 6–8, 7–8, 8–9. A vertex appears in the sequence one time fewer than its degree, so the leaves are exactly the labels the sequence never names.

Formulas

The mathematics inside

12 of its 99 formulas; every one is in the capability browser below.

Modular multiplicative inverse

a x \equiv 1 \pmod m

Chinese remainder theorem

x \equiv r_i \pmod{m_i},\ i=1..k \;\Rightarrow\; x \bmod \operatorname{lcm}(m_1,\dots,m_k)

Derangements

!n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} = (n-1)\big(!(n-1) + !(n-2)\big)

Chromatic number of a small graph

\chi(G) = \min\{k : G \text{ is } k\text{-colourable}\}

Tautology test

\models f \iff \forall v:\ f(v) = 1

Affine cipher

E(x) = (ax + b) \bmod 26,\ D(y) = a^{-1}(y - b) \bmod 26

Base (radix) conversion

(d_k \dots d_0)_b = \sum_i d_i\, b^i

Carmichael function

\lambda(n) = \operatorname{lcm}\big(\lambda(p_1^{e_1}),\dots\big),\ \lambda(p^e)=p^{e-1}(p-1)

Bell numbers

B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k

Caesar (shift) cipher

E(x) = (x + k) \bmod 26

Articulation points (cut vertices)

u \text{ cut vertex} \iff \exists \text{ child } v:\ \mathrm{low}(v) \ge \mathrm{disc}(u)

Contradiction test

\forall v:\ f(v) = 0

Capabilities

Every capability, with an example

Search by name, formula, input or topic. Each capability opens to show what it takes, what it returns, when it applies, and a question it answered.

99 capabilities

Combinatorics 25

Bell numbersbell

B_n: the number of partitions of an n-element set into any number of non-empty blocks.

B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k

Inputs

n size of the set (0..200) integer

Returns

bell the Bell number B_n

Applies when

0 <= n <= 200

Example

m.ask("What is the 5th Bell number?")

→ bell = 52

Bernoulli numbersbernoulli

The Bernoulli number B_n as an exact fraction (convention B_1 = -1/2).

\sum_{k=0}^{m} \binom{m+1}{k} B_k = 0,\quad B_0 = 1

Inputs

n the index n (0..200) integer

Returns

value B_n as a decimal
numerator numerator of B_n in lowest terms
denominator denominator of B_n (positive)

Applies when

0 <= n <= 200
B_1 = -1/2 (the 'first' Bernoulli numbers)

Example

m.ask("What is the Bernoulli number B_10?")

→ numerator = 5, denominator = 66, value = 0.0757576

Bracelets (rotations and reflections identified)bracelets

Distinct bracelets of n beads in k colours when rotations and flips count as the same.

B(n,k) = \tfrac12 N(n,k) + \begin{cases} \tfrac12 k^{(n+1)/2} & n \text{ odd} \\ \tfrac14 (k+1) k^{n/2} & n \text{ even} \end{cases}

Inputs

beads number of beads n (1..60) integer
colours number of colours k (1..60) integer

Returns

bracelets classes under rotation and reflection
necklaces classes under rotation only

Applies when

1 <= n, k <= 60

Example

m.ask("How many bracelets with 6 beads can be made using 2 colours?")

→ bracelets = 13, necklaces = 14

Catalan numberscatalan

C_n: balanced parenthesizations with n pairs, triangulations of an (n+2)-gon, full binary trees with n+1 leaves.

C_n = \frac{1}{n+1}\binom{2n}{n}

Inputs

n the index n (0..500) integer

Returns

catalan the Catalan number C_n

Applies when

0 <= n <= 500
a convex polygon with s sides has C_(s-2) triangulations

Example

m.ask("What is the 10th Catalan number?")

→ catalan = 16796

Coefficient in a binomial expansionbinomial_term

The coefficient of x^k in (a x + b)^n by the binomial theorem (exact integer).

(ax+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k} x^k

Inputs

a coefficient of x inside the bracket integer
b constant inside the bracket integer
n the power n (0..1000) integer
k the power of x asked for integer

Returns

coefficient C(n, k) a^k b^(n-k)

Applies when

integer a, b
0 <= k <= n <= 1000

Example

m.ask("What is the coefficient of x^3 in (2x + 3)^5?")

→ coefficient = 720

Combinations C(n, k)combinations

The number of ways to choose k of n distinct items when order does not matter (exact integer).

\binom{n}{k} = \frac{n!}{k!\,(n-k)!}

Inputs

n number of items to choose from (0..1000) integer
k number chosen (0..n) integer

Returns

combinations C(n, k) = n! / (k! (n-k)!)

Applies when

0 <= k <= n <= 1000
result at most 10^300

Example

m.ask("How many ways are there to choose 3 books from 10?")

→ combinations = 120

Combinations with repetition (multisets)multisets

The number of ways to choose k items from n types when types may repeat and order does not matter.

\left(\!\binom{n}{k}\!\right) = \binom{n+k-1}{k}

Inputs

n number of types (at least 1) integer
k number of items chosen integer

Returns

multisets C(n + k - 1, k)

Applies when

n >= 1
result at most 10^300

Example

m.ask("How many ways can we choose 3 scoops from 5 flavours with repetition allowed?")

→ multisets = 35

Counting multiples by inclusion-exclusioninclusion_exclusion

How many integers in 1..n are divisible by at least one of the given numbers (and how many by none).

\Big|\bigcup_i A_i\Big| = \sum_{\emptyset \ne S} (-1)^{|S|+1} \left\lfloor \frac{n}{\operatorname{lcm}(S)} \right\rfloor

Inputs

n the upper end of the range 1..n integer
divisors the divisors (whole numbers >= 1) vector

Returns

divisible_by_any count divisible by at least one divisor
divisible_by_none count divisible by none

Applies when

n >= 1
1 to 12 divisors, each >= 1

Example

m.ask("How many integers from 1 to 1000 are divisible by 3, 5 or 7?")

→ divisible_by_any = 543, divisible_by_none = 457

Derangementsderangements

!n: permutations of n items with no item in its original place, and the probability !n/n!.

!n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} = (n-1)\big(!(n-1) + !(n-2)\big)

Inputs

n number of items (0..170) integer

Returns

derangements !n
probability !n / n! (tends to 1/e)

Applies when

0 <= n <= 170

Example

m.ask("How many derangements of 5 objects are there?")

→ derangements = 44, probability = 0.366667

Distinct arrangements of the letters of a wordword_arrangements

The number of distinct orderings of a word's letters, repeated letters counted once (multiset permutations).

\frac{n!}{n_1!\,n_2!\cdots n_r!}

Inputs

word the word (letters A-Z; case is ignored) text

Returns

arrangements n! / (n1! n2! ...) over the letter multiplicities
length number of letters
letter_counts how often each letter occurs

Applies when

letters A-Z only (upper and lower case are the same letter)
at most 170 letters

Example

m.ask("How many distinct arrangements of the letters of MISSISSIPPI are there?")

→ arrangements = 34650, length = 11, letter_counts = {'I': 4, 'M': 1, 'P': 2, 'S': 4}

Fibonacci numbersfibonacci

F_n with F_0 = 0, F_1 = 1, F_n = F_(n-1) + F_(n-2) (exact integer).

F_n = F_{n-1} + F_{n-2},\ F_0 = 0,\ F_1 = 1

Inputs

n the index n (0..1000) integer

Returns

fibonacci F_n

Applies when

0 <= n <= 1000
F_0 = 0, F_1 = 1

Example

m.ask("What is the 30th Fibonacci number?")

→ fibonacci = 832040

Integer partitions p(n)integer_partitions

p(n): the number of ways to write n as a sum of positive integers, order ignored.

p(n) = \sum_{k \ne 0} (-1)^{k+1}\, p\!\left(n - \tfrac{k(3k-1)}{2}\right)

Inputs

n the integer n (0..2000) integer

Returns

partitions p(n)

Applies when

0 <= n <= 2000

Example

m.ask("How many partitions of 10 are there?")

→ partitions = 42

Integer solutions of x1 + ... + xk = n (stars and bars)stars_and_bars

How many integer solutions x1 + ... + xk = n have every xi between a lower and an optional upper bound (identical objects into distinct boxes).

\#\{x_i \ge 0, \textstyle\sum x_i = n\} = \binom{n+k-1}{k-1},\quad \sum_j (-1)^j \binom{k}{j}\binom{n - j(c+1) + k-1}{k-1}

Inputs

total the total n (0..2000) integer
variables the number of variables or boxes k (1..50) integer
lower lower bound for every variable (0 = non-negative, 1 = positive) integer optional
upper optional upper bound for every variable integer optional

Returns

solutions number of solutions

Applies when

the bounds apply to every variable
a question must say non-negative or positive

Example

m.ask("How many non-negative integer solutions does x1 + x2 + x3 = 10 have?")

→ solutions = 66

Lattice paths in a gridlattice_paths

Monotone lattice paths using unit steps right and up from (0, 0) to (m, n): C(m + n, m).

\binom{m+n}{m}

Inputs

right number of steps right m integer
up number of steps up n integer

Returns

paths C(m + n, m)

Applies when

m, n >= 0 (the end point is up and to the right)
an a by b grid of squares has C(a + b, a) corner-to-corner paths

Example

m.ask("How many lattice paths go from (0, 0) to (5, 3) moving only right and up?")

→ paths = 56

Lucas numberslucas

L_n with L_0 = 2, L_1 = 1, L_n = L_(n-1) + L_(n-2) (exact integer).

L_n = L_{n-1} + L_{n-2},\ L_0 = 2,\ L_1 = 1

Inputs

n the index n (0..1000) integer

Returns

lucas L_n

Applies when

0 <= n <= 1000
L_0 = 2, L_1 = 1

Example

m.ask("What is the 10th Lucas number?")

→ lucas = 123

Multinomial coefficientmultinomial

n! / (k1! k2! ... km!): ways to split n distinct items into labelled groups of the given sizes.

\binom{n}{k_1,\dots,k_m} = \frac{n!}{k_1!\cdots k_m!}

Inputs

counts the group sizes k1, ..., km (whole numbers) vector
total the stated total n (optional; must equal the sum of the sizes) integer optional

Returns

coefficient the multinomial coefficient
total n = k1 + ... + km

Applies when

sizes are whole numbers >= 0 adding up to at most 170
a stated total must equal their sum

Example

m.ask("Compute the multinomial coefficient for 2, 3, 5.")

→ coefficient = 2520, total = 10

Necklaces (rotations identified)necklaces

Distinct necklaces of n beads in k colours when rotations count as the same (and bracelets, also flips).

N(n,k) = \frac{1}{n}\sum_{d \mid n} \varphi(d)\, k^{n/d}

Inputs

beads number of beads n (1..60) integer
colours number of colours k (1..60) integer

Returns

necklaces classes under rotation
bracelets classes under rotation and reflection

Applies when

1 <= n, k <= 60

Example

m.ask("How many necklaces with 6 beads can be made using 2 colours?")

→ necklaces = 14, bracelets = 13

Partitions into distinct partspartitions_distinct

q(n): the number of ways to write n as a sum of distinct positive integers (equal to partitions into odd parts).

\sum_n q(n) x^n = \prod_{k \ge 1} (1 + x^k) = \prod_{k \ge 1} \frac{1}{1 - x^{2k-1}}

Inputs

n the integer n (0..1000) integer

Returns

partitions q(n)

Applies when

0 <= n <= 1000

Example

m.ask("How many partitions of 10 into distinct parts are there?")

→ partitions = 10

Partitions into exactly k partspartitions_k

p(n, k): the number of ways to write n as a sum of exactly k positive integers, order ignored.

p(n,k) = p(n-1,k-1) + p(n-k,k)

Inputs

n the integer n (0..300) integer
k the number of parts (0..300) integer

Returns

partitions p(n, k)

Applies when

0 <= n, k <= 300

Example

m.ask("How many partitions of 10 into exactly 3 parts are there?")

→ partitions = 8

Permutations P(n, k)permutations

The number of ordered arrangements of k of n distinct items (exact integer); P(n, n) = n!.

P(n,k) = \frac{n!}{(n-k)!}

Inputs

n number of distinct items (0..170) integer
k number arranged (0..n) integer

Returns

permutations P(n, k) = n! / (n-k)!

Applies when

0 <= k <= n <= 170

Example

m.ask("Compute P(10, 3).")

→ permutations = 720

Pigeonhole principle: guaranteed loadpigeonhole_max

Placing n objects into k boxes, some box must hold at least ceil(n / k) objects (and this is the best guarantee).

\max_i x_i \ge \left\lceil \frac{n}{k} \right\rceil

Inputs

items number of objects n integer
boxes number of boxes k integer

Returns

guaranteed ceil(n / k): the largest load every placement must reach in some box

Applies when

n, k >= 1

Example

m.ask("If 25 pigeons are placed into 7 holes, at least how many pigeons must share a hole?")

→ guaranteed = 4

Pigeonhole principle: objects needed for a guaranteepigeonhole_needed

How many objects drawn from k categories guarantee at least r of one category: k (r - 1) + 1.

N = k(r-1) + 1

Inputs

boxes number of categories k integer
at_least the guaranteed count r in one category integer

Returns

needed k (r - 1) + 1

Applies when

k, r >= 1

Example

m.ask("How many socks must be drawn from a drawer with 4 colours to guarantee 3 of the same colour?")

→ needed = 9

Sequences with repetition (n^k)sequences_with_repetition

The number of length-k sequences over n symbols when symbols may repeat.

n^k

Inputs

n number of available symbols (at least 1) integer
k length of the sequence integer

Returns

sequences n^k

Applies when

n >= 1
result at most 10^300

Example

m.ask("How many sequences of length 4 can be formed from 10 digits with repetition allowed?")

→ sequences = 10000

Stirling numbers of the first kindstirling1

c(n, k): permutations of n elements with exactly k cycles (unsigned), and the signed s(n, k).

c(n,k) = (n-1)\,c(n-1,k) + c(n-1,k-1),\quad x^{\overline n} = \sum_k c(n,k)\,x^k

Inputs

n number of elements (0..100) integer
k number of cycles (0..100) integer

Returns

stirling1 unsigned c(n, k)
signed signed s(n, k) = (-1)^(n-k) c(n, k)

Applies when

0 <= n, k <= 100

Example

m.ask("Compute the Stirling number of the first kind c(5, 2).")

→ stirling1 = 50, signed = -50

Stirling numbers of the second kindstirling2

S(n, k): ways to partition an n-element set into k non-empty unlabelled blocks; k! S(n, k) onto functions.

S(n,k) = k\,S(n-1,k) + S(n-1,k-1) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n

Inputs

n size of the set (0..100) integer
k number of blocks (0..100) integer

Returns

stirling2 S(n, k)
surjections k! S(n, k): onto functions from an n-set to a k-set

Applies when

0 <= n, k <= 100

Example

m.ask("Compute the Stirling number of the second kind S(7, 3).")

→ stirling2 = 301, surjections = 1806

Cryptography 9

Affine cipheraffine_cipher

Encrypt or decrypt with the affine cipher E(x) = a x + b (mod 26).

E(x) = (ax + b) \bmod 26,\ D(y) = a^{-1}(y - b) \bmod 26

Inputs

message the message (letters are kept, everything else is dropped) text
a multiplier (coprime to 26) integer
b shift integer
mode encrypt or decrypt choice

Returns

result the result in capital letters, without spaces or punctuation

Applies when

gcd(a, 26) = 1
letters A-Z only; other characters are removed; output is upper case

Example

m.ask("Encrypt \"AFFINE CIPHER\" with the affine cipher a = 5, b = 8.")

→ result = IHHWVCSWFRCP

Caesar (shift) ciphercaesar_cipher

Encrypt or decrypt a message with a Caesar shift of k letters.

E(x) = (x + k) \bmod 26

Inputs

message the message (letters are kept, everything else is dropped) text
shift the shift k integer
mode encrypt or decrypt choice

Returns

result the result in capital letters, without spaces or punctuation

Applies when

letters A-Z only are enciphered; other characters are removed; output is upper case

Example

m.ask("Encrypt \"HELLO WORLD\" with a Caesar shift of 3.")

→ result = KHOORZRUOG

Diffie-Hellman key exchangediffie_hellman

The public values A = g^a, B = g^b (mod p) and the shared secret g^(ab) mod p.

s = B^a \bmod p = A^b \bmod p = g^{ab} \bmod p

Inputs

p the prime modulus integer
g the generator (1 < g < p) integer
a Alice's secret exponent integer
b Bob's secret exponent integer

Returns

A Alice's public value g^a mod p
B Bob's public value g^b mod p
shared shared secret g^(ab) mod p

Applies when

p prime
1 < g < p

Example

m.ask("Diffie-Hellman with p = 23, g = 5, a = 6, b = 15: find the shared secret.")

→ A = 8, B = 19, shared = 2

ElGamal encryptionelgamal_encrypt

ElGamal ciphertext (c1, c2) = (g^k, m h^k) mod p with public key h = g^x.

c_1 = g^k,\ c_2 = m\,h^k \pmod p,\quad m = c_2\,c_1^{-x}

Inputs

p the prime modulus integer
g the generator integer
x the private key integer
k the ephemeral exponent integer
m the message (1 <= m < p) integer

Returns

h public key g^x mod p
c1 g^k mod p
c2 m h^k mod p

Applies when

p prime
1 < g < p
1 <= m < p

Example

m.ask("ElGamal: encrypt m = 10 with p = 23, g = 5, x = 6, k = 3.")

→ h = 8, c1 = 10, c2 = 14

RSA decryptionrsa_decrypt

The RSA plaintext m = c^d mod n of a ciphertext c.

m = c^d \bmod n

Inputs

c the ciphertext (0 <= c < n) integer
d private exponent integer
n modulus integer

Returns

m plaintext c^d mod n

Applies when

0 <= c < n

Example

m.ask("RSA: decrypt c = 2790 with d = 2753 and n = 3233.")

→ m = 65

RSA decryption from p, q and e (CRT)rsa_decrypt_pq

Decrypt an RSA ciphertext knowing the primes: compute d, then m by the Chinese remainder theorem.

m = m_q + q\,\big(q^{-1}(m_p - m_q) \bmod p\big)

Inputs

c the ciphertext (0 <= c < n) integer
p first prime integer
q second prime integer
e public exponent integer

Returns

m the plaintext
d private exponent e^(-1) mod phi(n)
n modulus p q

Applies when

p, q distinct primes
gcd(e, phi(n)) = 1
0 <= c < n

Example

m.ask("RSA: decrypt c = 2790 with p = 61, q = 53 and e = 17.")

→ m = 65, d = 2753, n = 3233

RSA encryptionrsa_encrypt

The RSA ciphertext c = m^e mod n of a message number m.

c = m^e \bmod n

Inputs

m the message as a number (0 <= m < n) integer
e public exponent integer
n modulus integer

Returns

c ciphertext m^e mod n

Applies when

0 <= m < n

Example

m.ask("RSA: encrypt m = 65 with e = 17 and n = 3233.")

→ c = 2790

RSA key from p, q and ersa_keygen

The RSA modulus n = p q, phi(n) = (p-1)(q-1) and the private exponent d = e^(-1) mod phi(n).

n = pq,\ \varphi = (p-1)(q-1),\ d \equiv e^{-1} \pmod{\varphi}

Inputs

p first prime integer
q second prime integer
e public exponent integer

Returns

n modulus p q
phi Euler's phi(n) = (p-1)(q-1)
d private exponent e^(-1) mod phi(n)

Applies when

p, q distinct primes
1 < e < phi(n) and gcd(e, phi(n)) = 1
d is taken modulo phi(n) (not lambda(n))

Example

m.ask("Find the RSA private key d for p = 61, q = 53, e = 17.")

→ n = 3233, phi = 3120, d = 2753

Vigenère ciphervigenere_cipher

Encrypt or decrypt with the Vigenère cipher under a keyword.

c_j = (m_j + k_{j \bmod |k|}) \bmod 26

Inputs

message the message (letters are kept, everything else is dropped) text
key the keyword (letters) text
mode encrypt or decrypt choice

Returns

result the result in capital letters, without spaces or punctuation

Applies when

letters A-Z only; other characters are removed first, so the key runs over letters only; output is upper case

Example

m.ask("Encrypt \"ATTACK AT DAWN\" with the Vigenère cipher and key LEMON.")

→ result = LXFOPVEFRNHR

Graph theory 25

Articulation points (cut vertices)articulation_points

The vertices whose removal increases the number of connected components.

u \text{ cut vertex} \iff \exists \text{ child } v:\ \mathrm{low}(v) \ge \mathrm{disc}(u)

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

count number of articulation points
points the articulation points, ascending

Applies when

undirected simple graph, unweighted

Example

m.ask("Find the articulation points of the graph with edges A-B, B-C, C-A, C-D, D-E.")

→ count = 2, points = ['C', 'D']

Bipartiteness testbipartite

Whether the vertices of an undirected graph split into two sets with every edge between them (no odd cycle).

G \text{ bipartite} \iff G \text{ has no odd cycle}

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

is_bipartite true when the graph is 2-colourable

Applies when

undirected simple graph, unweighted

Example

m.ask("Is the graph with edges A-B, B-C, C-D, D-A bipartite?")

→ is_bipartite = True

Breadth-first search orderbfs_order

The order in which breadth-first search from a source visits the vertices, and each vertex's distance in edges.

d(v) = d(u) + 1 \text{ when } v \text{ is first seen from } u

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges
source the start vertex text
directed true for a directed graph (edges u->v) boolean optional

Returns

order visiting order
reached number of vertices reached
distances number of edges from the source to each reached vertex

Applies when

simple unweighted graph
TIE RULE: neighbours are visited in ascending order of their names (numerically when the names are integers)

Example

m.ask("Give the breadth-first search order from A in the graph with edges A-B, A-C, B-D, C-D, D-E.")

→ order = ['A', 'B', 'C', 'D', 'E'], reached = 5, distances = {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 3}

Bridges (cut edges)bridges

The edges whose removal increases the number of connected components.

(u,v) \text{ bridge} \iff \mathrm{low}(v) > \mathrm{disc}(u)

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

count number of bridges
bridges the bridges [u, v] with u < v, sorted

Applies when

undirected simple graph, unweighted

Example

m.ask("Find the bridges of the graph with edges A-B, B-C, C-A, C-D, D-E.")

→ count = 2, bridges = [['C', 'D'], ['D', 'E']]

Chromatic number of a small graphchromatic_number

The fewest colours needed so that adjacent vertices differ, with one optimal colouring.

\chi(G) = \min\{k : G \text{ is } k\text{-colourable}\}

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

chromatic_number chi(G)
colouring an optimal colouring (colours 1..chi)

Applies when

undirected simple graph, unweighted, at most 12 vertices
the colouring is the first one found trying vertices in ascending name order, colours 1, 2, ...

Example

m.ask("What is the chromatic number of the graph with edges A-B, B-C, C-A, C-D?")

→ chromatic_number = 3, colouring = {'A': 1, 'B': 2, 'C': 3, 'D': 1}

Clique numberclique_number

The size of a largest complete subgraph, with one maximum clique.

\omega(G) = \max\{|K| : K \text{ complete}\}

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

clique_number omega(G)
clique a maximum clique (the lexicographically smallest), ascending

Applies when

undirected simple graph, unweighted, at most 60 vertices

Example

m.ask("What is the clique number of the graph with edges A-B, B-C, C-A, C-D, B-D, A-D, D-E?")

→ clique_number = 4, clique = ['A', 'B', 'C', 'D']

Connected componentsconnected_components

The connected components of an undirected graph: how many, their sizes and members, and whether it is connected.

V = C_1 \sqcup \dots \sqcup C_c

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

count number of connected components
sizes component sizes, descending
is_connected true when there is one component
components members of each component (ascending), components ordered by their first member

Applies when

undirected simple graph, unweighted
the vertices are those named in the edges

Example

m.ask("How many connected components does the graph with edges A-B, C-D, D-E have?")

→ count = 2, sizes = [3, 2], is_connected = False, components = [['A', 'B'], ['C', 'D', 'E']]

Cycle detection in a directed graphdirected_cycle

Whether a directed graph contains a directed cycle (equivalently, whether it is a DAG).

G \text{ acyclic} \iff \text{a topological order exists}

Inputs

edges the directed graph as edges u->v edges

Returns

has_cycle true when a directed cycle exists
is_dag true when the graph is acyclic

Applies when

directed simple graph, unweighted

Example

m.ask("Does the directed graph with edges A->B, B->C, C->A have a cycle?")

→ has_cycle = True, is_dag = False

Cycles in an undirected graph (cyclomatic number)cycle_rank

Whether an undirected graph has a cycle, and its cyclomatic number m - n + c (independent cycles).

\mu(G) = |E| - |V| + c(G)

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

cyclomatic_number m - n + c: the number of independent cycles
has_cycle true when the graph contains a cycle

Applies when

undirected simple graph, unweighted

Example

m.ask("What is the cyclomatic number of the graph with edges A-B, B-C, C-A, D-E?")

→ cyclomatic_number = 1, has_cycle = True

Depth-first search orderdfs_order

The preorder in which depth-first search from a source visits the vertices.

\mathrm{visit}(u):\ \text{mark } u;\ \forall v \in N(u) \text{ ascending, unmarked: } \mathrm{visit}(v)

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges
source the start vertex text
directed true for a directed graph (edges u->v) boolean optional

Returns

order visiting order (preorder)
reached number of vertices reached

Applies when

simple unweighted graph
TIE RULE: recursive DFS that tries neighbours in ascending order of their names (numerically when the names are integers)

Example

m.ask("Give the depth-first search order from A in the graph with edges A-B, A-C, B-D, C-D, D-E.")

→ order = ['A', 'B', 'D', 'C', 'E'], reached = 5

Diameter, radius and centergraph_diameter

Eccentricities of a connected unweighted graph: the diameter (largest), radius (smallest), center and periphery.

\operatorname{diam} G = \max_v e(v),\ \operatorname{rad} G = \min_v e(v)

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

diameter largest distance between two vertices
radius smallest eccentricity
center vertices of smallest eccentricity (ascending)
periphery vertices of largest eccentricity (ascending)

Applies when

connected undirected simple graph, unweighted (distances count edges)

Example

m.ask("What is the diameter of the graph with edges A-B, B-C, C-D, D-E, B-F?")

→ diameter = 4, radius = 2, center = ['C'], periphery = ['A', 'E', 'F']

Eulerian circuits and pathseulerian

Whether an undirected graph has an Euler circuit (closed trail using every edge once) or an Euler path.

\text{circuit} \iff \text{connected} \wedge \forall v:\ 2 \mid \deg v

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

odd_vertices number of vertices of odd degree
connected true when the graph is connected
has_circuit Euler circuit exists: connected and no odd vertex
has_path Euler path exists: connected and 0 or 2 odd vertices

Applies when

undirected simple graph, unweighted
the vertices are those named in the edges

Example

m.ask("Does the graph with edges A-B, B-C, C-A, C-D, D-E, E-C have an Euler circuit?")

→ odd_vertices = 0, connected = True, has_circuit = True, has_path = True

Girth (shortest cycle length)girth

The length of a shortest cycle of an undirected graph (none for a forest).

g(G) = \min\{|C| : C \text{ a cycle of } G\}

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

girth length of the shortest cycle (none when the graph is acyclic)

Applies when

undirected simple graph, unweighted

Example

m.ask("What is the girth of the graph with edges A-B, B-C, C-D, D-A, A-E, E-F, F-A?")

→ girth = 3

Graphical degree sequencegraphical_sequence

Whether a list of non-negative integers is the degree sequence of some simple graph.

\sum_{i \le k} d_i \le k(k-1) + \sum_{i > k} \min(d_i, k)\ \ \forall k,\quad \textstyle\sum d_i \text{ even}

Inputs

degrees the proposed degrees (whole numbers >= 0) vector

Returns

is_graphical true when a simple graph has exactly these degrees

Applies when

whole numbers >= 0

Example

m.ask("Is the sequence 3, 3, 2, 2, 2 graphical?")

→ is_graphical = True

Hamiltonian cycle of a small graphhamiltonian_cycle

Whether an undirected graph has a cycle through every vertex exactly once, with one such cycle.

v_1 v_2 \cdots v_n v_1,\ \{v_i\} = V

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

exists true when a Hamiltonian cycle exists
cycle a Hamiltonian cycle starting and ending at the smallest vertex (none if it does not exist)

Applies when

undirected simple graph, unweighted, at most 12 vertices
the cycle shown is the first found extending through neighbours in ascending order

Example

m.ask("Does the graph with edges A-B, B-C, C-D, D-A, A-C have a Hamiltonian cycle?")

→ exists = True, cycle = ['A', 'B', 'C', 'D', 'A']

Independence numberindependence_number

The size of a largest set of pairwise non-adjacent vertices, with one maximum independent set.

\alpha(G) = \omega(\overline G)

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

independence_number alpha(G)
independent_set a maximum independent set (the lexicographically smallest), ascending

Applies when

undirected simple graph, unweighted, at most 60 vertices
the vertices are those named in the edges

Example

m.ask("What is the independence number of the graph with edges 1-2, 2-3, 3-4, 4-5, 5-1?")

→ independence_number = 2, independent_set = ['1', '3']

Number of spanning trees (Kirchhoff)spanning_tree_count

How many spanning trees an undirected simple graph has (0 if it is disconnected).

\tau(G) = \det L_{11},\quad L = D - A

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

spanning_trees number of spanning trees tau(G)

Applies when

undirected simple graph, unweighted, at most 60 vertices

Example

m.ask("How many spanning trees does the graph with edges A-B, B-C, C-D, D-A, A-C have?")

→ spanning_trees = 8

Number of trianglesgraph_triangles

How many triangles (3-cycles) an undirected graph contains.

t(G) = \tfrac{1}{6}\operatorname{tr}(A^3)

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

triangles number of triangles

Applies when

undirected simple graph, unweighted

Example

m.ask("How many triangles does the graph with edges A-B, B-C, C-A, C-D, D-A have?")

→ triangles = 2

Number of walks of a given lengthwalks_count

How many walks of exactly k edges lead from u to v (the (u, v) entry of A^k).

\#\text{walks}_k(u,v) = (A^k)_{uv}

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges
source start vertex u text
target end vertex v text
length the walk length k (0..200) integer
directed true for a directed graph (edges u->v) boolean optional

Returns

walks number of walks of length k from u to v

Applies when

simple unweighted graph
vertices may repeat along a walk

Example

m.ask("How many walks of length 3 from A to B are there in the graph with edges A-B, B-C, C-A?")

→ walks = 3

Prüfer code of a labelled treeprufer_encode

The Prüfer sequence (length n - 2) of a tree on vertices labelled 1..n.

(a_1, \dots, a_{n-2}),\ a_i = \text{neighbour of the smallest leaf}

Inputs

edges the tree's edges, vertices numbered 1..n (or 0..n-1) edges

Returns

sequence the Prüfer sequence
vertices number of vertices n

Applies when

a tree whose vertices are numbered 1..n or 0..n-1
the smallest leaf is removed at every step

Example

m.ask("Find the Prüfer code of the tree with edges 1-4, 2-4, 3-4, 4-5, 5-6.")

→ sequence = [4, 4, 4, 5], vertices = 6

Strongly connected componentsstrongly_connected

The strongly connected components of a directed graph (vertices mutually reachable).

u \sim v \iff u \leadsto v \wedge v \leadsto u

Inputs

edges the directed graph as edges u->v edges

Returns

count number of strongly connected components
sizes component sizes, descending
components members of each component (ascending), ordered by first member

Applies when

directed simple graph, unweighted

Example

m.ask("Find the strongly connected components of the directed graph with edges A->B, B->C, C->A, C->D.")

→ count = 2, sizes = [3, 1], components = [['A', 'B', 'C'], ['D']]

Topological sorttopological_sort

An ordering of a directed acyclic graph's vertices in which every edge u->v has u before v.

(u \to v) \in E \Rightarrow \pi(u) < \pi(v)

Inputs

edges the directed graph as edges u->v edges

Returns

order the lexicographically smallest topological order
vertices number of vertices

Applies when

directed acyclic simple graph, unweighted
TIE RULE: among the vertices free at each step the smallest name comes first (numerically when integers): the lexicographically smallest order

Example

m.ask("Find a topological sort of the directed graph with edges A->C, B->C, C->D, B->D.")

→ order = ['A', 'B', 'C', 'D'], vertices = 4

Tree from a Prüfer codeprufer_decode

The labelled tree on 1..n (n = length + 2) whose Prüfer sequence is given.

\deg(v) = 1 + \#\{i : a_i = v\}

Inputs

sequence the Prüfer sequence (entries between 1 and n) vector

Returns

edges the tree's edges [u, v] with u < v, sorted
vertices number of vertices n

Applies when

vertices are numbered 1..n with n = length + 2

Example

m.ask("Decode the Prüfer sequence [4, 4, 4, 5].")

→ edges = [[1, 4], [2, 4], [3, 4], [4, 5], [5, 6]], vertices = 6

Tree testis_tree

Whether an undirected graph is a tree: connected with exactly n - 1 edges (equivalently, connected and acyclic).

T \text{ tree} \iff T \text{ connected} \wedge |E| = |V| - 1

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

is_tree true when the graph is a tree
vertices number of vertices
edges number of edges
connected true when the graph is connected

Applies when

undirected simple graph, unweighted
the vertices are those named in the edges

Example

m.ask("Is the graph with edges 1-2, 1-3, 3-4, 3-5 a tree?")

→ is_tree = True, vertices = 5, edges = 4, connected = True

Vertex degrees and degree sequencegraph_degrees

The degree of every vertex of an undirected simple graph, its degree sequence, maximum and minimum degree.

\sum_v \deg v = 2|E|

Inputs

edges the graph as a list of edges u-v (an optional third entry is the weight) edges

Returns

vertices number of vertices (those named in the edges)
edges number of edges
degrees degree of each vertex
degree_sequence degrees in descending order
max_degree maximum degree
min_degree minimum degree

Applies when

undirected simple graph (no loops, no repeated edges), unweighted
the vertices are those named in the edges

Example

m.ask("Find the degree sequence of the graph with edges A-B, A-C, B-C, C-D.")

→ vertices = 4, edges = 4, degrees = {'A': 2, 'B': 2, 'C': 3, 'D': 1}, degree_sequence = [3, 2, 2, 1], max_degree = 3, min_degree = 1

Logic 9

Contradiction testlogic_contradiction

Whether a formula is false under every assignment (unsatisfiable), with a satisfying assignment if not.

\forall v:\ f(v) = 0

Inputs

formula the formula (operators ~ & | ^ -> <->, or words) text

Returns

contradiction true when no assignment satisfies the formula
true_rows number of satisfying assignments
witness the satisfying assignment with the smallest row number (none for a contradiction)

Applies when

at most 12 variables

Example

m.ask("Is p & ~p a contradiction?")

→ contradiction = True, true_rows = 0, witness = none

Evaluate a propositional formulalogic_evaluate

The truth value of a propositional formula under a given assignment of true/false to its variables.

p \to q \equiv \neg p \vee q

Inputs

formula the formula, e.g. (p -> q) & ~r (operators ~ & | ^ -> <->, or not/and/or/xor/implies/iff) text
assignment a truth value for every variable, e.g. 'p = true, q = 0, r = false' text

Returns

value the formula's truth value

Applies when

every variable gets a value and no other name is given
precedence: ~ binds tightest, then &, ^, |, -> (right-associative), <-> loosest

Example

m.ask("Evaluate (p -> q) & ~r when p = true, q = false, r = false.")

→ value = False

Logical equivalence of two formulaslogic_equivalence

Whether two formulas have the same truth value under every assignment, with a distinguishing assignment if not.

f \equiv g \iff \models f \leftrightarrow g

Inputs

formula1 the first formula text
formula2 the second formula text

Returns

equivalent true when the formulas agree on every assignment
differing_rows number of assignments where they differ
counterexample the first distinguishing assignment (none if equivalent)

Applies when

at most 12 variables in total
rows range over the union of both formulas' variables

Example

m.ask("Are (p -> q) and (~p | q) logically equivalent?")

→ equivalent = True, differing_rows = 0, counterexample = none

Minimal product of sums (CNF)minimal_cnf

A minimum conjunctive normal form of a formula: fewest clauses, then fewest literals.

f = \prod_{\text{cover of } \bar f} \sum \bar\ell_i

Inputs

formula the formula (at most 6 variables) text

Returns

expression a minimal product of sums (clauses joined by &)
clauses number of clauses
literals number of literals

Applies when

at most 6 variables
cost: fewest clauses first, then fewest literals

Example

m.ask("Find the minimal CNF of (A | B) & (A | ~B | C).")

→ expression = (A | B) & (A | C), clauses = 2, literals = 4

Minimal sum of products (DNF)minimal_dnf

A minimum disjunctive normal form of a formula: fewest product terms, then fewest literals.

f = \sum_{\text{cover}} \prod \ell_i

Inputs

formula the formula (at most 6 variables) text

Returns

expression a minimal sum of products (terms joined by |, literals by &)
terms number of product terms
literals number of literals

Applies when

at most 6 variables
cost: fewest terms first, then fewest literals; when several minimal forms exist one is shown (all have these counts)

Example

m.ask("Find the minimal DNF of (A & B) | (A & ~B & C).")

→ expression = A & B | A & C, terms = 2, literals = 4

Minimal sum of products from minterms (with don't-cares)minimal_sop_minterms

The minimal sum of products of a Boolean function given by its minterms and optional don't-care rows (Karnaugh-map problems).

F(A,B,C) = \sum m(\dots) + d(\dots)

Inputs

minterms rows where the function is 1 vector
variables number of variables (1..6), named A, B, C, ... integer
dont_cares rows whose value does not matter (optional) vector optional

Returns

expression a minimal sum of products over A, B, C, ... (A is the most significant bit)
terms number of product terms
literals number of literals

Applies when

1..6 variables named A, B, C, D, E, F with A the most significant bit of the row number
cost: fewest terms first, then fewest literals; don't-cares may be used or not

Example

m.ask("Find the minimal sum of products for F(A, B, C) = Σm(1, 3, 5, 7).")

→ expression = C, terms = 1, literals = 1

Satisfiability of a propositional formulalogic_satisfiable

Whether some assignment makes the formula true, how many do, and the first such assignment.

\exists v:\ f(v) = 1

Inputs

formula the formula (operators ~ & | ^ -> <->, or words) text

Returns

satisfiable true when some assignment satisfies the formula
models number of satisfying assignments
first_model the satisfying assignment with the smallest row number (none if unsatisfiable)

Applies when

at most 12 variables
rows are numbered with the first (alphabetical) variable as the most significant bit

Example

m.ask("Is (p | q) & ~p & ~q satisfiable?")

→ satisfiable = False, models = 0, first_model = none

Tautology testlogic_tautology

Whether a formula is true under every assignment, and the first assignment that falsifies it if not.

\models f \iff \forall v:\ f(v) = 1

Inputs

formula the formula (operators ~ & | ^ -> <->, or words) text

Returns

tautology true when every assignment satisfies the formula
false_rows number of falsifying assignments
counterexample the falsifying assignment with the smallest row number (none for a tautology)

Applies when

at most 12 variables

Example

m.ask("Is (p -> q) | (q -> p) a tautology?")

→ tautology = True, false_rows = 0, counterexample = none

Truth table and mintermstruth_table

The full truth table of a propositional formula, the number of true rows and its minterms.

f = \sum m(\text{true rows})

Inputs

formula the formula (operators ~ & | ^ -> <->, or words) text

Returns

variables the variables in alphabetical order
values the formula's value on rows 0, 1, ... as a 0/1 string
true_rows number of true rows
minterms indices of the true rows

Applies when

at most 12 variables
row r assigns the binary digits of r to the variables, the first (alphabetically) variable being the most significant bit

Example

m.ask("Give the truth table of (p -> q) & (q -> r).")

→ variables = ['p', 'q', 'r'], values = 11010001, true_rows = 4, minterms = [0, 1, 3, 7]

Modular arithmetic 8

Chinese remainder theoremcrt

The x with x ≡ r_i (mod m_i) for every i, unique modulo lcm(m_i); moduli need not be coprime.

x \equiv r_i \pmod{m_i},\ i=1..k \;\Rightarrow\; x \bmod \operatorname{lcm}(m_1,\dots,m_k)

Inputs

residues the residues r_i vector
moduli the moduli m_i (each at least 1) vector

Returns

x the smallest non-negative solution
modulus lcm of the moduli: the solution is unique modulo it

Applies when

one residue per modulus
the system is consistent (r_i ≡ r_j modulo gcd(m_i, m_j))

Example

m.ask("Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).")

→ x = 23, modulus = 105

Discrete logarithmdiscrete_log

The smallest x >= 0 with base^x ≡ target (mod m).

g^{x} \equiv h \pmod m,\quad x = i\lceil\sqrt m\rceil + j

Inputs

base the base g integer
target the value h integer
modulus the modulus m (2..10^12) integer

Returns

x the smallest non-negative exponent with g^x ≡ h (mod m)

Applies when

gcd(base, m) = 1
a solution exists

Example

m.ask("Find the smallest x with 3^x ≡ 13 (mod 17).")

→ x = 4

Linear congruence ax ≡ b (mod m)linear_congruence

All solutions of a*x ≡ b (mod m): how many there are modulo m, the smallest, and their spacing.

ax\equiv b \pmod m \iff x \equiv \tfrac{b}{g}\left(\tfrac{a}{g}\right)^{-1} \pmod{\tfrac{m}{g}},\ g=\gcd(a,m)\mid b

Inputs

a coefficient of x integer
b right-hand side integer
m modulus (at least 1) integer

Returns

smallest smallest non-negative solution (none when there is no solution)
count number of solutions modulo m (gcd(a, m) when it divides b, else 0)
step m / gcd(a, m): solutions are smallest + k*step

Applies when

m >= 1
solvable exactly when gcd(a, m) divides b

Example

m.ask("Solve 3x ≡ 4 (mod 7).")

→ smallest = 6, count = 1, step = 7

Modular exponentiationmod_pow

a^e mod m by repeated squaring (also the last k digits of a power).

a^{e} \bmod m,\quad a^{2k} = (a^k)^2,\ a^{2k+1} = a\,(a^k)^2

Inputs

base the base a integer
exponent the exponent e (at least 0) integer
modulus the modulus m (at least 1) integer

Returns

result a^e mod m, between 0 and m - 1

Applies when

e >= 0
m >= 1

Example

m.ask("What is 3^200 mod 13?")

→ result = 9

Modular multiplicative inversemod_inverse

The x in 0..m-1 with a*x ≡ 1 (mod m); it exists exactly when gcd(a, m) = 1.

a x \equiv 1 \pmod m

Inputs

a the integer to invert integer
m the modulus (at least 2) integer

Returns

inverse a^{-1} mod m

Applies when

m >= 2
gcd(a, m) = 1 (otherwise no inverse exists)

Example

m.ask("Find the inverse of 3 modulo 11.")

→ inverse = 4

Multiplicative ordermultiplicative_order

The smallest k >= 1 with a^k ≡ 1 (mod n).

\operatorname{ord}_n(a) = \min\{k \ge 1 : a^k \equiv 1 \pmod n\},\ \operatorname{ord}_n(a) \mid \lambda(n)

Inputs

a the integer a (coprime to n) integer
n the modulus (at least 2) integer

Returns

order ord_n(a)

Applies when

gcd(a, n) = 1

Example

m.ask("What is the order of 2 modulo 7?")

→ order = 3

Remainder modulo m (Euclidean division)mod_reduce

a mod m as the least non-negative residue, with the floor quotient: a = q*m + r, 0 <= r < m.

a = q m + r,\quad 0 \le r < m

Inputs

a the integer to reduce integer
m the modulus (at least 1) integer

Returns

remainder r with 0 <= r < m
quotient q = floor(a/m)

Applies when

m >= 1
the remainder is never negative, also for negative a

Example

m.ask("What is 17 mod 5?")

→ remainder = 2, quotient = 3

Smallest primitive root modulo a primeprimitive_root

The smallest g whose powers run through every non-zero residue modulo the prime p.

g^{(p-1)/q} \not\equiv 1 \pmod p \ \ \forall q \mid p-1

Inputs

p a prime integer

Returns

root the smallest primitive root modulo p

Applies when

p prime (primitive roots also exist for 4, p^k and 2p^k, which this capability does not take)

Example

m.ask("Find the smallest primitive root modulo 23.")

→ root = 5

Number representations 2

Base (radix) conversionbase_convert

Rewrite an integer from one base (2..36) to another, with its decimal value.

(d_k \dots d_0)_b = \sum_i d_i\, b^i

Inputs

digits the number written in the source base (digits 0-9 then A-Z) text
from_base the source base (2..36) integer
to_base the target base (2..36) integer

Returns

result the number written in the target base (upper-case digits)
decimal its value in base 10

Applies when

2 <= bases <= 36
every digit is valid in the source base
a leading minus sign is kept

Example

m.ask("Convert 1011 from base 2 to base 10.")

→ result = 11, decimal = 11

Two's complement representationtwos_complement

The b-bit two's complement bit pattern of a signed integer, and that pattern read as an unsigned number.

\text{pattern}(n) = n \bmod 2^b

Inputs

n the signed integer integer
bits the word length b (2..64) integer

Returns

bits_text the b-bit pattern
unsigned the pattern read as an unsigned integer (n mod 2^b)

Applies when

-2^(b-1) <= n < 2^(b-1)

Example

m.ask("What is the 8-bit two's complement of -5?")

→ bits_text = 11111011, unsigned = 251

Number theory 21

Carmichael functioncarmichael_lambda

lambda(n): the smallest m with a^m ≡ 1 (mod n) for every a coprime to n (the exponent of the unit group).

\lambda(n) = \operatorname{lcm}\big(\lambda(p_1^{e_1}),\dots\big),\ \lambda(p^e)=p^{e-1}(p-1)

Inputs

n a positive integer integer

Returns

lambda Carmichael's lambda(n)

Applies when

n >= 1

Example

m.ask("Compute the Carmichael function of 15.")

→ lambda = 4

Continued fraction of a rational numbercf_rational

The finite simple continued fraction [a0; a1, ..., an] of p/q (canonical form: last term >= 2).

\frac{p}{q} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{\ddots + \cfrac{1}{a_n}}}

Inputs

numerator the numerator p integer
denominator the denominator q (at least 1) integer

Returns

terms the partial quotients [a0, a1, ..., an]
length number of partial quotients

Applies when

q >= 1
a0 = floor(p/q) (negative for negative p); canonical: the last term is at least 2

Example

m.ask("Find the continued fraction of 415/93.")

→ terms = [4, 2, 6, 7], length = 4

Continued fraction of a square rootcf_sqrt

The periodic continued fraction sqrt(d) = [a0; (a1, ..., ak)] of a non-square d, and its period length.

\sqrt d = [a_0; \overline{a_1, \dots, a_{k-1}, 2a_0}]

Inputs

d a positive non-square integer integer

Returns

a0 integer part floor(sqrt(d))
period the repeating block (ends with 2*a0)
period_length length of the period

Applies when

d not a perfect square

Example

m.ask("Find the continued fraction of sqrt(23).")

→ a0 = 4, period = [1, 3, 1, 8], period_length = 4

Divisors, divisor count and divisor sumdivisor_functions

All positive divisors of n, their number tau(n), their sum sigma(n), and whether n is perfect, abundant or deficient.

\tau(n)=\prod (e_i+1),\qquad \sigma(n)=\prod \frac{p_i^{e_i+1}-1}{p_i-1}

Inputs

n a positive integer integer

Returns

count number of divisors tau(n)
sum sum of divisors sigma(n)
proper_sum sum of the proper divisors sigma(n) - n
classification perfect, abundant or deficient
divisors every divisor, ascending

Applies when

n a whole number, 1 <= n <= 10^12

Example

m.ask("How many divisors does 360 have?")

→ count = 24, sum = 1170, proper_sum = 810, classification = abundant, divisors = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360]

Euler's totient functioneuler_phi

phi(n): how many integers in 1..n are coprime to n.

\varphi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)

Inputs

n a positive integer integer

Returns

phi Euler's totient phi(n)

Applies when

n a whole number, 1 <= n <= 10^15

Example

m.ask("What is Euler's totient of 36?")

→ phi = 12

Extended Euclidean algorithm (Bezout coefficients)extended_gcd

gcd(a, b) and integers x, y with a*x + b*y = gcd(a, b).

a x + b y = \gcd(a, b)

Inputs

a first positive integer integer
b second positive integer integer

Returns

gcd gcd(a, b)
x coefficient of a from the extended Euclidean algorithm
y coefficient of b from the extended Euclidean algorithm
x_min the coefficient of a with 0 <= x_min < b/gcd
y_min the matching coefficient of b

Applies when

a, b whole numbers >= 1
(x, y) are the coefficients the standard extended Euclidean algorithm produces; (x_min, y_min) is the solution with the smallest non-negative x

Example

m.ask("Find the Bezout coefficients of 240 and 46.")

→ gcd = 2, x = -9, y = 47, x_min = 14, y_min = -73

Greatest common divisor and least common multiplegcd_lcm

The gcd and lcm of two or more positive integers (Euclid's algorithm).

\gcd(a,b)=\gcd(b,\,a \bmod b),\qquad \operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}

Inputs

numbers the positive integers (two or more) vector

Returns

gcd greatest common divisor
lcm least common multiple

Applies when

two or more whole numbers, each at least 1

Example

m.ask("What is the gcd of 84 and 36?")

→ gcd = 12, lcm = 252

Integer square root and perfect squaresinteger_sqrt

floor(sqrt(n)) computed exactly, the remainder n - floor(sqrt(n))^2, and whether n is a perfect square.

r = \lfloor \sqrt n \rfloor \iff r^2 \le n < (r+1)^2

Inputs

n a whole number (at least 0) integer

Returns

isqrt floor(sqrt(n))
remainder n - isqrt^2
is_square true when n is a perfect square

Applies when

n >= 0

Example

m.ask("What is the integer square root of 1000?")

→ isqrt = 31, remainder = 39, is_square = False

Jacobi symboljacobi_symbol

(a/n) for an odd positive n, the product of Legendre symbols over the prime factors of n.

\left(\frac{a}{n}\right) = \prod_i \left(\frac{a}{p_i}\right)^{e_i},\quad n = \prod p_i^{e_i}

Inputs

a the integer a integer
n an odd positive integer integer

Returns

symbol the Jacobi symbol (a/n): -1, 0 or 1

Applies when

n odd and positive

Example

m.ask("Compute the Jacobi symbol (1001/9907).")

→ symbol = -1

Legendre symbollegendre_symbol

(a/p) for an odd prime p: 1 if a is a non-zero quadratic residue mod p, -1 if not, 0 if p divides a.

\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p

Inputs

a the integer a integer
p an odd prime integer

Returns

symbol the Legendre symbol (a/p): -1, 0 or 1

Applies when

p an odd prime

Example

m.ask("Find the Legendre symbol (5/11).")

→ symbol = 1

Linear Diophantine equation ax + by = clinear_diophantine

Whether a*x + b*y = c has integer solutions, and the general solution x = x0 + (b/g) t, y = y0 - (a/g) t.

ax+by=c \text{ solvable} \iff \gcd(a,b)\mid c;\quad x=x_0+\tfrac{b}{g}t,\; y=y_0-\tfrac{a}{g}t

Inputs

a coefficient of x (non-zero) integer
b coefficient of y (non-zero) integer
c right-hand side integer

Returns

solvable true when gcd(a, b) divides c
x0 the solution with the smallest non-negative x
y0 the matching y
x_step b/g: the step of x between solutions
y_step -a/g: the step of y between solutions

Applies when

a, b non-zero integers
solutions exist exactly when gcd(a, b) divides c

Example

m.ask("Find all integer solutions of 12x + 18y = 30.")

→ solvable = True, x0 = 1, y0 = 1, x_step = 3, y_step = -2

Möbius functionmobius

mu(n): 0 if a square divides n, otherwise (-1)^(number of prime factors).

\mu(n) = \begin{cases} (-1)^k & n = p_1\cdots p_k \text{ squarefree} \\ 0 & p^2 \mid n \end{cases}

Inputs

n a positive integer integer

Returns

mu the Möbius function mu(n)
squarefree true when no square > 1 divides n

Applies when

n >= 1

Example

m.ask("Compute the Möbius function of 30.")

→ mu = -1, squarefree = True

Next primenext_prime

The smallest prime strictly greater than n.

\min\{p > n : p \text{ prime}\}

Inputs

n the whole number n (at least 0) integer

Returns

prime the smallest prime p > n

Applies when

n >= 0
strictly greater: the next prime after a prime p is not p

Example

m.ask("What is the smallest prime greater than 100?")

→ prime = 101

Pell's equation (fundamental solution)pell_equation

The smallest positive solution (x, y) of x^2 - d y^2 = 1 for a non-square d.

x^2 - d\,y^2 = 1,\quad \frac{x}{y} = [a_0; a_1, \dots, a_{k-1}]

Inputs

d a non-square positive integer (2..1000) integer

Returns

x fundamental solution x
y fundamental solution y

Applies when

d not a perfect square
2 <= d <= 1000

Example

m.ask("Find the fundamental solution of x^2 - 61y^2 = 1.")

→ x = 1.76632e+09, y = 2.26154e+08

Previous primeprevious_prime

The largest prime strictly less than n.

\max\{p < n : p \text{ prime}\}

Inputs

n the whole number n (at least 3) integer

Returns

prime the largest prime p < n

Applies when

n >= 3
strictly less: the prime before a prime p is not p

Example

m.ask("What is the largest prime less than 100?")

→ prime = 97

Primality testis_prime

Whether n is prime (deterministic Miller-Rabin, exact for every n below 2^64), with its smallest prime factor.

a^{d}\equiv 1 \ \text{or}\ a^{2^r d}\equiv -1 \pmod n \text{ for every base } a

Inputs

n the whole number to test integer

Returns

is_prime true when n is prime
smallest_prime_factor smallest prime dividing n (n itself when prime; none for n < 2)

Applies when

0 <= n < 2^64 (questions accept n up to 10^15)

Example

m.ask("Is 97 prime?")

→ is_prime = True, smallest_prime_factor = 97

Prime factorizationprime_factorization

The prime factorization of n, its largest and smallest prime factors and the number of prime factors.

n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}

Inputs

n the whole number to factor (at least 2) integer

Returns

factorization list of [prime, exponent] pairs, primes ascending
distinct_primes number of distinct prime factors
prime_factors_with_multiplicity number of prime factors counted with multiplicity
largest_prime_factor largest prime factor
smallest_prime_factor smallest prime factor
text the factorization written as p^e × ...

Applies when

n a whole number, 2 <= n <= 10^15

Example

m.ask("Find the prime factorization of 360.")

→ factorization = [[2, 3], [3, 2], [5, 1]], distinct_primes = 3, prime_factors_with_multiplicity = 6, largest_prime_factor = 5, smallest_prime_factor = 2, text = 2^3 × 3^2 × 5

Prime-counting functionprime_counting

pi(x): how many primes are at most x.

\pi(x) = \#\{p \le x : p \text{ prime}\}

Inputs

x the bound (0..5,000,000) integer

Returns

count number of primes p <= x

Applies when

0 <= x <= 5,000,000
'less than N' counts primes up to N - 1

Example

m.ask("How many primes are there less than 100?")

→ count = 25

Square roots modulo a primesqrt_mod

Every x in 0..p-1 with x^2 ≡ a (mod p), for a prime p.

x^2 \equiv a \pmod p,\quad a^{(p-1)/2} \equiv 1

Inputs

a the integer a integer
p a prime modulus integer

Returns

roots all square roots of a modulo p, ascending
count number of roots (0, 1 or 2)
smallest the smallest root (none when a is a non-residue)

Applies when

p prime

Example

m.ask("Solve x^2 ≡ 10 (mod 13).")

→ roots = [6, 7], count = 2, smallest = 6

Sums of two squarestwo_squares

Every way to write n = x^2 + y^2 with 0 <= x <= y, and r2(n), the number of ordered signed representations.

r_2(n) = 4\big(d_1(n) - d_3(n)\big)

Inputs

n a whole number (0..10^12) integer

Returns

representations pairs [x, y] with 0 <= x <= y and x^2 + y^2 = n
count number of such pairs
r2 r2(n): ordered representations with signs

Applies when

0 <= n <= 10^12

Example

m.ask("Write 325 as a sum of two squares.")

→ representations = [[1, 18], [6, 17], [10, 15]], count = 3, r2 = 24

The n-th primenth_prime

The n-th prime number p_n (p_1 = 2).

p_n < n(\ln n + \ln\ln n)\quad (n \ge 6)

Inputs

n the index n (1..300,000) integer

Returns

prime the n-th prime

Applies when

1 <= n <= 300,000
p_1 = 2

Example

m.ask("What is the 100th prime?")

→ prime = 541

Versions & files

Releases and repository files

Versions

Version	Released
1.0.0	2026-10-25

Files

15 files, 45.7 MB in total. The largest:

File	Size
model.safetensors	18.9 MB
dist/discrete_math_ai999x-1.0.0-py3-none-any.whl	18 MB
onnx/search/encoder.int8.onnx	4.9 MB
docs/discrete_math_ai999x_capabilities.pdf	3 MB
onnx/search/index.json	403.3 KB
docs/discrete_math_ai999x_capabilities.html	239 KB
onnx/search/tokenizer.json	176.4 KB
docs/discrete_math_ai999x_capabilities.md	168.9 KB
README.md	20.5 KB
LICENSE	11.4 KB
evaluation/release_gate.md	2.3 KB
evaluation/KNOWLEDGE_CARD.md	1.4 KB

Browse every file ↗

Questions

Frequently asked

What does discrete-math-ai999x do?

Discrete Math answers questions in discrete math: number theory, modular arithmetic, combinatorics, graph theory and network algorithms, logic and the mathematics of cryptography. Each answer gives the value with its unit, the steps and the formula in LaTeX.

How do I install discrete-math-ai999x?

With pip: pip install discrete-math-ai999x. The same files are on Hugging Face (hf download AI999X/discrete-math-ai999x --local-dir discrete-math-ai999x) and GitHub.

Does it run offline?

Yes. It is a Python package that runs on an ordinary CPU without a network connection (Python >=3.10); no GPU and no API key are needed.

How many capabilities does discrete-math-ai999x have?

99 capabilities in 7 topics, including Combinatorics, Graph theory, Number theory, Cryptography, Logic.

Which field and tasks does it cover?

Field: Mathematics & Statistics. Tasks: Question Answering, Token Classification, Text Classification, Sentence Similarity, Feature Extraction.

What does an answer look like?

Asked "Find the inverse of 3 modulo 11.", it answers: inverse = 4.

What happens when a question cannot be answered?

It says so and names what is missing or out of range, instead of guessing a number.

Explore every model.

More in Mathematics & Statistics All models Capability orb