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.
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¶
- Declare n and B.
- Factor n or certify bounds on its prime divisors.
- Find the largest prime factor.
- Compare it with B.
- Record the factor-base exponent vector where relevant.
- For sampled integers up to x, estimate \(\Psi(x,B)\) using an appropriate regime.
- Balance smoothness probability against factor-base and linear-algebra costs.
- 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.
Instantiates / Related Primes¶
This entry is a kind of Natural Number.
Natural Number is the broader abstraction this entry instantiates. Factorization, Threshold, Composition, Sparsity, Counting, and Complexity are related.
Relationships to Other Abstractions¶
Current abstraction Smooth Number Domain-specific
Parents (1) — outgoing typed relations
-
Smooth Number is a kind of Natural Number Domain-specific
Natural Number is the broader abstraction this entry instantiates.Factorization, Threshold, Composition, Sparsity, Counting, and Complexity are related.
Hierarchy paths (8) — routes to 6 parentless roots
- Smooth Number → is a kind of Natural Number → is a kind of Discreteness → is a kind of Boundary
- Smooth Number → is a kind of Natural Number → includes Well-Foundedness (Well-Ordering) → presupposes Iteration
- Smooth Number → is a kind of Natural Number → includes Well-Foundedness (Well-Ordering) → presupposes Recurrence
- Smooth Number → is a kind of Natural Number → is a kind of Discreteness → presupposes Set and Membership
- Smooth Number → is a kind of Natural Number → includes Well-Foundedness (Well-Ordering) → presupposes Order → presupposes Comparison
- Smooth Number → is a kind of Natural Number → includes Well-Foundedness (Well-Ordering) → is a decomposition of Termination Condition → presupposes Iteration
- Smooth Number → is a kind of Natural Number → includes Well-Foundedness (Well-Ordering) → presupposes Order → presupposes Relation
- Smooth Number → is a kind of Natural Number → includes Well-Foundedness (Well-Ordering) → presupposes Order → presupposes Set and Membership
Neighborhood in Abstraction Space¶
Smooth Number sits in a sparse region of the domain-specific corpus (83rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Integer Properties & Number-Theoretic Sets (15 abstractions)
Nearest neighbors
- Giuga Number — 0.83
- Fundamental Theorem of Arithmetic — 0.82
- Refactorable number — 0.82
- Probable prime — 0.82
- Descartes Number — 0.81
Computed from structural-signature embeddings · 2026-10-25
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.not authoritative registry ↩ Show verification details
Supported in partVerified against the work's full text
The survey's introduction frames smooth numbers across computational and analytic number theory, but the fetched passage does not itself itemize the five applied areas listed.
“For those primarily interested in analytic problems, I have tried to give concise introductions to simplified versions of various key computational number theory algorithms, and to highlight applications and open counting questions.”
[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 ↩