discrete-math-ai999x — offline, verified discrete math solver with step-by-step answers

Desktop app & command line · Compute in your browser · Install (Python) · Guides · Evaluation · AI999X on Hugging Face · Website · Support: Buy Me a Coffee

License: Apache-2.0 · Author: Ibnul Jaif Farabi (creator and engineer) · Organization: AI999X · Version 1.0.3

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

discrete-math-ai999x is an offline, deterministic Python solver that answers discrete math questions with verified results from 99 certified capabilities, gives 538 documented answers identically on Windows and Linux, and refuses rather than guesses when an answer cannot be verified.

discrete-math-ai999x is a compact, deterministic discrete math engine for Python. It reads a question in plain English (or a typed call), picks a certified discrete math capability, computes the answer exactly, checks it, and returns the result with its steps, units, LaTeX and assumptions — or an honest refusal that says what is missing. It runs fully offline on any CPU, needs no GPU, no API key and no internet, and is built to give zero wrong answers: when it is not sure, it refuses instead of guessing.

Run it your way. discrete-math-ai999x comes as the AI999X desktop app and as the command-line program discrete-math for Windows and Linux, runs in your browser as WebAssembly, and installs as a Python package. The desktop app, the command line and the browser run the same compiled Rust program on your own device: offline, no Python needed.

Get it

Way to run it	For	Get it
AI999X Discrete Math desktop app 1.2.0	Windows, Linux — this model in its own app: search, ask in words, forms, live figures, explanations, offline	Windows (x86-64) · Linux (x86-64)
AI999X desktop app 1.2.0	Windows, Linux — every AI999X model in one app: search, ask in words, forms, live figures, explanations, offline	Windows (x86-64) · Linux (x86-64)
Command line (discrete-math)	Windows, Linux — one program per model, offline, no Python	Windows (x86-64) · Linux (x86-64)
In your browser	any device — nothing to install	Compute on the model page
Python	Python 3.10+	pip install discrete-math-ai999x

Checksums: SHA256SUMS · every version: https://www.ai999x.com/downloads/desktop/latest/ · install guide: desktop & command line

Rust versions

Discrete Math also comes as native programs compiled from Rust, version 1.2.0 of the AI999X desktop app and command line: they run offline on your computer and need no Python. Each file is in this repository's rust/ folder, on the GitHub release v1.0.3 and on the website.

Program	System	File	Size	Download	Use
Desktop app (Discrete Math)	Windows x86-64	ai999x-discrete-math-1.2.0-windows-x86_64.zip	8.0 MB	Hub · GitHub · website	unzip, then double-click ai999x-discrete-math.exe (no installer)
Desktop app (Discrete Math)	Linux x86-64	ai999x-discrete-math-1.2.0-linux-x86_64.tar.gz	8.9 MB	Hub · GitHub · website	extract, then run ./ai999x-discrete-math (X11 or Wayland desktop)
Command line (discrete-math)	Windows x86-64	ai999x-discrete-math-cli-1.2.0-windows-x86_64.zip	3.5 MB	Hub · GitHub · website (all models)	unzip, then discrete-math.exe ask "<question>" or discrete-math.exe solve <capability> name=value
Command line (discrete-math)	Linux x86-64	ai999x-discrete-math-cli-1.2.0-linux-x86_64.tar.gz	3.5 MB	Hub · GitHub · website (all models)	extract, then ./discrete-math ask "<question>" or ./discrete-math solve <capability> name=value

The command-line archive holds discrete-math with a README of its commands and examples, the licence and the notice. Checksums: rust/SHA256SUMS (sha256sum -c SHA256SUMS).

Quick start

Desktop app

Download AI999X Discrete Math for your system (above), unpack it and start it; type a question in words or pick a capability, fill in the form and press Compute. Figures and an explanation of the answer appear beside it. The AI999X desktop app has the same, with Discrete Math among all AI999X models.

Linux, from a terminal:

curl -LO https://www.ai999x.com/downloads/desktop/1.2.0/ai999x-discrete-math-1.2.0-linux-x86_64.tar.gz
curl -LO https://www.ai999x.com/downloads/desktop/1.2.0/SHA256SUMS
sha256sum -c --ignore-missing SHA256SUMS
tar xzf ai999x-discrete-math-1.2.0-linux-x86_64.tar.gz
./ai999x-discrete-math-1.2.0-linux-x86_64/ai999x-discrete-math

Command line

Linux:

curl -LO https://www.ai999x.com/downloads/desktop/1.2.0/ai999x-cli-1.2.0-linux-x86_64.tar.gz
curl -LO https://www.ai999x.com/downloads/desktop/1.2.0/SHA256SUMS
sha256sum -c --ignore-missing SHA256SUMS
mkdir -p ~/.local/share && tar xzf ai999x-cli-1.2.0-linux-x86_64.tar.gz -C ~/.local/share
echo 'export PATH="$HOME/.local/share/ai999x-cli-1.2.0-linux-x86_64:$PATH"' >> ~/.bashrc && source ~/.bashrc
discrete-math --version

Windows (PowerShell):

$F = "ai999x-cli-1.2.0-windows-x86_64.zip"
Invoke-WebRequest "https://www.ai999x.com/downloads/desktop/1.2.0/$F" -OutFile $F
Invoke-WebRequest "https://www.ai999x.com/downloads/desktop/1.2.0/SHA256SUMS" -OutFile SHA256SUMS
(Get-FileHash $F -Algorithm SHA256).Hash.ToLower() -eq ((Select-String -SimpleMatch $F SHA256SUMS).Line -split ' ')[0]
Expand-Archive $F -DestinationPath "$env:LOCALAPPDATA\AI999X" -Force
$D = "$env:LOCALAPPDATA\AI999X\ai999x-cli-1.2.0-windows-x86_64"; $env:Path += ";$D"
[Environment]::SetEnvironmentVariable("Path", [Environment]::GetEnvironmentVariable("Path", "User") + ";$D", "User")
discrete-math --version

Every command below was run as shown; the text under it is what the program printed.

Ask in words — Write the question as you would say it: the program reads the quantities and their units, picks the capability and answers.

