딕맨 함수
Mathematical function
The name shown is in ko. The article below is in English and is not a translation.
≈ 6 min read
Names in other languages
- FrançaisFonction de Dickman
- SvenskaDickmans funktion
- EnglishDickman function
- РусскийФункция Дикмана
- 中文Dickman函數
- 中文Dickman函數
- 简体中文Dickman函數
- 繁體中文Dickman函式
- 한국어딕맨 함수
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In analytic number theory, the Dickman function or Dickman–de Bruijn function ρ is a special function used to estimate the proportion of smooth numbers up to a given bound. It was first studied by actuary Karl Dickman [sv], who defined it in his only mathematical publication.[1] It was later studied by the Dutch mathematician Nicolaas Govert de Bruijn.[2][3]
Contents
- 1 Definition
- 2 Properties
- 3 Applications
- 4 Estimation
- 5 Computation
- 6 Extension
- 7 See also
- 8 References
- 9 Further reading
Definition
edit edit sourceThe Dickman–de Bruijn function ρ(u) is a continuous function that satisfies the delay differential equation
- uρ′(u)+ρ(u−1)=0
with initial conditions ρ(u)=1 for 0 ≤ u ≤ 1.
Properties
edit edit sourceDickman proved that, when a is fixed, we have
- Ψ(x,x1/a)∼xρ(a)
where Ψ(x,y) is the number of y-smooth (or y-friable) integers below x. Equivalently, the number of B-smooth numbers less than N is about Ψ(N,B)≈Nρ(logNlogB).
Ramaswami later gave a rigorous proof that for fixed a, Ψ(x,x1/a) was asymptotic to xρ(a), with the error bound
- Ψ(x,x1/a)=xρ(a)+O(x/logx)
Knuth gives a proof for a narrowed bound:
- Ψ(x,x1/a)=xρ(a)+(1−γ)ρ(a−1)(x/logx)+O(x/(logx)2)
where γ is Euler's constant.[5]: 98
Applications
edit edit sourceThe main purpose of the Dickman–de Bruijn function is to estimate the frequency of smooth numbers at a given size. This can be used to optimize various number-theoretical algorithms such as P–1 factoring and can be useful of its own right.[5]
It can be shown that[6]
- Ψ(x,y)=xuO(−u)
which is related to the estimate ρ(u)≈u−u below.
The Golomb–Dickman constant has an alternate definition in terms of the Dickman–de Bruijn function.
Estimation
edit edit sourceA first approximation might be ρ(u)≈u−u. A better estimate is[7]
- ρ(u)∼1ξ2πu⋅exp(−uξ+Ei(ξ))
where Ei is the exponential integral and ξ is the positive root of
- eξ−1=uξ.
A simple upper bound is ρ(x)≤1/x!.
| u | ρ(u) |
|---|---|
| 1 | 1 |
| 2 | 3.0685282×10−1 |
| 3 | 4.8608388×10−2 |
| 4 | 4.9109256×10−3 |
| 5 | 3.5472470×10−4 |
| 6 | 1.9649696×10−5 |
| 7 | 8.7456700×10−7 |
| 8 | 3.2320693×10−8 |
| 9 | 1.0162483×10−9 |
| 10 | 2.7701718×10−11 |
Computation
edit edit sourceFor each interval [n − 1, n] with n an integer, there is an analytic function ρn such that ρn(u)=ρ(u). For 0 ≤ u ≤ 1, ρ(u)=1. For 1 ≤ u ≤ 2, ρ(u)=1−logu. For 2 ≤ u ≤ 3,
- ρ(u)=1−(1−log(u−1))log(u)+Li2(1−u)+π212.
with Li2 the dilogarithm. Other ρn can be calculated using infinite series.[8]
An alternate method is computing lower and upper bounds with the trapezoidal rule;[7] a mesh of progressively finer sizes allows for arbitrary accuracy. For high precision calculations (hundreds of digits), a recursive series expansion about the midpoints of the intervals is superior.[9] Values for u ≤ 7 can be usefully computed via numerical integration in ordinary double-precision floating-point.[5]: 99
Extension
edit edit sourceFriedlander defines a two-dimensional analog σ(u,v) of ρ(u).[10] This function is used to estimate a function Ψ(x,y,z) similar to de Bruijn's, but counting the number of y-smooth integers with at most one prime factor greater than z. Then
- Ψ(x,x1/a,x1/b)∼xσ(b,a).
This class of numbers may be encountered in the two-stage variant of P-1 factoring. However, Kruppa's estimate of the probability of finding a factor by P-1 does not make use of this result.[5]: 100
See also
edit edit source- Buchstab function, a function used similarly to estimate the number of rough numbers, whose convergence to e−γ is controlled by the Dickman function
- Golomb–Dickman constant
- Poisson-Dirichlet distribution
References
edit edit source- ^ Dickman, K. (1930). "On the frequency of numbers containing prime factors of a certain relative magnitude". Arkiv för Matematik, Astronomi och Fysik. 22A (10): 1–14. Bibcode:1930ArMAF..22A..10D. Retrieved 2026-09-02.
- ^ de Bruijn, N. G. (1951). "On the number of positive integers ≤ x and free of prime factors > y" (PDF). Indagationes Mathematicae. 13: 50–60.
- ^ de Bruijn, N. G. (1966). "On the number of positive integers ≤ x and free of prime factors > y, II" (PDF). Indagationes Mathematicae. 28: 239–247.
- ^ Ramaswami, V. (1949). "On the number of positive integers less than x and free of prime divisors greater than xc" (PDF). Bulletin of the American Mathematical Society. 55 (12): 1122–1127. doi:10.1090/s0002-9904-1949-09337-0. MR 0031958.
- ^ a b c d Kruppa, Alexander (2010). Speeding up Integer Multiplication and Factorization (PDF) (PhD thesis). Henri Poincaré University. – Work describes algorithms that Kruppa had contributed to GMP-ECM and other factoring programs. Some chapters have been published elsewhere.
- ^ Hildebrand, A.; Tenenbaum, G. (1993). "Integers without large prime factors" (PDF). Journal de théorie des nombres de Bordeaux. 5 (2): 411–484. doi:10.5802/jtnb.101.
- ^ a b van de Lune, J.; Wattel, E. (1969). "On the Numerical Solution of a Differential-Difference Equation Arising in Analytic Number Theory". Mathematics of Computation. 23 (106): 417–421. doi:10.1090/S0025-5718-1969-0247789-3.
- ^ Bach, Eric; Peralta, René (1996). "Asymptotic Semismoothness Probabilities" (PDF). Mathematics of Computation. 65 (216): 1701–1715. Bibcode:1996MaCom..65.1701B. doi:10.1090/S0025-5718-96-00775-2.
- ^ Marsaglia, George; Zaman, Arif; Marsaglia, John C. W. (1989). "Numerical Solution of Some Classical Differential-Difference Equations". Mathematics of Computation. 53 (187): 191–201. doi:10.1090/S0025-5718-1989-0969490-3.
- ^ Friedlander, John B. (1976). "Integers free from large and small primes". Proc. London Math. Soc. 33 (3): 565–576. doi:10.1112/plms/s3-33.3.565.
Further reading
edit edit source- Broadhurst, David (2010). "Dickman polylogarithms and their constants". arXiv:1004.0519 [math-ph].
- Soundararajan, Kannan (2012). "An asymptotic expansion related to the Dickman function". Ramanujan Journal. 29 (1–3): 25–30. arXiv:1005.3494. doi:10.1007/s11139-011-9304-3. MR 2994087. S2CID 119564455.
- Weisstein, Eric W. "Dickman function". MathWorld.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1372858535 under CC BY-SA 4.0; modifications have been made.