Fonction nombre de diviseurs

Pour tout nombre naturel ${\displaystyle n}$ on définit :

${\displaystyle {\text{d}}(n)=\operatorname {card} \left(\{d\in \mathbb {N} {\text{$ ; }}1\leqslant d\leqslant n\ {\text{et}}\ d|n\}\right)=\sum _{d|n}1} où ${\displaystyle d|n}$ indique la divisibilité de ${\displaystyle n}$ par ${\displaystyle d}$.

Les premières valeurs sont les suivantes^[1] :

• On a l'identité suivante : ${\displaystyle \sum _{k=1}^{n}{\text{d}}(k)=\sum _{d=1}^{n}\left\lfloor {\frac {n}{d}}\right\rfloor }$ où ${\displaystyle \left\lfloor \,.\right\rfloor }$ désigne la fonction partie entière^[2],[3],[4] :

• Si la décomposition en produit de facteurs premiers de ${\displaystyle n}$ est

  ${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\dots p_{r}^{\alpha _{r}}}$,

  alors^[5] :

  ${\displaystyle {\text{d}}(n)=(\alpha _{1}+1)(\alpha _{2}+1)\dots (\alpha _{r}+1)}$.

• La fonction nombre de diviseurs est donc multiplicative, c.-à-d. que si ${\displaystyle m}$ et ${\displaystyle n}$ sont premiers entre eux, alors :

  ${\displaystyle {\text{d}}(mn)={\text{d}}(m){\text{d}}(n)}$.

• Un nombre n est premier si et seulement si d(n)=2.
• Un nombre n est un carré parfait si et seulement si d(n) est impair.
• ${\displaystyle {\text{d}}(n)}$ est le double du nombre de diviseurs de n entre 1 et √n, auquel il faut retrancher 1 si ${\displaystyle n}$ est un carré parfait, donc un majorant de d(n) est 2√n.
• La fonction génératrice de (d(n)) s'exprime comme série de Lambert :

  ${\displaystyle \sum _{n=1}^{\infty }{\text{d}}(n)s^{n}=\sum _{n=1}^{\infty }{\frac {s^{n}}{1-s^{n}}}}$ (pour ${\displaystyle \operatorname {Re} (s)>1}$)

• La série de Dirichlet de (d(n)) est le carré de la fonction zêta de Riemann^[6] :

  ${\displaystyle \sum _{n=1}^{\infty }{\frac {{\text{d}}(n)}{n^{s}}}=\zeta ^{2}(s)}$ (pour ${\displaystyle \operatorname {Re} (s)>1}$)

La fonction d est très irrégulière : elle prend la valeur 2 pour ${\displaystyle n}$ premier, et prend aussi des valeurs arbitrairement grandes (par exemple N + 1 pour n = 2^N) . Mais en moyenne de Cesàro : ${\displaystyle {\frac {\sum _{k=1}^{n}{\text{d}}(k)}{n}}\sim \ln n}$.

Ceci vient de la formule ${\displaystyle \sum _{k=1}^{n}{\text{d}}(k)=\sum _{k=1}^{n}\left\lfloor {\frac {n}{k}}\right\rfloor }$ , dont on déduit : ${\displaystyle H_{n}-1\leqslant {\frac {\sum _{k=1}^{n}{\text{d}}(k)}{n}}\leqslant H_{n}}$ où (H_n) est la série harmonique, puis l'encadrement :

${\displaystyle \ln n-1\leqslant {\frac {\sum _{k=1}^{n}{\text{d}}(k)}{n}}\leqslant \ln n+1}$.

Un développement plus précis est donné par^{[2],[7],[8],[4]}

${\displaystyle {\frac {\sum _{k=1}^{n}{\text{d}}(k)}{n}}=\ln n+2\gamma -1+O(1/{\sqrt {n}})}$