$ discrete-math ask "Find the inverse of 3 modulo 11."
Read as: Modular multiplicative inverse
inverse = 4
  by: Modular multiplicative inverse  (extended Euclidean algorithm)
  assumes: m >= 2; gcd(a, m) = 1 (otherwise no inverse exists)

What a capability needs — The equation or method, every input and output with its SI unit. Read this before solve: it tells you the input names.

$ discrete-math info mod_inverse
Modular multiplicative inverse
  extended Euclidean algorithm
  in   a        the integer to invert (integer) [1]
  in   m        the modulus (at least 2) (integer) [1]
  out  inverse  a^{-1} mod m [1]

Solve — Inputs as name=value, each with any unit of the right kind. The answer lists every output, the method used, each input converted to SI, and the conditions the answer assumes.

$ discrete-math solve mod_inverse a=3 m=11
inverse = 4
  by: Modular multiplicative inverse  (extended Euclidean algorithm)
  assumes: m >= 2; gcd(a, m) = 1 (otherwise no inverse exists)

Draw the figures — The live figures for your own inputs, written as SVG files into the folder given with --out (here the current folder); open them in any browser. Without --out the SVG text comes back as JSON.

$ discrete-math figures mod_inverse a=3 m=11 --out .
[
  {
    "slug": "mod-inverse-live-1",
    "title": "A^{-1} mod m as the integer to invert varies",
    "caption": "A^{-1} mod m as a runs from 1 to 7, every other input as you entered it (7 solutions). Marked: your a = 3 gives inverse = 4. Your inputs: a = 3, m = 11.",
    "file": "./mod-inverse-live-1.svg"
  },
  {
    "slug": "mod-inverse-live-2",
    "title": "A^{-1} mod m as the modulus (at least 2) varies",
    "caption": "A^{-1} mod m as m runs from 2 to 28, every other input as you entered it (11 solutions). Values in this range where the inputs admit no answer (4 of 15) are left out. Marked: your m = 11 gives inverse = 4. Your inputs: a = 3, m = 11.",
    "file": "./mod-inverse-live-2.svg"
  }
]

Many questions at once — One JSON request per line in, one JSON answer per line out, in order: for scripts, notebooks and agents (the program starts once). In PowerShell: Get-Content cases.jsonl | discrete-math batch

cases.jsonl:

{"key": "mod_inverse", "inputs": {"a": "3", "m": "11"}}
{"key": "crt", "inputs": {"residues": "[2, 3, 2]", "moduli": "[3, 5, 7]"}}

$ discrete-math batch < cases.jsonl
{"outcome":"SOLVED","message":"","value":4.0,"unit":"","solved_for":"inverse","values":[["inverse",4,""]],"target":"inverse","phrase":"a^{-1} mod m","assumptions":["m >= 2","gcd(a, m) = 1 (otherwise no inverse exists)"],"name":"Modular multiplicative inverse","equation":"extended Euclidean algorithm"}
{"outcome":"SOLVED","message":"","value":23.0,"unit":"","solved_for":"x","values":[["x",23,""],["modulus",105,""]],"target":"x","phrase":"the smallest non-negative solution","assumptions":["one residue per modulus","the system is consistent (r_i ≡ r_j modulo gcd(m_i, m_j))"],"name":"Chinese remainder theorem","equation":"merge the congruences pairwise with the extended Euclidean algorithm (works for non-coprime moduli)"}

In your browser

Open Discrete Math on ai999x.com, choose a capability and press Compute: the model runs on your own device as WebAssembly; nothing is sent anywhere. Change any input (any unit of the right kind) and the answer, its explanation and the figures follow.

