If $n=1$ then $\varphi(n)+d(n)=2=n+1$. Suppose $n>1$. In this case we have all $d(n)$ divisors of $n$ except 1 are not coprime with $n$. It follows that \[\varphi(n)+d(n)\leq n+1.\] Moreover, 1) $\varphi(n)+d(n)=n+1$ $\Leftrightarrow$ if $m<n$ and $(m,n)>1$ then $m\,|\,n$ (*). 2) $\varphi(n)+d(n)=n$ $\Leftrightarrow$ for all $m$ s.t. $m<n$ and $(m,n)>1$ we have $m\,|\,n$ and this rule has exactly 1 exception (**). Now we consider these cases. 1) If $n$ is prime or $n=4$ then $\varphi(n)+d(n)=n+1$. Suppose $n$ is composite number and $n\neq 4$. It implies that $n=ab$, $a,b\in\mathbb{N}$, $a\geq 2$ $b\geq 3$. Consider $m=a(b-1)$. We have $(m,n)=a>1$ and $n$ isn't divisible by $m$ -- contradiction with (*). 2) Suppose $n$ isn't prime and $n\neq 4$. If $n=6$, $n=8$, $n=9$ or $n=12$ then $\varphi(n)+d(n)=n$. Suppose $n\neq 6$. There are some subcases: 2.1. $n=p^k$, where $p$ is prime number, $k\geq 2$. In this case $\varphi(n)=p^k-p^{k-1}$ and $d(n)=k+1$, so $\varphi(n)+d(n)=n-(p^{k-1}-(k+1))$, hence we search for equality $p^{k-1}-(k+1)=0$. 2.1.1. If $p=2$ then $k\geq 4$ (since $n\neq 4,8$) and using unduction it is easy to show that $2^{k-1}-(k+1)>0$; 2.1.2. If $p=3$ then $k\geq 3$ (since $n\neq 9$) and using unduction we show $3^{k-1}-(k+1)>0$. 2.1.3. If $p\geq 5$ then $p^{k-1}-(k+1)>0$. Conclusion: case 2.1 doesn't give new values for $n$. 2.2. $n=p^kq^ls$, where $p<q$ are maximal distinct prime divisors, $s\geq 1$. 2.2.1. $p,q\geq 3$. Consider $m_1=(p^k-1)q^ls$ and $m_2=p^k(q^l-1)s$. We have $m_1$ and $m_2$ are two exception from (**) -- contradiction. 2.2.2. $p=2$ $\Rightarrow$ $s=1$, so $n=2^kq^l$. 2.2.2.1. $q=3$ and $l=1$. In this case $k\geq 3$ (since $n\neq 6,12$). Consider $m_1=3\cdot 3$ and $m_2=5\cdot 3$ -- contradiction with (**). 2.2.2.2. $q=3$ and $l\geq 2$. Consider $m_1=2\cdot 5$ and $m_2=2\cdot 7$ -- contradiction with (**). 2.2.2.3. $q\geq 5$. Consider $m_1=2\cdot 3$ and $m_2=2^k\cdot (q-1)$ -- contradiction with (**). Conclusion: case 2.2 doesn't give new values for $n$.

valentin where do you find cwmo problems?

zhaoli posted CWMO 2001, 2002, 2003 and 2004 http://www.mathlinks.ro/Forum/viewtopic.php?t=15596 http://www.mathlinks.ro/Forum/viewtopic.php?p=124375 http://www.mathlinks.ro/Forum/viewtopic.php?p=124142

Myth wrote: zhaoli posted CWMO 2001, 2002, 2003 and 2004 http://www.mathlinks.ro/Forum/viewtopic.php?t=15596 http://www.mathlinks.ro/Forum/viewtopic.php?p=124375 http://www.mathlinks.ro/Forum/viewtopic.php?p=124142 ah ic, thx myth Do you think that the papers are becoming easier ?? Personally i think cwmo 2004 looks easier than 2003 one.

Actually, I didn't compare them, because I have no time to carefully read CWMO 2003.

Myth wrote: Actually, I didn't compare them, because I have no time to carefully read CWMO 2003. ic.

What is "ic" ?

Spell it to hear it....you will see... Pierre.

who know CGMO for china girl MO

