Límite superior de Euler totient función en compuestos de números

Question

He visto antes de que el general vinculado $\phi(n) \leq n - n^{1/2}$ compuesto $n$. Puede esta obligado a ser mejorado al menos para los $n$ cuando no tenemos la igualdad de arriba? Decir que podríamos tener al menos $\phi(n) \leq n - kn^{1/2}$ algunos $k > 1$?

Answer 1

Deje $n=p^2$. A continuación,$\varphi(n)=p^2-p=n-\sqrt{n}$. Así que tenemos igualdad de infinidad de $n$.

Si $n=p^e$ donde$e\gt 2$,$\varphi(n)=p^e-p^{e-1}=n-n^{1-1/e}$. Peor de los casos es $e=3$, $p=2$. En este caso tenemos a $n^{2/3}\ge kn^{1/2}$ donde $k=2^{1/6}$. Por lo tanto $\varphi(n)\le n-2^{1/6}n^{1/2}$.

Si $n=ab$ donde $a$ $b$ son mayores de $1$ y relativamente primos, a continuación,$\varphi(n)=\varphi(ab)\le (a-1)(b-1)=n-(a+b)+1$. Tenga en cuenta que $a+b\gt 2\sqrt{n}$, con lo que conseguimos $\varphi(n)\le n-2\sqrt{n}+1$ en este caso.

Answer 2

Tenemos la fórmula $$ \phi(n)=n\prod_{\substack{p\mediados n\\p\text{ prime}}}\left(1-\frac1p\right)\etiqueta{1} $$ Para un compuesto $n$, el más pequeño prime $p_0\mid n$ es en la mayoría de las $\sqrt{n}$, lo $(1)$ implica $$ \begin{align} \phi(n) &\le n\left(1-\frac1{p_0}\right)\\ &\le n\left(1-\frac1{\sqrt{n}}\right)\\ &=n-\sqrt{n}\tag{2} \end{align} $$ Además, para $n=p^2$, $$ \phi(p^2)=p^2-p\etiqueta{3} $$ Así, podemos encontrar una arbitrariamente grande compuesto $n$, de modo que $\phi(n)=n-\sqrt{n}$.

Si no tenemos igualdad en $(3)$, tendremos a $n=p^k$ o $n$ cuenta con dos factores primos. $$ \phi(p^k)=p^k-p^{k-1}\etiqueta{4} $$ Así, por $k\ge3$ $$ \frac{n-\phi(n)}{\sqrt{n}}=\frac{p^{k-1}}{p^{k/2}}=p^{k/2-1}=n^{1/2-1/k}\ge n^{1/6}\etiqueta{5} $$ así que si estamos buscando la menor $\frac{n-\phi(n)}{\sqrt{n}}$, tenemos que mirar a $n=pq$. Tenemos $$ \frac{pq-\phi(pq)}{\sqrt{pq}}=\frac{p+q-1}{\sqrt{pq}}=\frac{\sqrt{p}}{\sqrt{q}}+\frac{\sqrt{q}}{\sqrt{p}}-\frac1{\sqrt{pq}}\tag{6} $$ Desde $x+\frac1x=2+\left(\sqrt{x}-\frac1{\sqrt{x}}\right)^2\ge2$, con igualdad sólo al $x=1$, tenemos que si $n$ cuenta con dos factores primos, $$ \frac{n-\phi(n)}{\sqrt{n}}\gt2-\frac1{\sqrt{n}}\implica\phi(n)\lt n-2\sqrt{n}+1\etiqueta{7} $$ Además, la desigualdad de $(5)$ garantiza que la desigualdad $(7)$ mantiene si $n\ge39$ $n$ no es un número primo o el cuadrado de un primo.

---

Comprobación de los números enteros de menos de $39$, podemos ver que si $n$ no es un número primo o el cuadrado de un primo y $n\ne8$$n\ne27$, $(7)$ mantiene.

Answer 3

Bueno, si $n$ es el producto de números primos consecutivos consigue $\phi(n) > n - 2 \sqrt n,$ pero se pone cerca, y usted probablemente puede tomar su $k = 1.5$ $n>8$ decir

2   16 = 2^4
1.999437280176435   1333 = 31 * 43
1.999118949876075   7663 = 79 * 97
1.99871723147485   8383 = 83 * 101
1.998342529102684   2867 = 47 * 61
1.99824032638073   9523 = 89 * 107
1.998065959315103   5561 = 67 * 83
1.997420223212713   6497 = 73 * 89
1.996970389115528   3551 = 53 * 67
1.996107193636781   4307 = 59 * 73
1.99504678865167   2173 = 41 * 53
1.994932096041783   8051 = 83 * 97
1.994893666788084   9167 = 89 * 103
1.993950461300493   2773 = 47 * 59
1.993453519963639   8989 = 89 * 101
1.993124970314336   4189 = 59 * 71
1.993082580330997   4453 = 61 * 73
1.993073020359085   5893 = 71 * 83
1.993044773767945   5293 = 67 * 79
1.991741189771645   91 = 7 * 13
1.991626618969993   7031 = 79 * 89
1.991524132758911   1271 = 31 * 41
1.991274911100793   6059 = 73 * 83
1.991089847651314   8633 = 89 * 97
1.990896104916204   9991 = 97 * 103
1.990568850865158   4331 = 61 * 71
1.990344721501349   1739 = 37 * 47
1.990305174632736   9797 = 97 * 101
1.989992514114262   2279 = 43 * 53
1.989582997411111   7387 = 83 * 89
1.989498190165494   5609 = 71 * 79
1.988391837175112   5767 = 73 * 79
1.988260497982835   6557 = 79 * 83
1.988138364484967   3953 = 59 * 67
1.987540416848836   4891 = 67 * 73
1.987355637820889   3233 = 53 * 61
1.986558698771642   4087 = 61 * 67
1.986341843827027   4757 = 67 * 71
1.986302700472586   5183 = 71 * 73
1.984993267773272   3127 = 53 * 59
1.984865598623816   713 = 23 * 31
1.984328160336157   1073 = 29 * 37
1.983608853697701   3599 = 59 * 61
1.983573651759631   2491 = 47 * 53
1.981884747156589   1927 = 41 * 47
1.980578231727406   1591 = 37 * 43
1.979734037185575   2021 = 43 * 47
1.9783042944476   1147 = 31 * 37
1.976960238957923   1517 = 37 * 41
1.976750859152595   1763 = 41 * 43
1.974727886289034   667 = 23 * 29
1.974435545143253   187 = 11 * 17
1.972482765224911   247 = 13 * 19
1.972314775954277   391 = 17 * 23
1.967760170596957   899 = 29 * 31
1.963961012123931   21 = 3 * 7
1.961295980263253   437 = 19 * 23
1.950751102589306   221 = 13 * 17
1.9474520942613   323 = 17 * 19
1.937329799813845   77 = 7 * 11
1.923356623016309   143 = 11 * 13
1.897366596101028   10 = 2 * 5
1.859339360402736   35 = 5 * 7
1.807392228230128   15 = 3 * 5
1.732050807568877   27 = 3^3
1.632993161855452   6 = 2 * 3
1.414213562373095   8 = 2^3
jagy@phobeusjunior:~$ 
    jagy@phobeusjunior:~$