(où O est un symbole de Landau et γ la constante d'Euler-Mascheroni.)

Il a été démontré par Johann Peter Gustav Lejeune Dirichlet en 1849^[9].

On en déduit qu'un ordre moyen pour d(n) est ln n + 2γ.

La recherche des valeurs de ${\displaystyle \beta \leqslant {\tfrac {1}{2}}}$ telles que

${\displaystyle \sum _{1\leqslant n\leqslant x}d(n)=x\ln x+(2\gamma -1)x+O(x^{\beta })}$

constitue le « problème des diviseurs de Dirichlet (en) »^[3].

Des avancées ont été effectuées par Gueorgui Voronoï (1903, O(√x) remplacé par O(³√x log(x))^[10], Johannes van der Corput (1922, β = 33/100)^[11], ainsi que Martin Huxley (de) (2003, β = 131/416)^[12]. À l'opposé, Godfrey Harold Hardy et Edmund Landau ont démontré^[13] que β est nécessairement supérieur ou égal à 1/4. Les valeurs possibles pour β font toujours l'objet de recherches.

Posons ${\textstyle {\text{u}}(n)=\sum _{d|n}(-1)^{d}={\text{dp}}(n)-{\text{di}}(n)}$ où ${\displaystyle {\text{dp}}(n)}$ est le nombre de diviseurs pairs de ${\displaystyle n}$ et ${\displaystyle {\text{di}}(n)}$ celui des diviseurs impairs ; la suite ${\displaystyle (-{\text{u}}(n))}$ est répertoriée comme suite A048272 de l'OEIS.

On a alors l'identité : ${\displaystyle \sum _{k=1}^{n}{\text{u}}(k)=\sum _{d=1}^{n}(-1)^{d}\left\lfloor {\frac {n}{d}}\right\rfloor }$ qui, combinée avec la valeur de la série harmonique alternée ${\displaystyle \sum _{d=1}^{\infty }{\frac {(-1)^{d}}{d}}=-\ln 2}$,

donne la convergence au sens de Cesàro de ${\displaystyle ({\text{u}}(n))}$ vers ${\displaystyle -\ln 2}$ .

La formule de Dirichlet permet d'obtenir plus précisément : ${\displaystyle {\frac {\sum _{k=1}^{n}{\text{u}}(k)}{n}}=-\ln 2+O(1/{\sqrt {n}})}$.

Notons ${\displaystyle n_{\min }(m)}$ le plus petit ${\displaystyle n}$ tel que ${\displaystyle {\text{d}}(n)=m}$ ; la suite ${\displaystyle (n_{\min }(m))_{m}}$ est répertoriée comme suite A005179 de l'OEIS.

Le tableau suivant en donne les 36 premiers termes.

Plus petit entier ayant un nombre prescrit de diviseurs

${\displaystyle n_{\min }(m)}$ : plus petit ${\displaystyle n}$ ayant ${\displaystyle m}$ diviseurs^[14].

Nombre ${\displaystyle m}$ de diviseurs	${\displaystyle n_{\min }(m)}$	Factorisation de ${\displaystyle n_{\min }(m)}$
1	1	1
2	2	2
3	4	22
4	6	2·3
5	16	24
6	12	22·3
7	64	26
8	24	23·3
9	36	22·32
10	48	24·3
11	1 024	210
12	60	22·3·5
13	4 096	212
14	192	26·3
15	144	24·32
16	120	23·3·5
17	65 536	216
18	180	22·32·5
19	262 144	218
20	240	24·3·5
21	576	26·32
22	3 072	210·3
23	4 194 304	222
24	360	23·32·5
25	1 296	24·34
26	12 288	212·3
27	900	22·32·52
28	960	26·3·5
29	268 435 456	228
30	720	24·32·5
31	1 073 741 824	230
32	840	23·3·5·7
33	9 216	210·32
34	196 608	216·3
35	5 184	26·34
36	1 260	22·32·5·7

 

Nota 1 : Pour p,q premiers tels que ${\displaystyle p\leqslant q}$, ${\displaystyle n_{\min }(p)=2^{p-1}}$ et ${\displaystyle n_{\min }(pq)=2^{q-1}3^{p-1}}$.

Nota 2 : si ${\displaystyle n_{\min }(m)}$ n'a pas de successeur plus petit que lui, alors il est hautement composé.