In your own page: discrete_math_ai999x.wasm and the loader ax-wasm.js (https://www.ai999x.com/compute/rust/ax-wasm.js).

Python

pip install discrete-math-ai999x

Worked examples in every form

The same worked example from the command line, from Python and in the browser. Each command-line output is what the program printed.

Bell numbers

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

Command line:

$ discrete-math solve bell n=5
bell = 52
  by: Bell numbers  (Bell triangle (Aitken's array))
  assumes: 0 <= n <= 200

Python:

import discrete_math_ai999x as m

a = m.solve("bell", n="5")
print(a.values or (a.value, a.unit))

Browser: open this capability on the model page and press Compute in your browser.

What this means: This calculation determines the total number of ways to partition a set containing 5 elements into any number of non-empty subsets. The result, denoted as 52, represents the sum of all Stirling numbers of the second kind for that specific set size. It quantifies the comprehensive possibilities for splitting the group without regard to the order of blocks or their internal arrangement.

Bernoulli numbers

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

Command line:

$ discrete-math solve bernoulli n=10
numerator = 5
denominator = 66
value = 0.07575757576
  by: Bernoulli numbers  (exact recurrence sum_{k=0}^{m} C(m+1, k) B_k = 0 in rational arithmetic)
  assumes: 0 <= n <= 200; B_1 = -1/2 (the 'first' Bernoulli numbers)

Python:

import discrete_math_ai999x as m

a = m.solve("bernoulli", n="10")
print(a.values or (a.value, a.unit))

Browser: open this capability on the model page and press Compute in your browser.

What this means: This calculation determines the Bernoulli number corresponding to the input index 10. Using a recursive definition with rational arithmetic, the result is expressed as an exact fraction where the numerator is 5 and the denominator is 66. The decimal approximation of this value is 0.0757576. This method ensures precision by avoiding floating-point errors during the computation.

Bracelets (rotations and reflections identified)

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

Command line:

$ discrete-math solve bracelets beads=6 colours=2
bracelets = 13
necklaces = 14
  by: Bracelets (rotations and reflections identified)  (Burnside's lemma over the dihedral group)
  assumes: 1 <= n, k <= 60

Python:

import discrete_math_ai999x as m

a = m.solve("bracelets", beads="6", colours="2")
print(a.values or (a.value, a.unit))

Browser: open this capability on the model page and press Compute in your browser.

What this means: This calculation determines the count of unique circular patterns using Burnside's lemma on the dihedral group, where rotations and reflections are considered identical. Given 6 beads and 2 available colours, the model computes that there are 13 distinct bracelet configurations. It also reports 14 as the count when only rotational symmetry is applied.

Catalan numbers

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

Command line:

$ discrete-math solve catalan n=10
catalan = 16796
  by: Catalan numbers  (closed form binomial(2n, n)/(n + 1))
  assumes: 0 <= n <= 500; a convex polygon with s sides has C_(s-2) triangulations

Python:

import discrete_math_ai999x as m

a = m.solve("catalan", n="10")
print(a.values or (a.value, a.unit))

Browser: open this capability on the model page and press Compute in your browser.

What this means: This calculation determines the nth Catalan number using the closed form formula involving binomial coefficients. Given an input index of 10, the resulting value 16796 represents the count of specific combinatorial structures such as balanced parenthesizations, triangulations of a convex polygon, or full binary trees with a corresponding number of leaves.

Documentation

• Rust user guide — the command line, every capability with a command and what it printed: PDF · Markdown
• Python guide — every capability with a Python example: PDF · Markdown
• Desktop app & command line — downloads, install, ask and search, figures, offline use, checksums: https://www.ai999x.com/desktop-cli/
• Model page — compute in your browser, every capability explained: https://www.ai999x.com/models/discrete-math-ai999x/

Highlights

• Verified, not generated. Every answer is computed by a certified discrete math capability and checked (substituted back, dimension-checked or compared with an independent computation) before it is returned.
• Zero wrong answers by design. Seven explicit outcomes — SOLVED, NEEDS_INPUT, AMBIGUOUS, INVALID_INPUT, OUT_OF_SCOPE, UNRECOGNIZED_FORMAT, INTERNAL_ERROR — never a silent guess. Every one of its 538 documented answers is reproduced exactly on every tested platform.
• Plain-English questions and a guaranteed typed interface. ask() reads documented question forms; solve(capability_id, **inputs) always solves a supported task with valid inputs.
• Explains itself. Steps, formulas in LaTeX, units, assumptions and the model used, ready for notebooks, tutoring apps and homework checkers.
• Native and in the browser. Every capability also computes natively in Rust: the desktop app and the discrete-math command line for Windows and Linux, and WebAssembly on the model page — no Python, no network.
• Small and portable. Pure Python (sympy, mpmath); identical answers on Windows and Linux (Python 3.10, 3.11, 3.12, 3.13, 3.14).
• Coverage: number theory, modular arithmetic, combinatorics, graph structure, propositional logic and the mathematics of cryptography.

Model overview

Property	Value
Package	discrete-math-ai999x 1.0.3 (import discrete_math_ai999x)
Type	Deterministic neuro-symbolic discrete math engine (rule-based reading + certified symbolic capabilities)
Capabilities	99 certified procedures
Knowledge pack	version 1.0.0
Golden answers	538 documented answers, identical on every tested platform
Platforms tested	Windows (Python 3.13), Linux x86-64 (Python 3.10, 3.11, 3.12, 3.13, 3.14)
Runtime	CPU only, offline; no GPU, no network, no API key
License	Apache-2.0
Creator / engineer	Ibnul Jaif Farabi
Organization	AI999X

Python quick start

pip install discrete-math-ai999x
# or straight from this repository:
pip install https://huggingface.co/AI999X/discrete-math-ai999x/resolve/main/dist/discrete_math_ai999x-1.0.3-py3-none-any.whl

import discrete_math_ai999x as discrete_math

discrete_math.ask("Find the inverse of 3 modulo 11.").show()
# -> SOLVED — inverse = 4  (mod_inverse)
discrete_math.ask("Solve x \u2261 2 (mod 3), x \u2261 3 (mod 5), x \u2261 2 (mod 7).").show()
# -> SOLVED — x = 23, modulus = 105  (crt)
discrete_math.ask("How many derangements of 5 objects are there?").show()
# -> SOLVED — derangements = 44, probability = 0.366667  (derangements)
discrete_math.solve("chromatic_number", edges="A-B, B-C, C-A, C-D").show()
# -> SOLVED — chromatic_number = 3, colouring = {'A': 1, 'B': 2, 'C': 3, 'D': 1}  (chromatic_number)
discrete_math.ask("Is (p -> q) | (q -> p) a tautology?").show()
# -> SOLVED — tautology = 1, false_rows = 0, counterexample = None  (logic_tautology)
discrete_math.ask("Who created you?").message
# -> discrete-math-ai999x was created and engineered by Ibnul Jaif Farabi at AI999X.

The Python package also installs a Python command, discrete-math-ai999x "<question>"; for the native program use discrete-math (above). The outputs above were produced by running this exact code on discrete-math-ai999x 1.0.3.

Find the right capability, and draw it

discrete_math.search() finds which certified capability a question is about — across every AI999X model, so a question for another model points you to it. It runs ai999x-encoder, AI999X's own capability encoder (4.7M parameters, a 4.9 MB ONNX model, offline; the root model.safetensors of this repository): pip install "discrete-math-ai999x[search]". ask(question, suggest=True) adds the same pointers to a question it does not answer; an answer itself never changes.

import discrete_math_ai999x as discrete_math

discrete_math.search("Solve x^2 - 5x + 6 = 0", k=2)
# -> Roots of a quadratic equation (math-foundations-ai999x, 0.63); Roots of a cubic equation (math-foundations-ai999x, 0.59)

How every answer is verified

1. Reading — the question is turned into typed quantities (value, unit, kind, role) and one asked quantity; every stated number must be used or the question is refused.
2. Planning — only certified capabilities may answer; a capability applies only under the conditions the wording states (for example a pendulum, a liquid at rest, boiling).
3. Computing — exact symbolic or high-precision numeric evaluation.
4. Checking — dimensions, substitution back into the defining equation, and agreement between independent readings; any disagreement becomes a refusal, never a number.

Capabilities are certified before they ship: each must reproduce hand-worked reference cases, reject a deliberately wrong variant (a control), and leave every benchmark answer unchanged.

Python worked examples, with their steps

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

Modular multiplicative inverse · Modular arithmetic

Find the inverse of 3 modulo 11.

→ inverse = 4

Steps

• Modular multiplicative inverse: a = 3, m = 11 → inverse = 4

Chinese remainder theorem · Modular arithmetic

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

→ x = 23, modulus = 105

Steps

• Chinese remainder theorem: residues = [2, 3, 2], moduli = [3, 5, 7] → x = 23, modulus = 105

Derangements · Combinatorics

How many derangements of 5 objects are there?

→ derangements = 44, probability = 0.3666666667

Steps

• Derangements: n = 5 → derangements = 44, probability = 0.3666666667

Chromatic number of a small graph · Graph theory

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}

Steps

• Chromatic number of a small graph: edges = A-B, B-C, C-A, C-D → chromatic_number = 3, colouring = {'A': 1, 'B': 2, 'C': 3, 'D': 1}

Tautology test · Logic

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

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

Steps

• Tautology test: formula = (p -> q) | (q -> p) → tautology = True, false_rows = 0, counterexample = None

Affine cipher · Cryptography

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

→ result = IHHWVCSWFRCP

Steps

• Affine cipher: a = 5, b = 8, message = AFFINE CIPHER, mode = encrypt → result = IHHWVCSWFRCP

Figures

Every point was computed by discrete-math-ai999x.

A graph coloured with the fewest colours

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

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

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

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

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.

Capabilities

99 certified procedures. A few of them:

• Procedures: Affine cipher; Articulation points (cut vertices); Base (radix) conversion; Bell numbers; Bernoulli numbers; Bipartiteness test; Bracelets (rotations and reflections identified); Breadth-first search order; Bridges (cut edges); Caesar (shift) cipher; Carmichael function; Catalan numbers; Chinese remainder theorem; Chromatic number of a small graph; Clique number; Coefficient in a binomial expansion; Combinations C(n, k); Combinations with repetition (multisets); Connected components; Continued fraction of a rational number; Continued fraction of a square root; Contradiction test; Counting multiples by inclusion-exclusion; Cycle detection in a directed graph …

discrete_math_ai999x.templates() lists every question form ask() reads; the capability guide (PDF, every example executed) is included in this repository.

All 99 formulas

Show every formula, by topic

Combinatorics / basic counting

Combinations C(n, k)

$$\left(\genfrac{}{}{0px}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}\backslash binom\{n\}\{k\}\; =\; \backslash frac\{n!\}\{k!\backslash ,(n-k)!\}$$

Combinations with repetition (multisets)

$$\left(\text{\hspace{0.17em}⁣}\left(\genfrac{}{}{0px}{}{n}{k}\right)\text{\hspace{0.17em}⁣}\right)=\left(\genfrac{}{}{0px}{}{n+k-1}{k}\right)\backslash left(\backslash !\backslash binom\{n\}\{k\}\backslash !\backslash right)\; =\; \backslash binom\{n+k-1\}\{k\}$$

Distinct arrangements of the letters of a word

$$\frac{n!}{n_1!n_2!\cdots n_r!}\backslash frac\{n!\}\{n\_1!\backslash ,n\_2!\backslash cdots\; n\_r!\}$$

Lattice paths in a grid

$$\left(\genfrac{}{}{0px}{}{m+n}{m}\right)\backslash binom\{m+n\}\{m\}$$

Multinomial coefficient

$$\left(\genfrac{}{}{0px}{}{n}{k_1,\dots ,k_m}\right)=\frac{n!}{k_1!\cdots k_m!}\backslash binom\{n\}\{k\_1,\backslash dots,k\_m\}\; =\; \backslash frac\{n!\}\{k\_1!\backslash cdots\; k\_m!\}$$

Permutations P(n, k)

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

Sequences with repetition (n^k)

$$n^{k}n^k$$

Combinatorics / binomial theorem

Coefficient in a binomial expansion

$$(ax+b{)}^n=\sum _{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)a^k{b}^{n-k}{x}^k(ax+b)^n\; =\; \backslash sum\_\{k=0\}^\{n\}\; \backslash binom\{n\}\{k\}\; a^k\; b^\{n-k\}\; x^k$$

Combinatorics / counting under symmetry

Bracelets (rotations and reflections identified)

Necklaces (rotations identified)

$$N(n,k)=\frac{1}{n}\sum _{d\mid n}\phi (d)k^{n\mathrm{/}d}N(n,k)\; =\; \backslash frac\{1\}\{n\}\backslash sum\_\{d\; \backslash mid\; n\}\; \backslash varphi(d)\backslash ,\; k^\{n/d\}$$

Combinatorics / distributions

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

$$\mathrm{\#}\{x_i\ge 0,\sum x_i=n\}=\left(\genfrac{}{}{0px}{}{n+k-1}{k-1}\right),{\sum }_j(-1{)}^j\left(\genfrac{}{}{0px}{}{k}{j}\right)\left(\genfrac{}{}{0px}{}{n-j(c+1)+k-1}{k-1}\right)\backslash \#\backslash \{x\_i\; \backslash ge\; 0,\; \backslash textstyle\backslash sum\; x\_i\; =\; n\backslash \}\; =\; \backslash binom\{n+k-1\}\{k-1\},\backslash quad\; \backslash sum\_j\; (-1)^j\; \backslash binom\{k\}\{j\}\backslash binom\{n\; -\; j(c+1)\; +\; k-1\}\{k-1\}$$

Combinatorics / inclusion-exclusion

Counting multiples by inclusion-exclusion

$$\mid \bigcup _i{A}_i\mid =\sum _{\mathrm{\varnothing }\mathrm{\ne }S}(-1{)}^{\mathrm{\mid }S\mathrm{\mid }+1}\lfloor \frac{n}{\mathrm{lcm}(S)}\rfloor \backslash Big\backslash vert\; \backslash bigcup\_i\; A\_i\backslash Big\backslash vert\; =\; \backslash sum\_\{\backslash emptyset\; \backslash ne\; S\}\; (-1)^\{\backslash vert\; S\backslash vert\; +1\}\; \backslash left\backslash lfloor\; \backslash frac\{n\}\{\backslash operatorname\{lcm\}(S)\}\; \backslash right\backslash rfloor$$

Derangements

$$!n=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}=(n-1)(!(n-1)+!(n-2))!n\; =\; n!\backslash sum\_\{k=0\}^\{n\}\backslash frac\{(-1)^k\}\{k!\}\; =\; (n-1)\backslash big(!(n-1)\; +\; !(n-2)\backslash big)$$

Combinatorics / integer partitions

Integer partitions p(n)

$$p(n)=\sum _{k\mathrm{\ne }0}(-1{)}^{k+1}p\text{\hspace{0.17em}⁣}(n-\frac{k(3k-1)}{2})p(n)\; =\; \backslash sum\_\{k\; \backslash ne\; 0\}\; (-1)^\{k+1\}\backslash ,\; p\backslash !\backslash left(n\; -\; \backslash tfrac\{k(3k-1)\}\{2\}\backslash right)$$

Partitions into distinct parts

$$\sum _{n}q(n)x^n=\prod _{k\ge 1}(1+x^k)=\prod _{k\ge 1}\frac{1}{1-x^{2k-1}}\backslash sum\_n\; q(n)\; x^n\; =\; \backslash prod\_\{k\; \backslash ge\; 1\}\; (1\; +\; x^k)\; =\; \backslash prod\_\{k\; \backslash ge\; 1\}\; \backslash frac\{1\}\{1\; -\; x^\{2k-1\}\}$$

Partitions into exactly k parts

$$p(n,k)=p(n-1,k-1)+p(n-k,k)p(n,k)\; =\; p(n-1,k-1)\; +\; p(n-k,k)$$

Combinatorics / permutations and cycles

Stirling numbers of the first kind

$$c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1),x^{\bar{n}}=\sum _{k}c(n,k)x^{k}c(n,k)\; =\; (n-1)\backslash ,c(n-1,k)\; +\; c(n-1,k-1),\backslash quad\; x^\{\backslash overline\; n\}\; =\; \backslash sum\_k\; c(n,k)\backslash ,x^k$$

Combinatorics / pigeonhole principle

Pigeonhole principle: guaranteed load

$$\underset{i}{\max }{x}_i\ge \lceil \frac{n}{k}\rceil \backslash max\_i\; x\_i\; \backslash ge\; \backslash left\backslash lceil\; \backslash frac\{n\}\{k\}\; \backslash right\backslash rceil$$

Pigeonhole principle: objects needed for a guarantee

$$N=k(r-1)+1N\; =\; k(r-1)\; +\; 1$$

Combinatorics / recurrences

Fibonacci numbers

$$F_n=F_{n-1}+F_{n-2},F_0=0,F_1=1F\_n\; =\; F\_\{n-1\}\; +\; F\_\{n-2\},\backslash \; F\_0\; =\; 0,\backslash \; F\_1\; =\; 1$$

Lucas numbers

$$L_n=L_{n-1}+L_{n-2},L_0=2,L_1=1L\_n\; =\; L\_\{n-1\}\; +\; L\_\{n-2\},\backslash \; L\_0\; =\; 2,\backslash \; L\_1\; =\; 1$$

Combinatorics / recursive counting

Catalan numbers

$$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0px}{}{2n}{n}\right)C\_n\; =\; \backslash frac\{1\}\{n+1\}\backslash binom\{2n\}\{n\}$$