For all non-negative integers $c$ , $c\in\mathbb{N}$ what can we say about the solutions of \[ n + 1 - d(n) - \varphi(n) = c , \] and for each such $c$ we may have solutions (a finite set always?) Does exist a subsequence of non-negative integers such that $ \frac{d(n) + \varphi(n)}{n}$ tends to 0 - yes or we can get in terms of some elementary function also a lower bound: \[ L(n) \leq d(n) + \varphi(n) \leq n+1 \]

Consider $n_k=p_1p_2...p_k$, where $p_k$ is a sequnce of all prime numbers. Then $d(n_k)=2^k$ and $\varphi(n)=(p_1-1)...(p_k-1)$. And we have $\frac{d(n_k)}{n_k}\to 0$ and $\frac{\varphi(n_k)}{n_k}\to 0$ (last one is not so obvious, but it is equaivalent to $\frac{1}{p_1}+...+\frac{1}{p_k}\to +\infty$ as $k\to +\infty$).

I knew these and i wrote because it seems related, but i wonder for the 1st part which is the answer and for the lower bound $ L(n) $ if we can express using only a combination of rational, logarithmic and exponential.

I think I can prove something like $\frac{n}{\ln^2(n+1)}<\varphi(n)$. In the same time $d(p)=2$ for all prime numbers $p$, so there are no estimates.

Myth wrote: Consider $n_k=p_1p_2...p_k$, where $p_k$ is a sequnce of all prime numbers... $\varphi(n)=(p_1-1)...(p_k-1)$... $\frac{\varphi(n_k)}{n_k}\to 0$ (last one is not so obvious, but it is equaivalent to $\frac{1}{p_1}+...+\frac{1}{p_k}\to +\infty$ as $k\to +\infty$). $n_k=p_1p_2...p_k$ is the primordial, while the fact $\frac{\varphi(n_k)}{n_k}\to 0$ has an elementary proof, by considering for example a set of integers from $1$ to some given value $a$ , $A=${$1,2,...,a$} and the subset of $A$ , $B$ that contains only integers from $A$ that does not divide with any of the primes $p_i$. It follows that $\frac{(p_1-1)(p_2-1)...(p_k-1)}{p_1p_2...p_k}\to 0$ by making $a$ large enough as $k\to +\infty$.

heartwork wrote: Myth wrote: Consider $n_k=p_1p_2...p_k$, where $p_k$ is a sequnce of all prime numbers... $\varphi(n)=(p_1-1)...(p_k-1)$... $\frac{\varphi(n_k)}{n_k}\to 0$ (last one is not so obvious, but it is equaivalent to $\frac{1}{p_1}+...+\frac{1}{p_k}\to +\infty$ as $k\to +\infty$). $n_k=p_1p_2...p_k$ is the primordial, while the fact $\frac{\varphi(n_k)}{n_k}\to 0$ has an elementary proof, by considering for example a set of integers from $1$ to some given value $a$ , $A=${$1,2,...,a$} and the subset of $A$ , $B$ that contains only integers from $A$ that does not divide with any of the primes $p_i$. It follows that $\frac{(p_1-1)(p_2-1)...(p_k-1)}{p_1p_2...p_k}\to 0$ by making $a$ large enough as $k\to +\infty$. No, it is not clear for me. Maybe I am missing something.

Fix an integer $a$ , $A=${$1,2,...,a$}. Construct $B$ by eliminating step by step all integers which are multiple of $p_1$, $B$ will have at most $\frac{(p_1-1)}{p_1}B$ elements, then eliminate from this new set all integers which are multiple of $p_2$, then $B$ will have at most $\frac{(p_2-1)}{p_2}\frac{(p_1-1)}{p_1}B$ elements and so on, for $p_k$ large enough $B$ will contain only $1$, so $\frac{|B|}{|A|}\to 0$ as both $k\to +\infty$ and $a\to +\infty$. I hope it is correct.

heartwork wrote: Construct $B$ by eliminating step by step all integers which are multiple of $p_1$, $B$ will have at most $\frac{(p_1-1)}{p_1}B$ elements, then eliminate from this new set all integers which are multiple of $p_2$, then $B$ will have at most $\frac{(p_2-1)}{p_2}\frac{(p_1-1)}{p_1}B$ elements It is not true, because in your esimate you exlude some numbers twice.

