Количество делителей

Counting divisors is as old as arithmetic, but the counting function became an object of study in the nineteenth century. Peter Gustav Lejeune Dirichlet asked, in 1849, not what d(n) is for a particular n — that falls straight out of the prime factorisation — but what it is on average. His answer introduced a technique still taught as the hyperbola method: adding up d(n) for all n up to x amounts to counting lattice points under the hyperbola uv = x, and each point can be paired with its mirror image across the diagonal, which halves the work. He obtained x·log x + (2γ − 1)x, where γ is the Euler–Mascheroni constant, with an error term no larger than a constant times √x.

Pinning that error term down is the Dirichlet divisor problem, and it is still open. Georgy Voronoy improved the exponent from 1/2 to 1/3 in 1903. In 1915 G. H. Hardy and Edmund Landau showed, independently, that the exponent can never be pushed below 1/4 — which is where nearly everyone expects the truth to lie. The best published upper bound is Martin Huxley's 131/416 ≈ 0.3149, from 2003. More than a century of effort has closed well under a tenth of the gap.

The other natural question is how large d(n) can get. Severin Wigert settled the maximal order in 1907: d(n) is at most 2^((1+o(1))·log n / log log n). Ramanujan recovered and sharpened that result in his 1915 paper on highly composite numbers, which are precisely the record-holders for divisor count.

The notation never converged. d(n), τ(n) and σ₀(n) all denote the same function — the last because counting divisors is the same as summing their zeroth powers.

Ключевые свойства

• If n = p₁^a₁ · p₂^a₂ · … then d(n) = (a₁+1)(a₂+1)…, so the count depends only on the exponents, never on which primes appear.
• d is multiplicative: d(mn) = d(m)·d(n) whenever gcd(m, n) = 1.
• d(n) is odd exactly when n is a perfect square, because divisors pair up as d and n/d except when d = √n.
• d(n) = 1 only for n = 1, and d(n) = 2 exactly when n is prime.
• Dirichlet (1849): the divisor counts up to x total x·log x + (2γ − 1)x + O(√x), so a number near x has about log x divisors on average.
• The Dirichlet series of d is the square of the Riemann zeta function: Σ d(n)/nˢ = ζ(s)² for Re(s) > 1.
• 720720 is the smallest number with 240 divisors, and no number below one million has more.
• d grows slower than any positive power of n: d(n) = n^o(1), even though it is unbounded.

Где встречаются

• The locker puzzle: walk down a corridor of closed lockers toggling every kth one on pass k, and the lockers left open are exactly the perfect squares — because only squares have an odd number of divisors.
• The number of ways to lay n items out in a rectangular grid, counting a×b and b×a separately, is exactly d(n). Spreadsheet and sprite-sheet layout tools use this.
• The Dirichlet divisor problem is the model case for lattice-point counting under curves, a whole subfield of analytic number theory.
• Trial-division factoring and subgroup-lattice enumeration both have running costs that scale with d(n) rather than with n.
• Database sharding and load-balancing designs favour counts with many divisors, so that the same data splits cleanly across different cluster sizes — a practical preference rather than a theoretical result.