Combinatorics / set partitions

Bell numbers

$$B_{n+1}=\sum _{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)B_{k}B\_\{n+1\}\; =\; \backslash sum\_\{k=0\}^\{n\}\; \backslash binom\{n\}\{k\}\; B\_k$$

Stirling numbers of the second kind

$$S(n,k)=kS(n-1,k)+S(n-1,k-1)=\frac{1}{k!}\sum _{j=0}^k(-1{)}^j\left(\genfrac{}{}{0px}{}{k}{j}\right)(k-j{)}^{n}S(n,k)\; =\; k\backslash ,S(n-1,k)\; +\; S(n-1,k-1)\; =\; \backslash frac\{1\}\{k!\}\backslash sum\_\{j=0\}^\{k\}\; (-1)^j\; \backslash binom\{k\}\{j\}\; (k-j)^n$$

Combinatorics / special numbers

Bernoulli numbers

$$\sum _{k=0}^m\left(\genfrac{}{}{0px}{}{m+1}{k}\right)B_k=0,B_0=1\backslash sum\_\{k=0\}^\{m\}\; \backslash binom\{m+1\}\{k\}\; B\_k\; =\; 0,\backslash quad\; B\_0\; =\; 1$$

Cryptography / RSA

RSA decryption

$$m=c^{d}nm\; =\; c^d\; \backslash bmod\; n$$

