6
$\begingroup$

An exercise in a text I am reading says to find the smallest $n$ such that $\frac{\phi(n)}{n}<\frac{1}{10}$. I checked the first 10 million integers and found none with this property.

$\endgroup$
2
  • $\begingroup$ In the grand scheme of things 10 million is a pretty small number. It's only $10^7$ after all..... GOing to have to try something other the programming. Maybe if $n= \prod p_i^{a_i}$ and $\phi(n)=(\prod (p_i -1))(\prod p_i^{a_i-1})$ find $\frac{\phi(n)=(\prod (p_i -1))(\prod p_i^{a_i-1})}{\prod p_i^{a_i}} < 10$. $\endgroup$
    – fleablood
    Commented Dec 27, 2019 at 21:36
  • $\begingroup$ @fleablood see math.stackexchange.com/questions/301837/… and proof (primorials are optimal) at math.stackexchange.com/questions/301837/… $\endgroup$
    – Will Jagy
    Commented Dec 27, 2019 at 21:40

2 Answers 2

10
$\begingroup$

if $n$ has a prime factorization $p_1^ip_2^jp_3^k$

$\frac {\phi(n)}{n} = \frac{(p_1-1)(p_2-1)(p_3-1)}{p_1p_2p_3}$

If trying to find the smallest $n$ such than $\phi(n) < \frac 1{10}$ there is no reason for to choose $i,j,k > 1$

Take the smallest consecutive prime numbers until you have enough

$\frac{(2-1)(3-1)(5-1)\cdots}{2\cdot 3\cdot 5\cdots}$

You may need 50 prime numbers, and their product may be beyond what you can compute directly, but will get there eventually.

$\endgroup$
1
  • 1
    $\begingroup$ OK Thanks I have now the 55th primorial will be the smallest number to have the desired ratio. 16516447045902521732188973253623425320896207954043566485360902980990824644545340710198976591011245999110 $\endgroup$
    – geoffrey
    Commented Dec 27, 2019 at 19:26
3
$\begingroup$

ADDED: it is known that $$ \phi(n) > \frac{n}{e^\gamma \log \log n + \frac{3}{\log \log n}} $$ for $n>2,$ and where $\gamma = 0.5772156649...$


Once you know to use primorials, you can just add up logs, I used the reciprocal. For each new prime $p,$ I add $$ \log p \; - \; \log (p-1) = \log \left( \frac{p}{p-1} \right) $$ to the cumulative sum

Fri Dec 27 12:30:33 PST 2019


