# How does one know the growth rate of distinct prime divisors?

I saw online a statement that

"It can be shown that the number of distinct prime divisors of an integer n, denoted $\omega(n)$, is such that

$$\omega(n) = O\left(\frac{\log n}{\log \log n}\right)."$$

But I really have no idea how this is true,

In general I actually have very little experience proving any results about growth rates and such.

Does one need to use some basic known results in number theory to prove it?

• You need to know a lot more than basic results in number theory to prove things of this kind. You can see some of the results and ideas at en.wikipedia.org/wiki/Analytic_number_theory Mar 11, 2017 at 20:05

The smallest number with $m$ distinct prime factors is the primorial $M=p_1\cdot\ldots\cdot p_m$.
By the prime number theorem $\sum_{p\leq x}\log p= x+o(x)$ and $p_m\approx m\log m$, hence in order to have $\omega(M)=m$ we need $M\geq e^{m\log m+O(m)}$ and that turns into $$\omega(M)=O\left(\frac{\log M}{\log\log M}\right)$$ as wanted.

• Can you please explain the following: I understand why if you write $M$ as you did that we would need $\omega(M)=m$, but I am not sure how you do some of the steps ( I am very new to this subject) such as, how did you get the estimate with the little o? and why in order for us to have that do you require M to be greater then that term and how does that turn into the big O notation form? Mar 12, 2017 at 2:08
• @Quality: both the estimates $\sum_{p\leq x}\log p=x+o(x)$ and $p_m\approx m\log m$ follow from the prime number theorem. The remaining part is trivial: we want an upper bound for $\omega$, hence we may equivalently find how small $M$ might be to ensure $\omega(M)=m$. Mar 12, 2017 at 2:12
• Thank you.. so I see from the prime number theorem that $\Pi (x)$ is asymptotic to $x/logx$ and so the some of the primes over the logs gives me the x, where does the o(x) come from though? Mar 12, 2017 at 22:37
• @Quality: the remainder term in the prime number theorem depends on the distribution of the zeroes of the Riemann $\zeta$ function. Assuming RH, such $o(x)$ is indeed $O(\sqrt{x}\log^2 x)$, but the PNT is enough to ensure $\psi(x)\sim x$, i.e. $\psi(x) = x+o(x)$. Mar 12, 2017 at 22:49
• I understand that part now, I really do appreciate the time. The last things I would be wondering are, how do you get the bound on the mth prime? and isnt \omega(M)=m by your definition of M? Why does it require that extra part and is it actually equivalent to the last part? Mar 12, 2017 at 23:02

This problem is unusual in that there is an obvious sequence, the primorials, for which the value of $\omega(n)$ increases; your function does not increase (achieve a new maximum) at anywhere else. So, it is enough to estimate the inverse function. Let me make a quick program output, give me a few minutes. It appears that, for $n > 2,$ we get $$\omega(n) < 1.4 \frac{\log n}{\log \log n}.$$ Alright, he does not attempt an explicit bound such as my conjectured 1.4, but Ramanujan does derive the maximal order. Note that this extreme behavior is not at all typical, see Erdos Kac. Again, Ramanujan did get part of Erdos-Kac.

Page 17 of Carella. See formula (4.6) which gives an explicit error term.

  omega prime             n = primorial              log n / log log n  ratio
1    2                                          2    -1.89119  -0.528766
2    3                                          6    3.0723  0.650978
3    5                                         30    2.77847  1.07973
4    7                                        210    3.18934  1.25418
5   11                                       2310    3.7835  1.32153
6   13                                      30030    4.41897  1.35778
7   17                                     510510    5.10235  1.37192
8   19                                    9699690    5.79097  1.38146
9   23                                  223092870    6.50283  1.38401
10   29                                 6469693230    7.24626  1.38002
11   31                               200560490130    7.98531  1.37753
12   37                              7420738134810    8.74464  1.37227
13   41                            304250263527210    9.50917  1.3671
14   43                          13082761331670030    10.2687  1.36336
15   47                         614889782588491410    11.0328  1.35959
16   53                       32589158477190044730    11.8079  1.35502
17   59                     1922760350154212639070    12.592  1.35006
18   61                   117288381359406970983270    13.3715  1.34614
19   67                  7858321551080267055879090    14.1585  1.34195
20   71                557940830126698960967415390    14.9465  1.3381
21   73              40729680599249024150621323470    15.7307  1.33497
22   79            3217644767340672907899084554130    16.5207  1.33166
23   83          267064515689275851355624017992790    17.3116  1.32859
24   89        23768741896345550770650537601358310    18.1072  1.32544
25   97      2305567963945518424753102147331756070    18.9107  1.32201
omega prime             n = primorial              log n / log log n  ratio


I let the primorials get bigger but did not print them, the 1.4 figure looks good.

    1    2    -1.89119  -0.528766