RSA decryption from p, q and e (CRT)

$$m=m_q+q(q^{-1}(m_p-m_q)p)m\; =\; m\_q\; +\; q\backslash ,\backslash big(q^\{-1\}(m\_p\; -\; m\_q)\; \backslash bmod\; p\backslash big)$$

RSA encryption

$$c=m^{e}nc\; =\; m^e\; \backslash bmod\; n$$

RSA key from p, q and e

$$n=pq,\phi =(p-1)(q-1),d\equiv e^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}\phi )n\; =\; pq,\backslash \; \backslash varphi\; =\; (p-1)(q-1),\backslash \; d\; \backslash equiv\; e^\{-1\}\; \backslash pmod\{\backslash varphi\}$$

Cryptography / classical ciphers

Affine cipher

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

Caesar (shift) cipher

$$E(x)=(x+k)26E(x)\; =\; (x\; +\; k)\; \backslash bmod\; 26$$

Vigenère cipher

$$c_j=(m_j+k_{j\mathrm{\mid }k\mathrm{\mid }})26c\_j\; =\; (m\_j\; +\; k\_\{j\; \backslash bmod\; \backslash vert\; k\backslash vert\; \})\; \backslash bmod\; 26$$

Cryptography / key exchange

Diffie-Hellman key exchange

$$s=B^{a}p=A^{b}p=g^{ab}ps\; =\; B^a\; \backslash bmod\; p\; =\; A^b\; \backslash bmod\; p\; =\; g^\{ab\}\; \backslash bmod\; p$$

Cryptography / public-key encryption

ElGamal encryption