What i wrote is only a sketch of proof and i think it works since between the remaining numbers after such step this is the closer percentage from $B$ (it's about distribution of all rests modulo $p_i p_j$ which are not multiple of $p_j$ - how many of them are not multiple of $p_i$). Do you think that the only proof for this fact it comes from the Euler product and Riemann-Zeta for $s=1$ ?

heartwork wrote: Do you think that the only proof for this fact it comes from the Euler product and Riemann-Zeta for s=1 ? Actually, it is not that difficult. Just not mention Euler product and Riemann-Zeta

I'll post the solution that Gabriel (silver medal in IMO2004) and me got to the original CWMO problem. It's a nice (and short!!) solution. Well, it's fairly easy to prove that $\phi(n) + d(n) \leq n+1$ by a counting argument: $\phi(n)$ is the number of positive integers less than $n$ and coprime with $n$. Let $A$ be the set of such numbers. On the other hand, $d(n)$ is the number of positive divisors of $n$. Let $B$ be the set of such numbers. It's easy to see that $A \cap B = \{1\}$, so since $A$ and $B$ are subsets of $[n] = \{1,2,\dots,n\}$, $n\geq |A\cup B| = |A| + |B| - |A\cap B| = \phi(n) + d(n) - 1$ and the result follows. So $c \leq 1$. If $c = 1$, by the previous counting argument, every number less or equal to $n$ must be a divisor of $n$ or a number coprime with $n$, which is "kinda hard to happen". OK, not so hard: if $n$ is a prime, $\phi(n)=n-1$ and $d(n) = 2$, so all primes $n$ are solutions if $c=1$. Let's find the other solutions in this case. Suppose $n$ is not prime and let $p$ be the smaller prime divisor of $n$. Since $\gcd(n,n-p)=p\neq 1$, $n-p$ divides $n$ and thus $n-p$ divides $p$. Hence $n-p \leq p \iff n\leq 2p$. But $n\geq p^2$, so $p=2$ and $n\leq 4$. $n=4$ is the only other solution. If $c=0$, let $p$ be as before and consider $n-p$ and $n-2p$. If $n-p$ divides $n$ the problem reduces to the former case. So $n-p$ is not a divisor of $n$ nor coprime to $n$ and it must be the only one. Thus $n-2p$ divides $n$ and consequently $2p$ as well. Hence $n-2p \leq 2p \iff n \leq 4p$ and since $n \geq p^2$, $p \leq 3$ and $n \leq 12$. Testing, we get the other solutions: $6$, $8$, $9$ and $12$. Well, I didn't think of a lower bound yet (I didn't read all the other messages) but I know that the average number of divisors of $n$ is close to $\log n$. More precisely: let $\overline{d}(n)$ be the average of the number of divisors of all numbers less or equal to $n$, that is, \[\overline{d}(n) = \frac{1}{n}\sum_{1\leq k\leq n}d(k)\] Thus $|\overline{d}(n) - \log n|\leq 1$. To manage to prove this, count in two ways the number of pairs $(x,y)\in Z^2$ such that $1\leq x, y\leq n$ and $x$ divides $y$. Or look it in "Proofs from The Book". Oh, $\log n = \log_e n$, by the way. You can replace it by $H(n) = \sum_{1\leq k\leq n}\frac{1}{k}$ (OK, the Euler-Mascheroni constant is missing, but it is indeed a good estimate).

No comments

Actually, what I did is so lengthy and not so rigorous, that I will write it. But here is the sketch. We exploit this fact $p^{k-1}>k+1$,for all $p>=5,k>=2$, then we just have to check the following cases to search where $n-d(n)-\varphi(n)$ is actually non negative. 1)$n$ is a product of primes 2) $n$ is a a prime power (also includes one and primes here) Then with a good deal of intuitional bounding and a bit heavy casework, we get that only these choices of $n$ give a non-negative $c$ They are just $n=1,p,4,8,6$ and all in all $c$ can be just $0,1$ and $n$ is already found,just assign them to their respective values of $c$. My non-rigorous solution can be made rigorous but it will be extremely long. To make it rigorous,I would have to replace my intuitional bounding with some analytic Number theory as used in the above solutions. An example of the 'intuitional bounding' that I was referring to is as follows, When I had to verify that $pqr....t-(p-1)(q-1).....(r-)$ is greater than $$2^{no. of primes-1}$$for primes $p,q,r,...t$ and also # of primes>2, I actually took $2,3,5$ to verify it and then used an 'intuitional bounding'to see that this value should now only increase.This seems true obviously but I dont want to prove,since it seems tedious and maybe uses analytic Number theory ,which I am not aware of . But I think I solved the problem, with only such obvious looking bounds to be proved.