2    3    3.0723  0.650978
3    5    2.77847  1.07973
4    7    3.18934  1.25418
5   11    3.7835  1.32153
6   13    4.41897  1.35778
7   17    5.10235  1.37192
8   19    5.79097  1.38146
9   23    6.50283  1.38401
10   29    7.24626  1.38002
11   31    7.98531  1.37753
12   37    8.74464  1.37227
13   41    9.50917  1.3671
14   43    10.2687  1.36336
15   47    11.0328  1.35959
16   53    11.8079  1.35502
17   59    12.592  1.35006
18   61    13.3715  1.34614
19   67    14.1585  1.34195
20   71    14.9465  1.3381
21   73    15.7307  1.33497
22   79    16.5207  1.33166
23   83    17.3116  1.32859
24   89    18.1072  1.32544
25   97    18.9107  1.32201
26  101    19.7141  1.31885
27  103    20.5143  1.31616
28  107    21.3147  1.31365
29  109    22.1122  1.31149
30  113    22.9101  1.30947
31  127    23.722  1.3068
32  131    24.5336  1.30433
33  137    25.3474  1.30191
34  139    26.1586  1.29976
35  149    26.9763  1.29744
36  151    27.7914  1.29537
37  157    28.6082  1.29333
38  163    29.4267  1.29134
39  167    30.2448  1.28948
40  173    31.0644  1.28765
41  179    31.8853  1.28586
42  181    32.7042  1.28424
43  191    33.5277  1.28252
44  193    34.3491  1.28097
45  197    35.1701  1.27949
46  199    35.9893  1.27816
47  211    36.8141  1.27668
48  223    37.6441  1.2751
49  227    38.4735  1.2736
50  229    39.3011  1.27223
51  233    40.1283  1.27092
52  239    40.9563  1.26965
53  241    41.7826  1.26847
54  251    42.6121  1.26724
55  257    43.4424  1.26604
56  263    44.2734  1.26487
57  269    45.105  1.26372
58  271    45.9351  1.26265
59  277    46.7659  1.2616
60  281    47.5962  1.2606
61  283    48.4251  1.25968
62  293    49.2567  1.25871
63  307    50.0927  1.25767
64  311    50.9283  1.25667
65  313    51.7624  1.25574
66  317    52.5962  1.25484
67  331    53.434  1.25388
68  337    54.2722  1.25294
69  347    55.1124  1.25199
70  349    55.9513  1.25109
71  353    56.7898  1.25022
72  359    57.6287  1.24938
73  367    58.4686  1.24853
74  373    59.3089  1.2477
75  379    60.1495  1.24689
76  383    60.9897  1.24611
77  389    61.8302  1.24535
78  397    62.6717  1.24458
79  401    63.5127  1.24385
80  409    64.3548  1.24311
81  419    65.1984  1.24236
82  421    66.0409  1.24165
83  431    66.885  1.24094
84  433    67.728  1.24025
85  439    68.5713  1.23959
86  443    69.4142  1.23894
87  449    70.2572  1.23831
88  457    71.1012  1.23767
89  461    71.9447  1.23706
90  463    72.7872  1.23648
91  467    73.6295  1.23592
92  479    74.4736  1.23534
93  487    75.3185  1.23476
94  491    76.1631  1.23419
95  499    77.0084  1.23363
96  503    77.8533  1.23309
97  509    78.6984  1.23255
98  521    79.5452  1.232
99  523    80.3912  1.23148
100  541    81.2403  1.23092
101  547    82.0896  1.23036
102  557    82.9399  1.22981
103  563    83.7903  1.22926
104  569    84.6409  1.22872
105  571    85.4905  1.22821
106  577    86.3403  1.2277
107  587    87.1911  1.22719
108  593    88.042  1.22669
109  599    88.893  1.22619
110  601    89.7432  1.22572
111  607    90.5934  1.22525
112  613    91.4438  1.2248
113  617    92.2938  1.22435
114  619    93.1431  1.22392
115  631    93.9937  1.22349
116  641    94.8452  1.22304
117  643    95.696  1.22262
118  647    96.5465  1.22221
119  653    97.3971  1.2218
120  659    98.2477  1.2214
121  661    99.0977  1.22102
122  673    99.9489  1.22062
123  677    100.8  1.22024
124  683    101.651  1.21986
125  691    102.502  1.21949
126  701    103.354  1.21911
127  709    104.207  1.21873
128  719    105.061  1.21834
129  727    105.914  1.21796
130  733    106.768  1.21759
131  739    107.622  1.21722
132  743    108.476  1.21686
133  751    109.33  1.2165
134  757    110.184  1.21615
135  761    111.038  1.2158
136  769    111.892  1.21546
137  773    112.746  1.21512
138  787    113.601  1.21478
139  797    114.457  1.21443
140  809    115.314  1.21408
141  811    116.17  1.21373
142  821    117.027  1.21339
143  823    117.884  1.21306
144  827    118.74  1.21274
145  829    119.595  1.21242
146  839    120.451  1.21211
147  853    121.309  1.21179
148  857    122.166  1.21147
149  859    123.022  1.21116
150  863    123.878  1.21087
151  877    124.736  1.21056
152  881    125.593  1.21026
153  883    126.449  1.20997
154  887    127.306  1.20969
155  907    128.164  1.20939
156  911    129.022  1.2091
157  919    129.88  1.20881
158  929    130.739  1.20851
159  937    131.598  1.20822
160  941    132.457  1.20794
161  947    133.316  1.20766
162  953    134.175  1.20738
163  967    135.035  1.2071
164  971    135.894  1.20682
165  977    136.754  1.20655
166  983    137.613  1.20628
167  991    138.473  1.20601
168  997    139.333  1.20574
jagy@phobeusjunior:~\$