$$c_1=g^k,c_2=m{h}^k(\mathrm{m}\mathrm{o}\mathrm{d}p),m=c_2{c}_1^{-x}c\_1\; =\; g^k,\backslash \; c\_2\; =\; m\backslash ,h^k\; \backslash pmod\; p,\backslash quad\; m\; =\; c\_2\backslash ,c\_1^\{-x\}$$

Graph theory / Euler and Hamilton

Eulerian circuits and paths

$$\text{circuit}⟺\text{connected}\wedge \mathrm{\forall }v:2\mid \mathrm{deg}v\backslash text\{circuit\}\; \backslash iff\; \backslash text\{connected\}\; \backslash wedge\; \backslash forall\; v:\backslash \; 2\; \backslash mid\; \backslash deg\; v$$

Hamiltonian cycle of a small graph

$$v_1{v}_2\cdots v_n{v}_1,\{v_i\}=Vv\_1\; v\_2\; \backslash cdots\; v\_n\; v\_1,\backslash \; \backslash \{v\_i\backslash \}\; =\; V$$

Graph theory / adjacency matrices

Number of walks of a given length

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

Graph theory / basic structure

Vertex degrees and degree sequence

$$\sum _v\mathrm{deg}v=2\mathrm{\mid }E\mathrm{\mid }\backslash sum\_v\; \backslash deg\; v\; =\; 2\backslash vert\; E\backslash vert$$

Graph theory / cliques and independent sets

Clique number

$$\omega (G)=\max \{\mathrm{\mid }K\mathrm{\mid }:K\text{ complete}\}\backslash omega(G)\; =\; \backslash max\backslash \{\backslash vert\; K\backslash vert\; :\; K\; \backslash text\{\; complete\}\backslash \}$$

Independence number

$$\alpha (G)=\omega (\bar{G})\backslash alpha(G)\; =\; \backslash omega(\backslash overline\; G)$$

Graph theory / colouring

Bipartiteness test

$$G\text{ bipartite}⟺G\text{ has no odd cycle}G\; \backslash text\{\; bipartite\}\; \backslash iff\; G\; \backslash text\{\; has\; no\; odd\; cycle\}$$

Chromatic number of a small graph

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

Graph theory / connectivity

Articulation points (cut vertices)

$$u\text{ cut vertex}⟺\mathrm{\exists }\text{ child }v:\mathrm{l}\mathrm{o}\mathrm{w}(v)\ge \mathrm{d}\mathrm{i}\mathrm{s}\mathrm{c}(u)u\; \backslash text\{\; cut\; vertex\}\; \backslash iff\; \backslash exists\; \backslash text\{\; child\; \}\; v:\backslash \; \backslash mathrm\{low\}(v)\; \backslash ge\; \backslash mathrm\{disc\}(u)$$

Bridges (cut edges)

$$(u,v)\text{ bridge}⟺\mathrm{l}\mathrm{o}\mathrm{w}(v)>\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{c}(u)(u,v)\; \backslash text\{\; bridge\}\; \backslash iff\; \backslash mathrm\{low\}(v)\; >\; \backslash mathrm\{disc\}(u)$$

Connected components

$$V=C_1\bigsqcup \cdots \bigsqcup C_{c}V\; =\; C\_1\; \backslash sqcup\; \backslash dots\; \backslash sqcup\; C\_c$$

Strongly connected components

$$u\sim v⟺u⇝v\wedge v⇝uu\; \backslash sim\; v\; \backslash iff\; u\; \backslash leadsto\; v\; \backslash wedge\; v\; \backslash leadsto\; u$$

Graph theory / cycles

Cycles in an undirected graph (cyclomatic number)

$$\mu (G)=\mathrm{\mid }E\mathrm{\mid }-\mathrm{\mid }V\mathrm{\mid }+c(G)\backslash mu(G)\; =\; \backslash vert\; E\backslash vert\; -\; \backslash vert\; V\backslash vert\; +\; c(G)$$

Girth (shortest cycle length)

$$g(G)=\min \{\mathrm{\mid }C\mathrm{\mid }:C\text{ a cycle of }G\}g(G)\; =\; \backslash min\backslash \{\backslash vert\; C\backslash vert\; :\; C\; \backslash text\{\; a\; cycle\; of\; \}\; G\backslash \}$$

Graph theory / degree sequences

Graphical degree sequence

$$\sum _{i\le k}{d}_i\le k(k-1)+\sum _{i>k}\min (d_i,k)\mathrm{\forall }k,\sum d_i\text{ even}\backslash sum\_\{i\; \backslash le\; k\}\; d\_i\; \backslash le\; k(k-1)\; +\; \backslash sum\_\{i\; >\; k\}\; \backslash min(d\_i,\; k)\backslash \; \backslash \; \backslash forall\; k,\backslash quad\; \backslash textstyle\backslash sum\; d\_i\; \backslash text\{\; even\}$$

Graph theory / directed acyclic graphs

Cycle detection in a directed graph

$$G\text{ acyclic}⟺\text{a topological order exists}G\; \backslash text\{\; acyclic\}\; \backslash iff\; \backslash text\{a\; topological\; order\; exists\}$$

Topological sort

Graph theory / distances

Diameter, radius and center

$$\mathrm{diam}G=\underset{v}{\max }e(v),\mathrm{rad}G=\underset{v}{\min }e(v)\backslash operatorname\{diam\}\; G\; =\; \backslash max\_v\; e(v),\backslash \; \backslash operatorname\{rad\}\; G\; =\; \backslash min\_v\; e(v)$$

Graph theory / graph search

Breadth-first search order

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

Depth-first search order

$$\mathrm{v}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{t}(u):\text{ mark }u;\mathrm{\forall }v\in N(u)\text{ ascending, unmarked: }\mathrm{v}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{t}(v)\backslash mathrm\{visit\}(u):\backslash \; \backslash text\{mark\; \}\; u;\backslash \; \backslash forall\; v\; \backslash in\; N(u)\; \backslash text\{\; ascending,\; unmarked:\; \}\; \backslash mathrm\{visit\}(v)$$

Graph theory / subgraph counts

Number of triangles

