Skip to content

Smooth Number

A positive integer is B-smooth when every prime divisor is at most the declared bound B, making its factorization lie entirely within a small-prime factor base.

Version
v2 · 2026-09-06 · History
Domain-specific #
2797
Origin domain
mathematics
Subdomain
number theory
Aliases
Friable number, B-smooth integer, Y-smooth number

Core Idea

A positive integer \(n\) is B-smooth if every prime divisor of \(n\) is at most \(B\); equivalently, its largest prime factor \(P^+(n)\le B\), with \(1\) included by convention. Smoothness is relative to the stated bound. The counting function \(\Psi(x,B)\) records B-smooth integers not exceeding \(x\).[1]

The recognition invariant is positive integer + complete prime factorization constraint + explicit upper bound on every prime factor.

Structural Signature

  • A positive integer \(n\).
  • A real/integer bound \(B\ge2\) by common convention.
  • Unique prime factorization.
  • Every prime divisor at most \(B\).
  • Largest-prime-factor test.
  • Bound monotonicity: B-smooth implies C-smooth for \(C\ge B\).
  • Missing small primes permitted.
  • Exponents unrestricted.
  • Unit \(1\) vacuously smooth.
  • Factor-base representation.
  • Counting function \(\Psi(x,B)\).
  • Density controlled by the ratio of logarithms in asymptotic regimes.
  • Algorithmic usefulness balanced against rarity.

What It Is Not

It is not a highly composite number, a number with many divisors, or a number whose prime factors occur with small exponents. A huge power of two is 2-smooth. Conversely, a squarefree integer containing one large prime is not B-smooth below that prime.[2]

It is not “smooth” in calculus. The term “friable” is a synonym intended to avoid that homonym.

Scope of Application

Smooth numbers drive integer-factorization and discrete-logarithm algorithms because relations over a fixed factor base can be combined algebraically. They also appear in primality proving, cryptographic parameter assessment, fast Fourier transform sizes, scheduling/combinatorial enumeration, and analytic number theory.[3]

Algorithm design balances a larger factor base, which increases the probability that sampled values are smooth, against more costly relation collection and linear algebra.

Clarity

Always attach the bound. “Smooth” without B is incomplete. B need not be prime; the condition uses the largest prime not exceeding it. The factor B itself need not divide n.

Power-smoothness, semismoothness (allowing one controlled larger factor), and smoothness relative to ideals or polynomials are related but distinct definitions.

Manages Complexity

Smoothness compresses a full factorization into a one-threshold predicate while retaining an exponent vector over a small factor base. Algorithms exploit that vector representation to turn multiplicative relations into linear algebra.

Abstract Reasoning

  1. Declare n and B.
  2. Factor n or certify bounds on its prime divisors.
  3. Find the largest prime factor.
  4. Compare it with B.
  5. Record the factor-base exponent vector where relevant.
  6. For sampled integers up to x, estimate \(\Psi(x,B)\) using an appropriate regime.
  7. Balance smoothness probability against factor-base and linear-algebra costs.
  8. Separate smooth, semismooth, and power-smooth variants.

Knowledge Transfer

The portable structure is membership determined by whether every atomic factor lies within an allowed vocabulary. The proposed immediate parent is Natural Number.

Examples

5-smooth. \(1620=2^2\cdot3^4\cdot5\) is 5-smooth.

Not 7-smooth. \(702=2\cdot3^3\cdot13\) fails because 13 exceeds 7.

Unit. One is B-smooth for every usual B because it has no prime divisors.

Structural Tensions

  • Larger factor base versus relation-processing cost.
  • Simple predicate versus hard factorization evidence.
  • Greater smoothness probability versus weaker selectivity.
  • Exact finite counts versus asymptotic estimates.
  • Number-theoretic rarity versus algorithmic leverage.
  • Terminological smoothness versus analytic smoothness.

Structural–Framed Character

Bounded atomic vocabulary, monotonicity, and factor representation are structural. Prime divisors, factor bases, Dickman-type asymptotics, and cryptographic algorithms are number-theoretic frame.

Structural Core vs. Domain Accent

The portable core is an object composed only from allowed atoms. The constitutive accent is unique prime factorization and the numeric bound on prime divisors.

Natural Number is the proposed immediate parent. Factorization, Threshold, Composition, Sparsity, Counting, and Complexity are related.

The prospective queue contains one strict edge to domain_specific:natural_number. No live DAG mutation is authorized.

Relationships to Other Abstractions

Local relationship map for Smooth NumberParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Smooth NumberDOMAINDomain-specific abstraction: Natural Number — is a kind ofNatural NumberDOMAIN

Current abstraction Smooth Number Domain-specific

Parents (1) — more general patterns this builds on

  • Smooth Number is a kind of Natural Number Domain-specific

    Natural Number is the proposed immediate parent.

Hierarchy paths (8) — routes to 6 parentless roots

Neighborhood in Abstraction Space

Smooth Number sits in a sparse region of the domain-specific corpus (82nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Additive Number Theory & Series Tests (6 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With

  • Highly composite number.
  • Squarefree number.
  • Number with small prime exponents.
  • Semismooth number.
  • Smooth function.
  • Smoothness without a declared B.

References

[1] Gérald Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, 3rd ed., American Mathematical Society, 2015. registry ↩

[2] Adolf Hildebrand and Gérald Tenenbaum, “Integers without Large Prime Factors”, Journal de Théorie des Nombres de Bordeaux 5 (1993): 411–484. registry ↩

[3] Andrew Granville, “Smooth Numbers: Computational Number Theory and Beyond,” in Algorithmic Number Theory, MSRI Publications 44, 2008. registry ↩

[4] N. G. de Bruijn, “On the Number of Positive Integers ≤ x and Free of Prime Factors > y,” Indagationes Mathematicae 13 (1951): 50–60. registry ↩