For a positive integer $n$, let $d(n)$ be the number of positive divisors of $n$, and let $\varphi(n)$ be the number of positive integers not exceeding $n$ which are coprime to $n$. Does there exist a constant $C$ such that $$ \frac {\varphi ( d(n))}{d(\varphi(n))}\le C$$for all $n\ge 1$ Cyprus
Problem
Source: IMO SL 2020 N6
Tags: number theory, Euler s totient function, number of divisors, IMO Shortlist, IMO Shortlist 2020
20.07.2021 23:47
The answer is no. By Prime Number Theorem we can pick arbitrarily large sets $A$ of primes such that $\text{max}(A) \le 2\text{min}(A)$. Let $S$ be the smallest set such that for every $t \in A \cup S$, all the prime divisors of $t-1$ are in $S$. Note $S$ and $A$ are disjoint, since for all $a \in A$ the number $a-1$ is even, so every prime dividing $a-1$ is at most $\frac{a-1}{2} < \text{min}(A)$. Let $B$ be a large number much larger than $|A|$, and consider the number$$n=\left( \displaystyle\prod\limits_{s \in S} s^{2^B-1} \right) \left( \displaystyle\prod\limits_{a \in A} a \right).$$Note $\varphi(d(n))=\varphi(2^{B|S|+|A|})=2^{B|S|+|A|-1}$. By our definition of $S$,$$\varphi(n)=\displaystyle\prod\limits_{s \in S}s^{2^B-1+\varepsilon_s}$$for some values of $\varepsilon_s$ much smaller than $B$. Hence $d(\varphi(n)) \approx 2^{B|S|}$, and$$\frac{\varphi(d(n))}{d(\varphi(n))} \approx 2^{|A|-1}$$which is arbitrarily large.
20.07.2021 23:48
We claim such a constant does not exist. Let $N$ denote a huge positive integer. Let $p_1,p_2, \cdots , p_{\pi(N)}$ denote the primes atmost $N$ and let $p_{\pi(N)+1}, p_{\pi(N)+2}, \cdots , p_{\pi(2N)}$ denote the primes between $N$ and $2N$. Define $A= \prod_{i=1}^{\pi(N)} p_i$ and $B= \prod_{i=\pi (N)+1}^{\pi(2N)} p_i$ The key observation is that $$ \varphi (AB) = \prod_{i=1}^{\pi (N)} p_i^{a_i}$$ for some non negative integers $a_i$. This is because for $i> \pi(N)$, $p_i-1$ is not divisible by a prime $>N$. For huge primes $q$ and $r$, we commit to the choice $n=A^{q-1}B^{r-1}$. We have : $$ \varphi ( \tau (n)) = \varphi ( q^{\pi (N)} \cdot r^{\pi (2N)- \pi (N)} ) = (q-1)(r-1) q^{\pi (N)-1} r^{\pi(2N)-\pi(N)-1}$$ Also we have: $$ \tau ( \varphi (n)) = \tau ( A^{q-2} \cdot B^{r-2} \cdot \phi (AB) ) = (r-1)^{\pi(2N)-\pi(N)} \cdot \left( \prod_{i=1}^{\pi (N)} (q+a_i-1) \right)$$ So we have : $$ \frac {\varphi ( \tau n ))} { \tau ( \varphi (n))} = \frac {q-1}{q} \cdot \frac {r-1}{r} \cdot \left( \prod_{i=1}^{\pi(N)} \frac {q}{q+a_i-1} \right) \cdot \left( \frac {r}{r-1} \right)^{\pi(2N)-\pi(N)-1}$$ Now we claim that $\pi(2N)-\pi(N)$ is unbounded, which implies the result. By the prime number theorem, we have : $$ \lim_{n \rightarrow \infty} \frac { \pi(2n)-\pi(n)}{ \tfrac n{\log n} } = 1$$ Hence $\pi(2n)-\pi(n)$ is asymptotic to $\tfrac n {\log n}$, which is unbounded, so we are done. $\square$
21.07.2021 03:48
I'm kinda curious about the motivation behind this problem... like why would one want to investigate on the boundedness of this quantity... Does anyone have a good explanation for this? Otherwise composing two random functions and dividing them seems too unmotivated for me...
22.07.2021 08:45
This is probably not the answer and Solution one would expect from a high N problem of the SL. The answer is $\color{red} \boxed{\boxed{\text{No.}}}$ In fact, we will prove that for every $C = 2^l$, there exists a $n \in \mathbb{N}$ such that \[ \dfrac{\varphi{(d(n))}}{d(\varphi{(n)})} > 2^l. \]First, we state a claim on the distribution of primes:
$\color{cyan} \rule{6.2cm}{2pt}$ $\color{cyan} \clubsuit$ $\boxed{\textbf{Why does PNT Spam Work.}}$ $\color{cyan} \clubsuit$ $\color{cyan} \rule{6.2cm}{2pt}$ Given $k \in \mathbb{N}$. Then, there exists a $N$ such that the number of primes between $N$ and $2N$ is greater than $k$. $\color{cyan} \rule{25cm}{0.2pt}$ $\color{cyan} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{cyan} \spadesuit$ If there does not exist such $N$, then the number of primes between $[1,2^M]$ for any $M$ will be at most $Mk$. This is obtained by dividing that interval into $M$ intervals in the form $(a,2a)$ as follows: \[ [1,2]; [2,4]; \ldots, [2^{M-1},2^M]. \]However, PNT has done the work in contradicting this: we know that \[ \pi(2^M) \sim \dfrac{2^M}{\log{(2^M)}} \geq c \cdot \dfrac{2^M}{M} \]which cannot be smaller than $O(M)$ for $M$ large. A contradiction. Alternatively, we can establish this by $\textbf{Generalization of Bertrand's Postulate}$ (see the wikipedia article): it claims that given $\epsilon > 0$, there must exist a prime between $n$ and $(1+\epsilon)n$ for $n$ large. Setting $\epsilon = \sqrt[k]{2}$ settles this. $\color{green} \rule{25cm}{0.2pt}$ Unsurprisingly, the ingenuity lies in the construction of $n$ as follows: $\color{magenta} \rule{10cm}{2pt}$ $\color{magenta} \diamondsuit$ $\boxed{\textbf{The Lucky Break (Insert Maniacal Laugh Emoji).}}$ $\color{magenta} \diamondsuit$ $\color{magenta} \rule{10cm}{2pt}$ Pick $N$ so that the number of primes between $N$ and $2N$ is at least $l+2$. Let this number (i.e. $\pi(2N)-\pi(N)$) to be $L$. We Claim that \[ n = \prod_{1 < p_i < N} p_i^{p_{m+i}-1} \prod_{N < p < 2N} p \]satisfies the assertion in the beginning of this Solution. Note: $m$ is to be determined later, with $p_i$ being the $i^{\text{th}}$ prime, arranged in increasing order. $\color{magenta} \rule{25cm}{0.2pt}$ Denote $P$ and $\varphi(P)$ to be \[ P = \prod_{N < p < 2N} p, \quad \varphi(P) = \prod_{1 < p_i < N} p_i^{\alpha_i}. \]We can write $\varphi(P)$ as follows since $q \mid p-1$, $p < 2N$ implies $q < N$. Now we count the weird expressions $\varphi{(d(n))}$ and $d(\varphi{(n)})$. The former expression is \[ \varphi(2^L \cdot \prod p_{m+i}) = 2^{L-1} \prod(p_{m+i}-1) \]and the latter expression is \begin{align*} & \quad \ d\left(\prod p_i^{p_{m+i}-2} \cdot \prod_{1<p_i<N} (p_i-1) \prod_{N < p < 2N} (p-1)\right)\\ &= d\left(\prod p_i^{p_{m+i}-2} \cdot \prod_{1<p_i<N} p_i^{\beta_i} \prod_{1 < p_i < N} p_i^{\alpha_i}\right) \\ &= d\left(\prod p_i^{p_{m+i}+\alpha_i+\beta_i-2}\right) \\ &= \prod_{i, 1 < p_i < N} (p_{m+i}+\alpha_i+\beta_i-1) \\ \end{align*}letting $\varphi\left(\prod p_i \right)$ to be the product of $p_i^{\beta_i}$. This may seem grim, but note that $p_{m+i}$ may be adjusted as big as we want, to make the lopsided fraction \[ \dfrac{p_{m+i}-1}{p_{m+i} + \text{some fixed constant}} \]as close to $1$ as possible; while keeping the already big number $2^{L-1}$ unaffected. We select $m$ with this in mind. Set $m$ so that \[ \dfrac{p_m-1}{p_m-1+\max{(\alpha_i+\beta_i)}} > \dfrac{1}{\sqrt[N]{2}}. \]This will imply the inequality with all $p_m$ replaced with $p_{m+i}$ for every $1 \leq i \leq \pi(N)$, as \[ \dfrac{a}{b} \leq \dfrac{a+c}{b+c} \]when $\dfrac{a}{b} \leq 1$. So, \begin{align*} \dfrac{\varphi{(d(n))}}{d(\varphi{(n)})} &= 2^{L-1} \prod \dfrac{p_{m+i}-1}{p_{m+i}-1 + \alpha_i + \beta_i} \\ &> 2^{L-2} \cdot 2 \prod_{1 < p_i < N} \dfrac{1}{\sqrt[N]{2}} \\ &= 2^{L-2} \cdot 2 \cdot 2^{\frac{\pi(N)}{N}} \geq 2^{L-2} \geq 2^l. \\ \end{align*}We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$
23.07.2021 05:17
02.08.2021 23:44
Quote: For a positive integer $n$, let $d(n)$ be the number of positive divisors of $n$, and let $\varphi(n)$ be the number of positive integers not exceeding $n$ which are coprime to $n$. Prove that for any number $C$ , there exist an integer $n$ for which $$ \frac {\varphi ( d(n))}{d(\varphi(n))}> C$$
11.08.2021 16:47
The answer is No. Denote by $\pi(n)$ the number of primes not exceeding $n$. Claim. The quantity $\pi(2n)-\pi(n)$ is unbounded. Proof We can use PNT, but this is unnecessary. Assume $\pi(2n)-\pi(n)$ is bounded for all positive integers $n$. Hence there exists a constant $c$ such that $\pi(2^a)\le ac$ for all positive integers $a$. Pick any positive integer $a$. On the one hand, $$\binom{2^a}{2^{a-1}}=2\binom{2^a-1}{2^{a-1}-1}\ge 2\cdot\frac{2^{2^a-1}}{2^a}=\frac{2^{2^a}}{2^a}=2^{2^a-a}$$On the other hand, every prime $p$ dividing $\binom{2^a}{2^{a-1}}$ is at most $2^a$. By Legendre's formula, $$v_p\left(\binom{2^a}{2^{a-1}}\right)=\sum_{k=1}^{\infty}\left(\left\lfloor\frac{2^a}{p^k}\right\rfloor-2\left\lfloor\frac{2^{a-1}}{p^k}\right\rfloor\right)\le\sum_{k=1}^{\log_p(2^a)} 1=\log_p(2^a)$$Hence, $$\binom{2^a}{2^{a-1}}=\prod_{p\le 2^a}p^{v_p\left(\binom{2^a}{2^{a-1}}\right)}\le \prod_{p\le 2^a}p^{\log_p(2^a)}=(2^a)^{\pi(2^a)}\le 2^{a^2c}$$Therefore $2^a-a\le a^2c$ for all positive integers $a$. Obviously a large $a$ gives a contradiction. $\blacksquare$ Now let $q>2$ be a large prime number. For a suitable choice of $n$, consider $$N=\left(\prod_{p\le n}p\right)^{q-1}\cdot\left(\prod_{n<p\le 2n}p\right)$$We claim that $\frac{\varphi(d(N))}{d(\varphi(N))}$ can be as large as we want. Write $d=\pi(n)$ and $k=\pi(2n)-\pi(n)$. observe that $$\varphi(d(N))=\varphi(q^d 2^k)=(q-1)q^{d-1}2^{k-1}$$Note that for a prime $p\in [n+1,2n]$, $p-1=2\cdot\frac{p-1}{2}$ is divisible by only primes not exceeding $n$. Hence we can write $$\varphi\left(\prod_{p\le 2n}p\right)=\prod_{p\le n} p^{a_p}$$and note that the $a_p$ are independent from $q$. Therefore $$d(\varphi(N))=d\left(\prod_{p\le n} p^{q-2+a_p}\right)=\prod_{p\le n}(q-1+a_p)$$Combine all results to obtain $$\frac{\varphi(d(N))}{d(\varphi(N))}=\frac{(q-1)q^{d-1}2^{k-1}}{\prod_{p\le n}(q-1+a_p)}=\frac{(q-1)2^{k-1}}{q}\cdot\prod_{p\le n}\frac{q}{q-1+a_p}$$By taking $q$ to be a large enough prime we can get closer to $2^{k-1}$ as we want. Now $k$ is unbounded by the claim, so we are done.
11.08.2021 17:52
The problem was proposed by Demetres Christofides (aka Demetres in AoPS).
25.08.2021 08:04
The answer is no, and we construct the following counterexample: Fix $k$. Let $p_1, p_2, \ldots, p_{\pi (k)}, \ldots, p_{\pi (2k)}$ be the primes between $1$ and $2k$. Our construction takes the form $$n = \prod_{p_i \le k} p_i^{A} \prod_{k < q_i \le 2k} q_i$$where $A = 2^{B} - 1$ for $B$ sufficiently large. First, note $d(n) = (A+1)^{\pi (k)} 2^{\pi (2k) - \pi (k)} = 2^{(B-1)\pi (k) + \pi (2k) }$. Since $d(n)$ is a power of $2$, $\varphi (d(n)) = d(n)/2 = (A+1)^{\pi (k)} 2^{\pi (2k) - \pi (k) - 1}$. On the other hand, $\varphi (n) = \prod_{p_i \le k} p_i^{A-1} \prod_{q_i \le 2k} (q_i - 1)$. Denote $M_k = \prod_{q_i \le 2k} (q_i - 1)$; then we may write $\varphi (n) = \prod_{p_i \le k} p_i^{A-1 + v_{p_i}(M_k)}$ since the only primes dividing $M_k$ must be at most $k$ (since a prime divisor of $q_i - 1$ is at most $\frac{q_i - 1}{2} < k$ since $q_i$ are odd for $q_i > 2$). This means $d(\varphi(n)) = \prod_{p_i \le k} (A + v_{p_i}(M_k))$. Now the rest is clear: we have $$\frac{\varphi (d(n))}{d(\varphi(n))} = 2^{\pi (2k) - \pi (k) - 1}\prod_{p_i \le k} \left(\frac{A+1}{A + v_{p_i}(M_k)}\right) $$Since $k$ is fixed, $v_{p_i}(M_k)$ are fixed for all $i\le \pi (k)$, and we can choose $A = 2^B - 1$ sufficiently large such that $\frac{A+1}{A + v_{p_i} (M_k)} > 2^{-1/69}$. This means for each $k$, there exists $n$ such that $\frac{\varphi (d(n))}{d(\varphi(n))} > 2^{\pi (2k) - 70/69\pi (k) - 1}$. But now by the Prime Number Theorem, since $\pi (2k) - 70/69\pi (k) - 1\uparrow \infty$ as k$\uparrow \infty$, we get that $\frac{\varphi (d(n))}{d(\varphi(n))}$ is unbounded, as desired.
04.09.2021 08:08
Probably the shortest solution yet: $\color{black} \rule{25cm}{2.5pt}$ Claim: The quantity $\pi(2n)-\pi(n)$ is unbounded. Proof: This is pretty well known. Note that $\pi(2n)-\pi(n)>\frac{\text{In } 4}{3} \cdot \frac{n}{\text{In } 2n}-\sqrt{\frac{n}{2}}>\frac{\text{In }4}{3} \cdot \frac{n}{\text{In } n}$ which tends to $\inf$ when $n \rightarrow \inf$ $\color{black} \rule{25cm}{2.5pt}$ Choose $\left(\prod_{i=1}^{\pi(N)} p_i \right)^{q-1} \left(\prod_{i=\pi (N)+1}^{\pi(2N)} p_i \right)^{r-1}$ where $q,r$ are sufficiently large primes. Computing,$ \frac {\varphi ( \tau (n) ))} { \tau ( \varphi (n))} = \frac {q-1}{q} \cdot \frac {r-1}{r} \cdot \left( \prod_{i=1}^{\pi(N)} \frac {q}{q+a_i-1} \right) \cdot \left( \frac {r}{r-1} \right)^{\pi(2N)-\pi(N)-1}$ which is unbounded hence the answer is $\boxed{\text{No}}$
06.01.2022 11:20
Aryan-23 wrote: For a positive integer $n$, let $d(n)$ be the number of positive divisors of $n$, and let $\varphi(n)$ be the number of positive integers not exceeding $n$ which are coprime to $n$. Does there exist a constant $C$ such that $$ \frac {\varphi ( d(n))}{d(\varphi(n))}\le C$$for all $n\ge 1$ Cyprus I think this is one of the best NT constructions I have done. Solved with squareman. Choose and fix a very big positive integer \(N\). From now, let \(p_i\) denote the \(i\)-th prime number. We take it for granted that \(\pi(2N)-\pi(N)\) is unbounded. Let \[n=\left(\prod_{i=1}^{\pi(N)}p_i\right)^{q-1}\times\left(\prod_{j=\pi(N)+1}^{\pi(2N)}p_j\right)\]where \(q\) is a large prime. Then, we see that \[\frac{\phi(d(n))}{d(\phi(n))}=\frac{q(q-1)^{\pi(N)}\cdot2^{\pi(2N)-\pi(N)-1}}{d\left(p_1^{q-2+c_1}\cdots p_{\pi(N)}^{q-2+c_{\pi(N)}}\right)}=\frac{q(q-1)^{\pi(N)}\cdot2^{\pi(2N)-\pi(N)-1} }{\prod_{l=1}^{\pi(N)}(q-2+c_l)}\]Where \(c_1, c_2,\hdots, c_{\pi(N)}\) are constants independent of \(q\) and \(c=\max\{c_1,..,c_{\pi(N)}\}\). This is because \(p_i\), for all \(i>\pi(N)\) have their prime factors in \(p_1, p_2,\hdots, p_{\pi(N)}\). Since \(\pi(2N)-\pi(N)-1\) is unbounded, the expression above is unbounded too (since \(q,c\) are fixed) by varying \(N\). Therefore, there does not exist such a constant \(C\).
30.03.2023 18:08
对固定的整数 $N>1$, 设 $p_1,p_2,\cdots ,p_k$ 是 ${1}$ 至 ${N}$ 中的所有素数, $p_{k+1},p_{k+2},\cdots ,p_{k+s}$ 是 $N+1$ 至 $2N$ 中的所有素数. 由于对 $\forall 1\le j\le k+s$, $p_j-1$ 的素因子不超过 $N$, 因此可设 $$\prod\limits_{j=1}^{k+s}(p_j-1)=\prod\limits_{i=1}^{k}p_i^{c_i},$$其中 $c_1,c_2,\cdots ,c_k$ 为固定的非负整数. 对于充分大的素数 ${q}$, 令 $$n=\left(\prod\limits_{i=1}^{k}p_i\right)^{q-1}\cdot\prod\limits_{i=k+1}^{k+s}p_i.$$则 $$\varphi ( \tau (n))=\varphi ( q^k\cdot 2^s)=q^{k-1}(q-1)2^{s-1},$$$$\begin{aligned}\tau ( \varphi (n))&=\tau\left(\left(\prod\limits_{i=1}^{k}p_i\right) ^{q-2}\prod\limits_{i=1}^{k+s}(p_i-1)\right)\\ &=\tau\prod\limits_{i=1}^{k}p_i^{q-2+c_i}=\prod\limits_{i=1}^{k}(q-1+c_i).\end{aligned}$$于是 $$\frac {\varphi ( \tau (n))}{\tau (\varphi(n))}=2^{s-1}\cdot\frac{q-1}{q}\cdot\prod\limits_{i=1}^{k}\frac{q}{q-1+c_i}.$$当 ${q}$ 充分大时, $\frac {\varphi ( \tau (n))}{\tau (\varphi(n))}\to 2^{s-1}$. 由 Bertrand-Chebyshev 定理, 存在 ${N}$ 使得 $N+1$ 至 $2N$ 中有任意多个素数, 即 ${s}$ 可任意大. 因此 $\frac {\varphi ( \tau (n))}{\tau (\varphi(n))}$ 可任意大, 不存在满足条件的 ${C}.\blacksquare$
29.05.2023 04:28
rolled this unfortunately in marabot, solved with my friend: The answer is no, and we construct a counterexample as follows. Let $P_1$ be the set of all primes less than $N$ for some arbitrary $N > 2$, and let $P_2$ be the set of primes in between $N$ and $2N$. I claim that \[ n = \left( \prod_{p_k \in S_1} p_k^{2^X - 1} \right) \cdot \left(\prod_{q_k \in S_2} q_k \right) \]works for some $X \gg |P_1|, |P_2|$. We have that \[\varphi(d(n)) = \varphi(2^{X|P_1|+|P_2|}) = 2^{X|P_1|+|P_2| - 1}.\]However, since all prime factors of $q_k - 1$ for $q_k \in P_2$ are in $P_1$, we have (for some insignificant $\epsilon_1, \epsilon_2, ... \epsilon_{|S_1|}$) that \[\varphi(n) = \prod_{p_k \in P_1} p_k^{2^X-1+\epsilon_k} \implies d(\varphi(n)) \approx 2^{X|P_1|}\]which means that \[\frac {\varphi ( d(n))}{d(\varphi(n))} \approx 2^{|P_2|-1}.\]Hence it suffices to show that $|P_2| $ is unbounded, which is true by PNT.
29.05.2023 08:43
Wait can't you just say that since phi(n) = product of all p|n (1-(1/p)), and d(n) is the product of 1+ the exponents, all 1+ exponents must be prime, so since product of primes is not bounded, denominator is not, and then for numerator CAN YOU DO SOMETHING HERE TO PROVE THIS IS NOT BOUNDED? and thus such a C does not exist
27.06.2023 21:21
The answer is no. Fix a large integer $m$. Call a prime small if it is at most $m$ and large if it is greater than $m$ but at most $2m$. Let $p_1<\ldots<p_k$ be the small primes and $q_1<\ldots<q_l$ be the large ones. The idea is to consider a prime $P$ and take $$n=p_1^{P-1}\ldots p_k^{P-1}q_1\ldots q_l.$$Then it is clear that $d(n)=P^k2^l \implies \varphi(d(n))=(P-1)P^{k-1}2^{l-1}$. On the other hand, observe that for any large prime $q_i$, we have that $\varphi(q_i)=q_i-1=2\cdot \tfrac{q_i-1}{2}$ is the product of small primes. Furthermore, if we vary $P$, the value of $\tfrac{\varphi(n)}{n}$ remains the same, so by selecting a massive $P$ we can make it so that each of the exponents of the small primes increases by a factor of at most $\sqrt[k]{2}$ when applying $\varphi$. Then we find that $$d(\varphi(n))\leq (\sqrt[k]{2}P)^k=2P^k.$$Hence, $$\frac{\varphi(d(n))}{d(\varphi(n))}\geq \frac{P-1}{P}2^{l-2}.$$But for large $m$, by using the Prime Number Theorem, $l=\pi(2m)-\pi(m)$ is unbounded above, while $\tfrac{P-1}{P}$ is always at least $\tfrac{1}{2}$, so by sending $m \to \infty$ we find that the expression is unbounded.
29.01.2024 16:06
Funny problem, The answer is no, we show that that the function is unbounded, the idea is to choose $\left(\mathcal{R} = \prod_{i=1}^{\pi{(n)}} p_i \right),\left( \mathcal{S} = \prod_{i=\pi{(n)} +1}^{2\pi{(n)}} p_i \right)$, choose $\quad n = {\mathcal{R}}^{q-1}{\mathcal{S}}^{r-1} \quad$for huge primes $q$ and $r$. Notice $\varphi(\tau(n)) = \varphi(q^{\pi(n)} \cdot r^{\pi(2n)-\pi(n)}) = (q-1)(r-1)q^{\pi(n)-1}r^{\pi(2n)-\pi(n)-1}$ $\tau(\varphi(n)) = \tau({\mathcal{R}}^{q-2} \cdot {\mathcal{S}}^{r-2} \cdot \varphi{(\mathcal{R} \mathcal{S})})=(r-1)^{\pi(2n)-\pi(n)} \cdot \left( \prod_{i=1}^{\pi(n)} (q+a_i-1) \right)$ where $\varphi(\mathcal{R} \cdot \mathcal{S}) = \prod_{i=1}^{\pi(n)} p_i^{\alpha_i}$, by PNT $\pi(2n)-\pi(n)$ is unbounded, so we are done.
12.02.2024 17:30
Solved with mathboy100. The answer is no. First we prove the following claim: Claim: For every positive integer $x > 100$, if there are $k$ primes strictly in between $x$ and $2x$, there exists a positive integer $n$ with $f(n) > 2^{k-1} - 1$. Proof: Suppose there were $m$ primes less than or equal to $x$. Let the distinct primes less than $2x$ be $p_1, p_2, \ldots, p_{m+k}$ in increasing order. Additionally, let $P$ be a sufficiently large prime. Consider\[ n = \left( \prod_{i=1}^m p_i \right)^{P - 1} \cdot \prod_{i=m+1}^{m+k} p_i \]Notice for each $1 \le i \le m + k$, $p_i - 1$ We see that $d(n) = 2^k \cdot P^m$, so $\varphi(d(n)) = 2^{k-1} (P - 1) \cdot P^{m-1}$. Now we have that $\varphi(n) = \left( \prod_{i=1}^m p_i \right)^{P - 2} \cdot \prod_{i=1}^{m+k} (p_i - 1)$. We first show that $p_i - 1$ contains only prime factors less than $x$ for each $1\le i \le m + k$. This is obvious for $1\le i \le m$. For $i > m$, notice that since $m > 2$, $p_i - 1$ is composite and less than $2x$. Hence its largest prime factor is at most $\frac{p_i - 1}{2} < x$, as desired. Now for each $1\le t \le m$, let $\nu_{p_t} \prod_{i=1}^{m+k} (p_i - 1) = a_t$. Note that $\varphi(n) = \prod_{i=1}^m p_i^{P - 2 + a_i} $, hence $d(\varphi(n)) = \prod_{i=1}^m (P - 1 + a_i)$. Altogether,\[ f(n) = \frac{2^{k-1} (P - 1) \cdot P^{m-1} }{ (P - 1 + a_1) \cdot (P - 1 + a_2) \cdots (P - 1 + a_m) }\]Since $(a_i)$ doesn't depend on $P$ (it only depends on $x$), we see that the fraction for $f(n)$ approaches $2^{k-1}$ as $P$ approaches infinity. Therefore, if we take $P$ large enough, we will find some $n$ where $f(n) > 2^{k-1} - 1$. $\square$ Now, for each integer $x>100$, the number of primes strictly in between $x$ and $2x$ is just $\pi(2x) - \pi(x)$, where $\pi$ denotes the prime counting function. By the Prime Number Theorem, $\pi(2x) - \pi(x)$ is unbounded above. This means that $f(n) > 2^{k-1} - 1$ for arbitrarily large $k$, so $f(n)$ is unbounded above, as desired.
21.05.2024 05:13
The answer is no. Note that by PNT, the function $\pi(2n)-\pi(n)$ is unbounded. Let $\pi(2n)-\pi(n)=X$. Let $p_i$ denote the $i$th smallest prime. Then, let \[n=\prod_{i=1}^{\pi(n)} p_i^{q-1} \prod_{i=\pi(n)+1}^{\pi(2n)} p_i^{r-1}\]for some primes $q$, $r$. The numerator of the expression is \[\varphi(d(n))=\varphi(q^{\pi(n)}r^{X})=(q-1)(r-1)q^{\pi(n)-1}r^{X-1}\]and the denominator is \[d(\varphi(n))=d\left(\left(\prod_{i=1}^{\pi(2n)}(p_i-1)\right)\left(\prod_{i=1}^{\pi(n)}(p_i^{q-2})\right)\left(\prod_{i=\pi(n)+1}^{\pi(2n)}(p_i^{r-2})\right)\right)\]The important thing to note is that if $d$ is a prime divisor of $p_i-1$ then $d\le n$ since $p_i-1$ is either even or small. Therefore, the following expressions are coprime: \[\left(\prod_{i=1}^{\pi(2n)}(p_i-1)\right)\left(\prod_{i=1}^{\pi(n)}(p_i^{q-2})\right);\prod_{i=\pi(n)+1}^{\pi(2n)}(p_i^{r-2})\]Let \[\prod_{i=1}^{\pi(2n)}(p_i-1)=\prod_{i=1}^{\pi(n)}\left(p_i^{e_i}\right)\]then \[d(\varphi(n))=(r-1)^{X}\prod_{i=1}^{\pi(n)}(e_i+q-2)\]So in total we have \[\frac{\varphi(d(n))}{d(\varphi(n))}=\frac{(q-1)q^{\pi(n)-1}}{\prod_{i=1}^{\pi(n)}(e_i+q-2)}\cdot \left(\frac{r}{r-1}\right)^{X-1}\]Increasing $X$ makes the right factor unbounded and increasing $q$ makes the left factor insignificant. We are done.
05.07.2024 10:52
The answer is no. such $C$ does not exist. We give a construction of $n$ for which $\frac{\phi(d(n))}{d(\phi(n))}$ gets arbitarily large. For large positive integer $N$ consider a number like $(p_1)^{{b_1}}*(p_2)^{b_2}....*(p_N)^{b_N}$ where $b_i+1$ is always prime. where if $j$ is the smallest positive integer such that $p_j \geq p_N0.99$ we set $b_j=b_{j+1}=....=b_N=1$ and choose rest $b_i$'s to be distinct large number of form prime-1. Observe $\frac{\phi(d(n))}{d(\phi(n))}=\frac{b_1b_2....b_{j-1} (2)^{N-j}}{d((p_1)^{b_1-1}(p_2)^{b_2-1}.....(p_{j-1})^{b_{j-1}} (p_1-1)....(p_N-1))}$ Observe $(p_1)^{b_1-1}(p_2)^{b_2-1}.....(p_{j-1})^{b_{j-1}} (p_1-1)....(p_N-1))=(p_1)^{b_1-1+c_1} (p_2)^{b_2-1+c_2}*.....(p_{j-1})^{b_{j-1}+c_{j-1}}$ [ all factors of the $p_i-1$ product are in $p_1,p_2,....,p_{j-1}$] The whole thing simplfies to $\frac{b_1}{b_1+c_1}\frac{b_2}{b_2+c_2}....\frac{b_{j-1}}{b_{j-1}+c_{j-1}}2^{N-j}$ By stronger version of bertands $N-j$ gets arbitarily large and we can keep the other terms $<1$ get arbiarily close to $1$ by keeping the rest $b_i$'s really large so we can reach arbiarily close to $2^{N-j}$ this means the value can get arbitarily large
07.08.2024 16:55
We claim there does not exist such a constant. Let $p_1 < p_2 < p_3 < \dots$ be the primes. Let $N \in \mathbb{Z}$. Define $k$ and $m$ such that $p_k \le 2^N < p_{k+1}$ and $p_m \le 2^{N+1} < p_{m+1}$. Claim: $m-k$ can be arbitrarily high depending on the choice of $N$. Proof: Assume towards a contradiction this is false. Then, there is some constant $\alpha$ such that there are at most $\alpha$ primes between $2^N$ and $2^{N+1}$. Then, the number of primes below $2^N$ is at most $\alpha N$, which contradicts the prime number theorem. $\blacksquare$ Let $P$ be a prime. Let \[n = (p_1\dots p_k)^{P-1}p_{k+1}\dots p_m.\]Assume $p_j\mid p_i - 1$ for $i \le m$. Then, $p_j \le \frac{p_i-1}2 < 2^N$. So, $j\le k$. So, for some $a_1, \dots, a_k$, \[(p_1-1)\dots (p_n-1) = p_1^{a_1}\dots p_k^{a_k}.\]So, \[\frac{\varphi(d(n))}{d(\varphi(n))} = % \frac{\varphi(P^k2^{m-k})}{d(p_1^{a_1+P-2}\dots p_k^{a_k+P-2})} = % \frac{(P-1)P^{k-1}2^{m-k-1}}{(P+a_1-1)\dots (P+a_k-1)}.\]For sufficiently high values of $P$, $\frac{(P-1)P^{k-1}}{(P+a_1-1)\dots (P+a_k-1)}$ can become arbitrarily close to $1$. So, the expression can become arbitrarily close to $2^{m-k-1}$, which we have previously shown can be arbitrarily high.