$$t(G)=\frac{1}{6}\mathrm{tr}(A^3)t(G)\; =\; \backslash tfrac\{1\}\{6\}\backslash operatorname\{tr\}(A^3)$$

Graph theory / trees

Number of spanning trees (Kirchhoff)

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

Prüfer code of a labelled tree

$$(a_1,\dots ,a_{n-2}),a_i=\text{neighbour of the smallest leaf}(a\_1,\; \backslash dots,\; a\_\{n-2\}),\backslash \; a\_i\; =\; \backslash text\{neighbour\; of\; the\; smallest\; leaf\}$$

Tree from a Prüfer code

$$\mathrm{deg}(v)=1+\mathrm{\#}\{i:a_i=v\}\backslash deg(v)\; =\; 1\; +\; \backslash \#\backslash \{i\; :\; a\_i\; =\; v\backslash \}$$

Tree test

$$T\text{ tree}⟺T\text{ connected}\wedge \mathrm{\mid }E\mathrm{\mid }=\mathrm{\mid }V\mathrm{\mid }-1T\; \backslash text\{\; tree\}\; \backslash iff\; T\; \backslash text\{\; connected\}\; \backslash wedge\; \backslash vert\; E\backslash vert\; =\; \backslash vert\; V\backslash vert\; -\; 1$$

Logic / Boolean minimization

Minimal product of sums (CNF)

$$f=\prod _{\text{cover of }\bar{f}}\sum {\bar{\mathrm{\ell }}}_{i}f\; =\; \backslash prod\_\{\backslash text\{cover\; of\; \}\; \backslash bar\; f\}\; \backslash sum\; \backslash bar\backslash ell\_i$$

Minimal sum of products (DNF)

$$f=\sum _{\text{cover}}\prod {\mathrm{\ell }}_{i}f\; =\; \backslash sum\_\{\backslash text\{cover\}\}\; \backslash prod\; \backslash ell\_i$$

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

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

Logic / propositional logic

Evaluate a propositional formula

$$p\to q\equiv \mathrm{\neg }p\vee qp\; \backslash to\; q\; \backslash equiv\; \backslash neg\; p\; \backslash vee\; q$$

Logical equivalence of two formulas

$$f\equiv g⟺\models f\leftrightarrow gf\; \backslash equiv\; g\; \backslash iff\; \backslash models\; f\; \backslash leftrightarrow\; g$$

Truth table and minterms

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

Logic / satisfiability

Contradiction test

$$\mathrm{\forall }v:f(v)=0\backslash forall\; v:\backslash \; f(v)\; =\; 0$$

Satisfiability of a propositional formula

$$\mathrm{\exists }v:f(v)=1\backslash exists\; v:\backslash \; f(v)\; =\; 1$$

Logic / validity

Tautology test

$$\models f⟺\mathrm{\forall }v:f(v)=1\backslash models\; f\; \backslash iff\; \backslash forall\; v:\backslash \; f(v)\; =\; 1$$

Modular arithmetic / congruences

Chinese remainder theorem

$$x\equiv r_i(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i),i=\mathrm{1..}k\Rightarrow x\mathrm{lcm}(m_1,\dots ,m_k)x\; \backslash equiv\; r\_i\; \backslash pmod\{m\_i\},\backslash \; i=1..k\; \backslash ;\backslash Rightarrow\backslash ;\; x\; \backslash bmod\; \backslash operatorname\{lcm\}(m\_1,\backslash dots,m\_k)$$

Linear congruence ax ≡ b (mod m)

$$ax\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)⟺x\equiv \frac{b}{g}{\left(\frac{a}{g}\right)}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}\frac{m}{g}),g=\gcd (a,m)\mid bax\backslash equiv\; b\; \backslash pmod\; m\; \backslash iff\; x\; \backslash equiv\; \backslash tfrac\{b\}\{g\}\backslash left(\backslash tfrac\{a\}\{g\}\backslash right)^\{-1\}\; \backslash pmod\{\backslash tfrac\{m\}\{g\}\},\backslash \; g=\backslash gcd(a,m)\backslash mid\; b$$

Modular arithmetic / discrete logarithms

Discrete logarithm

$$g^x\equiv h(\mathrm{m}\mathrm{o}\mathrm{d}m),x=i\lceil \sqrt{m}\rceil +jg^\{x\}\; \backslash equiv\; h\; \backslash pmod\; m,\backslash quad\; x\; =\; i\backslash lceil\backslash sqrt\; m\backslash rceil\; +\; j$$

Modular arithmetic / inverses

Modular multiplicative inverse

$$ax\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)a\; x\; \backslash equiv\; 1\; \backslash pmod\; m$$

Modular arithmetic / orders and primitive roots

Multiplicative order

$${\mathrm{ord}}_n(a)=\min \{k\ge 1:a^k\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)\},{\mathrm{ord}}_n(a)\mid \lambda (n)\backslash operatorname\{ord\}\_n(a)\; =\; \backslash min\backslash \{k\; \backslash ge\; 1\; :\; a^k\; \backslash equiv\; 1\; \backslash pmod\; n\backslash \},\backslash \; \backslash operatorname\{ord\}\_n(a)\; \backslash mid\; \backslash lambda(n)$$

Smallest primitive root modulo a prime

$$g^{(p-1)\mathrm{/}q}\equiv ̸1(\mathrm{m}\mathrm{o}\mathrm{d}p)\mathrm{\forall }q\mid p-1g^\{(p-1)/q\}\; \backslash not\backslash equiv\; 1\; \backslash pmod\; p\; \backslash \; \backslash \; \backslash forall\; q\; \backslash mid\; p-1$$

Modular arithmetic / powers

Modular exponentiation

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

Modular arithmetic / residues

Remainder modulo m (Euclidean division)

Number representations / binary arithmetic

Two's complement representation

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

Number representations / positional systems

Base (radix) conversion

$$(d_k\dots d_0{)}_b=\sum _i{d}_i{b}^i(d\_k\; \backslash dots\; d\_0)\_b\; =\; \backslash sum\_i\; d\_i\backslash ,\; b^i$$

Number theory / Diophantine equations

Linear Diophantine equation ax + by = c

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