1 Prime  2     log of (primorial) P over P  0.6931471805599453  log ten 2.302585092994046
2 Prime  3     log of (primorial) P over P  1.09861228866811  log ten 2.302585092994046
3 Prime  5     log of (primorial) P over P  1.321755839982319  log ten 2.302585092994046
4 Prime  7     log of (primorial) P over P  1.475906519809577  log ten 2.302585092994046
5 Prime  11     log of (primorial) P over P  1.571216699613903  log ten 2.302585092994046
6 Prime  13     log of (primorial) P over P  1.651259407287438  log ten 2.302585092994046
7 Prime  17     log of (primorial) P over P  1.711884029103873  log ten 2.302585092994046
8 Prime  19     log of (primorial) P over P  1.765951250374148  log ten 2.302585092994046
9 Prime  23     log of (primorial) P over P  1.810403012944982  log ten 2.302585092994046
10 Prime  29     log of (primorial) P over P  1.845494332756253  log ten 2.302585092994046
11 Prime  31     log of (primorial) P over P  1.878284155579243  log ten 2.302585092994046
12 Prime  37     log of (primorial) P over P  1.905683129767358  log ten 2.302585092994046
13 Prime  41     log of (primorial) P over P  1.930375742357729  log ten 2.302585092994046
14 Prime  43     log of (primorial) P over P  1.953906239767923  log ten 2.302585092994046
15 Prime  47     log of (primorial) P over P  1.975412444988887  log ten 2.302585092994046
16 Prime  53     log of (primorial) P over P  1.994460639959582  log ten 2.302585092994046
17 Prime  59     log of (primorial) P over P  2.011555073318883  log ten 2.302585092994046
18 Prime  61     log of (primorial) P over P  2.028084375270094  log ten 2.302585092994046
19 Prime  67     log of (primorial) P over P  2.043122252634634  log ten 2.302585092994046
20 Prime  71     log of (primorial) P over P  2.057306887626591  log ten 2.302585092994046
21 Prime  73     log of (primorial) P over P  2.071100209758927  log ten 2.302585092994046
22 Prime  79     log of (primorial) P over P  2.083839235536357  log ten 2.302585092994046
23 Prime  83     log of (primorial) P over P  2.095960596068702  log ten 2.302585092994046
24 Prime  89     log of (primorial) P over P  2.107260151322635  log ten 2.302585092994046
25 Prime  97     log of (primorial) P over P  2.117622938358182  log ten 2.302585092994046
26 Prime  101     log of (primorial) P over P  2.127573269211351  log ten 2.302585092994046
27 Prime  103     log of (primorial) P over P  2.137329444156716  log ten 2.302585092994046
28 Prime  107     log of (primorial) P over P  2.146719184506555  log ten 2.302585092994046
29 Prime  109     log of (primorial) P over P  2.155935839611478  log ten 2.302585092994046
30 Prime  113     log of (primorial) P over P  2.164824787028725  log ten 2.302585092994046
31 Prime  127     log of (primorial) P over P  2.172729966535838  log ten 2.302585092994046
32 Prime  131     log of (primorial) P over P  2.180392839281407  log ten 2.302585092994046
33 Prime  137     log of (primorial) P over P  2.187718879373481  log ten 2.302585092994046
34 Prime  139     log of (primorial) P over P  2.194939127346967  log ten 2.302585092994046
35 Prime  149     log of (primorial) P over P  2.201673159528312  log ten 2.302585092994046
36 Prime  151     log of (primorial) P over P  2.208317702246981  log ten 2.302585092994046
37 Prime  157     log of (primorial) P over P  2.214707500345751  log ten 2.302585092994046
38 Prime  163     log of (primorial) P over P  2.22086136592013  log ten 2.302585092994046
39 Prime  167     log of (primorial) P over P  2.226867389980343  log ten 2.302585092994046
40 Prime  173     log of (primorial) P over P  2.232664507664669  log ten 2.302585092994046
41 Prime  179     log of (primorial) P over P  2.238266763213339  log ten 2.302585092994046
42 Prime  181     log of (primorial) P over P  2.243806943588955  log ten 2.302585092994046
43 Prime  191     log of (primorial) P over P  2.249056299475098  log ten 2.302585092994046
44 Prime  193     log of (primorial) P over P  2.254251116352203  log ten 2.302585092994046
45 Prime  197     log of (primorial) P over P  2.259340185859674  log ten 2.302585092994046
46 Prime  199     log of (primorial) P over P  2.264377979889631  log ten 2.302585092994046
47 Prime  211     log of (primorial) P over P  2.269128582648229  log ten 2.302585092994046
48 Prime  223     log of (primorial) P over P  2.273622972236069  log ten 2.302585092994046
49 Prime  227     log of (primorial) P over P  2.278037990445186  log ten 2.302585092994046
50 Prime  229     log of (primorial) P over P  2.282414365044985  log ten 2.302585092994046
51 Prime  233     log of (primorial) P over P  2.286715446944375  log ten 2.302585092994046
52 Prime  239     log of (primorial) P over P  2.290908325204412  log ten 2.302585092994046
53 Prime  241     log of (primorial) P over P  2.295066335353075  log ten 2.302585092994046
54 Prime  251     log of (primorial) P over P  2.299058356622613  log ten 2.302585092994046
55 Prime  257     log of (primorial) P over P  2.302956997038271  log ten 2.302585092994046


Fri Dec 27 12:30:33 PST 2019

====================================================

    double logten = log(10.0);
   cout.precision(16);
   cout << logten << endl;

   double log_P_over_phi_P  = 0.0; 

   int count = 0;

   for(mpz_class n = 2; log_P_over_phi_P < logten &&     n <= 2000; ++n)
    {
       if( mp_PrimeQ(n) ) 
       {
         ++count;
         cout << count << " Prime  " << n << "    ";
          log_P_over_phi_P += mp_Log(n);
          log_P_over_phi_P -= mp_Log(n-1);
          cout << " log of (primorial) P over P  " << log_P_over_phi_P  << "  log ten " << logten << endl;
       }
    }

================================================

$\endgroup$
1
  • $\begingroup$ I see, I left out the word "phi" in the printout; the numbers are all as they should be $\endgroup$
    – Will Jagy
    Commented Dec 27, 2019 at 20:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .