Number of distinct prime divisors of an integer $n$ is $O(\log n/\log\log n)$

Solution 1:

Yes, the paper by Robin you cite has, on page 368 (its second page):

la fonction $\omega(n)$: nombre de diviseurs premiers de l'entier $n$.

Which translates to:

the function $\omega(n)$: the number of prime divisors of the integer $n$.

(This is a standard definition, but it's good to check the paper is using the definition you want.)

Then, on the following page (369, the third page of the article) there are various upper bounds on $\omega(n)$ given. I'll just quote the first one; you can read them yourself with the note that pour means for and a comma is used instead of a decimal point:

$\omega(n) \leq 1.3841 \frac{\log n}{\log\log n}$ for $n \geq 3$

This confirms that $\omega(n)$ is $O(\frac{\log n}{\log \log n})$.

Solution 2:

The primorials are the products of the consecutive primes from 2 up to something, so they are $2, 6, 30, 210,$ and so on. A number $n$ cannot have more distinct prime divisors than the largest primorial that is no larger than $n.$ I suggest that you write a quick program to calculate the first ten or twenty primorials, and for each primorial $n$ calculate $$ \frac{\log n}{ \log \log n} $$ and compare with the number of prime factors, these being distinct by the definition of the primorials. It is not necessary to explicitly find the primorial itself (or print it), its logarithm is just the sum of the logs of its prime factors. Then take another log of that to get the denominator.

In turn, this observation can be made to quickly give the bound quoted from Robin using explicit bounds in Rosser and Schoenfeld (1962). Edit: looking again, and noticing that the optimum occurs at the primorial with largest prime factor 23, I suggest that Robin found that result, while Rosser and Schoenfeld might give a less precise constant, maybe 2.0 instead of 1.3841. I imagine Robin quotes their constant in his article in the first few pages.


 omega    1 top prime    2 Robin ratio -1.891194393528896   Primorial  2
 omega    2 top prime    3 Robin ratio 3.072300009669941   Primorial  6
 omega    3 top prime    5 Robin ratio 2.778466514782393   Primorial  30
 omega    4 top prime    7 Robin ratio 3.189340693812293   Primorial  210
 omega    5 top prime   11 Robin ratio 3.783498689132461   Primorial  2310
 omega    6 top prime   13 Robin ratio 4.418974532899663   Primorial  30030
 omega    7 top prime   17 Robin ratio 5.102354851231403   Primorial  510510
 omega    8 top prime   19 Robin ratio 5.790972042777755   Primorial  9699690
 omega    9 top prime   23 Robin ratio 6.502830309657649   Primorial  223092870
 omega   10 top prime   29 Robin ratio 7.246259778056221   Primorial  6469693230
 omega   11 top prime   31 Robin ratio 7.985305729097138   Primorial  200560490130
 omega   12 top prime   37 Robin ratio 8.744643009669849   Primorial  7420738134810
 omega   13 top prime   41 Robin ratio 9.50916568672571   Primorial  304250263527210
 omega   14 top prime   43 Robin ratio 10.26873760689452   Primorial  13082761331670030
 omega   15 top prime   47 Robin ratio 11.03275458447593   Primorial  614889782588491410
 omega   16 top prime   53 Robin ratio 11.80791815799024   Primorial  32589158477190044730
 omega   17 top prime   59 Robin ratio 12.59204609226844   Primorial  1922760350154212639070
 omega   18 top prime   61 Robin ratio 13.37154899993717   Primorial  117288381359406970983270
 omega   19 top prime   67 Robin ratio 14.15847947390451   Primorial  7858321551080267055879090
 omega   20 top prime   71 Robin ratio 14.94653596430098   Primorial  557940830126698960967415390
 omega   21 top prime   73 Robin ratio 15.73068925382913   Primorial  40729680599249024150621323470
 omega   22 top prime   79 Robin ratio 16.52071947436941   Primorial  3217644767340672907899084554130
 omega   23 top prime   83 Robin ratio 17.31157778776554   Primorial  267064515689275851355624017992790
 omega   24 top prime   89 Robin ratio 18.10720534877059   Primorial  23768741896345550770650537601358310
 omega   25 top prime   97 Robin ratio 18.9106523419625   Primorial  2305567963945518424753102147331756070

 omega    1 top prime    2 Robin ratio -1.891194393528896 compare 1.3841  -0.5287663729448977
 omega    2 top prime    3 Robin ratio 3.072300009669941 compare 1.3841  0.6509780925381897
 omega    3 top prime    5 Robin ratio 2.778466514782393 compare 1.3841  1.07973228543118
 omega    4 top prime    7 Robin ratio 3.189340693812293 compare 1.3841  1.254177707562094
 omega    5 top prime   11 Robin ratio 3.783498689132461 compare 1.3841  1.321528143874282
 omega    6 top prime   13 Robin ratio 4.418974532899663 compare 1.3841  1.357781076883214
 omega    7 top prime   17 Robin ratio 5.102354851231403 compare 1.3841  1.371915557443171
 omega    8 top prime   19 Robin ratio 5.790972042777755 compare 1.3841  1.381460649594613
 omega    9 top prime   23 Robin ratio 6.502830309657649 compare 1.3841  1.384012740826666
 omega   10 top prime   29 Robin ratio 7.246259778056221 compare 1.3841  1.380022288226942
 omega   11 top prime   31 Robin ratio 7.985305729097138 compare 1.3841  1.377530225288409
 omega   12 top prime   37 Robin ratio 8.744643009669849 compare 1.3841  1.372268712025222
 omega   13 top prime   41 Robin ratio 9.50916568672571 compare 1.3841  1.367102060083705
 omega   14 top prime   43 Robin ratio 10.26873760689452 compare 1.3841  1.363361353259263
 omega   15 top prime   47 Robin ratio 11.03275458447593 compare 1.3841  1.359587932927135
 omega   16 top prime   53 Robin ratio 11.80791815799024 compare 1.3841  1.355022941886928
 omega   17 top prime   59 Robin ratio 12.59204609226844 compare 1.3841  1.350058590592204
 omega   18 top prime   61 Robin ratio 13.37154899993717 compare 1.3841  1.346141722255558
 omega   19 top prime   67 Robin ratio 14.15847947390451 compare 1.3841  1.34195201080871
 omega   20 top prime   71 Robin ratio 14.94653596430098 compare 1.3841  1.338102691337241
 omega   21 top prime   73 Robin ratio 15.73068925382913 compare 1.3841  1.334970112316485
 omega   22 top prime   79 Robin ratio 16.52071947436941 compare 1.3841  1.33166113220016
 omega   23 top prime   83 Robin ratio 17.31157778776554 compare 1.3841  1.32859062772745
 omega   24 top prime   89 Robin ratio 18.10720534877059 compare 1.3841  1.325439212607677
 omega   25 top prime   97 Robin ratio 18.9106523419625 compare 1.3841  1.322006218924839