Pell's equation (fundamental solution)

$$x^2-d{y}^2=1,\frac{x}{y}=[a_0;a_1,\dots ,a_{k-1}]x^2\; -\; d\backslash ,y^2\; =\; 1,\backslash quad\; \backslash frac\{x\}\{y\}\; =\; [a\_0;\; a\_1,\; \backslash dots,\; a\_\{k-1\}]$$

Number theory / arithmetic functions

Carmichael function

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

Divisors, divisor count and divisor sum

$$\tau (n)=\prod (e_i+1),\sigma (n)=\prod \frac{p_i^{e_i+1}-1}{p_i-1}\backslash tau(n)=\backslash prod\; (e\_i+1),\backslash qquad\; \backslash sigma(n)=\backslash prod\; \backslash frac\{p\_i^\{e\_i+1\}-1\}\{p\_i-1\}$$

Euler's totient function

$$\phi (n)=n\prod _{p\mid n}(1-\frac{1}{p})\backslash varphi(n)\; =\; n\; \backslash prod\_\{p\; \backslash mid\; n\}\backslash left(1\; -\; \backslash frac\{1\}\{p\}\backslash right)$$

Möbius function

Number theory / continued fractions

Continued fraction of a rational number

$$\frac{p}{q}=a_0+{\displaystyle \frac{1}{a_1+{\displaystyle \frac{1}{\ddots +{\displaystyle \frac{1}{a_n}}}}}}\backslash frac\{p\}\{q\}\; =\; a\_0\; +\; \backslash cfrac\{1\}\{a\_1\; +\; \backslash cfrac\{1\}\{\backslash ddots\; +\; \backslash cfrac\{1\}\{a\_n\}\}\}$$

Continued fraction of a square root

$$\sqrt{d}=[a_0;\overline{a_1,\dots ,a_{k-1},2a_0}]\backslash sqrt\; d\; =\; [a\_0;\; \backslash overline\{a\_1,\; \backslash dots,\; a\_\{k-1\},\; 2a\_0\}]$$

Number theory / divisibility

Extended Euclidean algorithm (Bezout coefficients)

$$ax+by=\gcd (a,b)a\; x\; +\; b\; y\; =\; \backslash gcd(a,\; b)$$

Greatest common divisor and least common multiple

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

Number theory / primes

Next prime

$$\min \{p>n:p\text{ prime}\}\backslash min\backslash \{p\; >\; n\; :\; p\; \backslash text\{\; prime\}\backslash \}$$

Previous prime

Primality test

$$a^d\equiv 1\text{ or }{a}^{2^{r}d}\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}n)\text{ for every base }aa^\{d\}\backslash equiv\; 1\; \backslash \; \backslash text\{or\}\backslash \; a^\{2^r\; d\}\backslash equiv\; -1\; \backslash pmod\; n\; \backslash text\{\; for\; every\; base\; \}\; a$$

Prime factorization

$$n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}n\; =\; p\_1^\{e\_1\}\; p\_2^\{e\_2\}\; \backslash cdots\; p\_k^\{e\_k\}$$

Prime-counting function

$$\pi (x)=\mathrm{\#}\{p\le x:p\text{ prime}\}\backslash pi(x)\; =\; \backslash \#\backslash \{p\; \backslash le\; x\; :\; p\; \backslash text\{\; prime\}\backslash \}$$

The n-th prime

Number theory / quadratic residues

Jacobi symbol

$$\left(\frac{a}{n}\right)=\prod _i{\left(\frac{a}{p_i}\right)}^{e_i},n=\prod p_i^{e_i}\backslash left(\backslash frac\{a\}\{n\}\backslash right)\; =\; \backslash prod\_i\; \backslash left(\backslash frac\{a\}\{p\_i\}\backslash right)^\{e\_i\},\backslash quad\; n\; =\; \backslash prod\; p\_i^\{e\_i\}$$

Legendre symbol

$$\left(\frac{a}{p}\right)\equiv a^{(p-1)\mathrm{/}2}(\mathrm{m}\mathrm{o}\mathrm{d}p)\backslash left(\backslash frac\{a\}\{p\}\backslash right)\; \backslash equiv\; a^\{(p-1)/2\}\; \backslash pmod\; p$$

Square roots modulo a prime

$$x^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p),a^{(p-1)\mathrm{/}2}\equiv 1x^2\; \backslash equiv\; a\; \backslash pmod\; p,\backslash quad\; a^\{(p-1)/2\}\; \backslash equiv\; 1$$

Number theory / squares

Integer square root and perfect squares

Number theory / sums of squares

Sums of two squares

$$r_2(n)=4(d_1(n)-d_3(n))r\_2(n)\; =\; 4\backslash big(d\_1(n)\; -\; d\_3(n)\backslash big)$$

Out of scope

• Open-ended explanation, essay writing or tutoring dialogue: it is a solver, not a chatbot.
• Questions outside its certified discrete math capabilities, and any question whose stated numbers it cannot all use — it refuses with the reason instead.
• High-stakes engineering, medical or legal decisions without independent review.

Limitations

• It answers what its certified capabilities cover (number theory, modular arithmetic, combinatorics, graph structure, propositional logic and the mathematics of cryptography); anything else is refused with a reason.
• ask() reads documented question forms and common phrasings; unusual wording may be refused — use solve() for guaranteed results.
• Results are as correct as the certified relations and their stated conditions; a certified relation is a checked model, not a claim about every physical situation.

Citation

@software{discrete_math_ai999x_1_0_3,
  title  = {discrete-math-ai999x: an offline, verified discrete math solver},
  author = {Farabi, Ibnul Jaif}, organization = {AI999X},
  year   = {2026}, version = {1.0.3},
  url    = {https://huggingface.co/AI999X/discrete-math-ai999x}
}

Contact

Questions, bug reports and requests: open a discussion on https://huggingface.co/AI999X/discrete-math-ai999x/discussions or visit https://ai999x.com.

Support the project

discrete-math-ai999x is free and open source. If it helps you, you can support further development on Buy Me a Coffee.

Created and engineered by Ibnul Jaif Farabi · AI999X · ai999x.com