For all $n$ there exists $x$ such that $\varphi(x)<\varphi(x+1)<\ldots<\varphi(x+n)$ Let $\varphi$ be the Euler's function, i.e. $\varphi(n)$ stands for the number of integers $m \in \{1,\ldots,n\}$ such that $\text{gcd}(m,n)=1$.
Let $n\ge 2$ be a positive integer. Show that there exists infinitely many $x$ for which
$$
\varphi(x)<\varphi(x+1)<\ldots<\varphi(x+n).
$$
[It is a generalization of a math contest asking the same question for $n=2$; I know the answer, and it is positive]
 A: In the following $p$ will always denote a prime numer. $p_k$ will be the $k$-th prime.
Clearly it suffices to show that, given $0\le x_i<y_i\le\alpha$ ($i=0,\dots,n$), we can always find $x$ s.t. $\phi(x+i)\in(x_i,y_i)$ for any $i$.
Here $\alpha:=\prod_{p\le n+1}\frac{p-1}{p}$.
We first prove this crucial lemma, which in particular gives the thesis for $n=0$:
Lemma. Given $0\le x<y\le 1$ and any $z\in\mathbb{N}$, there exists a set $A$ of primes $>z$ s.t. $m:=\prod_{p\in A}p$ satisfies $x<\frac{\phi(m)}{m}<y$. 
We remember that $\frac{\phi(m)}{m}=\prod_{p\in A}\frac{p-1}{p}$. 
Proof. Pick any prime $p_k>z$ s.t. $\frac{p_k-1}{p_k}>x$. Since $\prod_p\frac{p-1}{p}=0$ (which follows from the well-known divergence of $\sum_p\frac{1}{p}$) there exists a maximal $\ell\ge k$ s.t. $\prod_{j=k}^\ell\frac{p_j-1}{p_j}>x$. Put all the primes $p_k,\dots,p_\ell$ in the set $A$
and look for another $k'>\ell$ s.t. $\left(\prod_{j=k}^\ell\frac{p_j-1}{p_j}\right)\frac{p_{k'}-1}{p_{k'}}>x$ and again
there is a maximal $\ell'\ge k'$ for which
$$\left(\prod_{j=k}^\ell\frac{p_j-1}{p_j}\right)\left(\prod_{j=k'}^{\ell'}\frac{p_j-1}{p_j}\right)>x$$
holds. Add $p_{k'},\dots,p_{\ell'}$ to $A$ and iterate this procedure. After a finite number of steps we will obtain the desired $A$ since
$\frac{p-1}{p}\to 1$ as $p\to\infty$ (so if a positive real number $t$ is such that $t>x$ and $t\frac{p-1}{p}\le x$, for some large $p$,
we will have $t<y$). $\blacksquare$
Set $q:=\prod_{p\le n+1}q$. Applying the lemma $n+1$ times, we find disjoint sets $A_0,\dots,A_n$ of primes $>n+1$ such that, calling $s_i:=\prod_{p\in A_i}p$,
we have $x_i\frac{(q,i)}{\phi((q,i))}<\frac{\phi(s_i)}{s_i}<y_i\frac{(q,i)}{\phi((q,i))}$. Here $(q,i)=\text{gcd}(q,i)$.
This can be done since $\frac{(q,i)}{\phi((q,i))}\le\frac{1}{\alpha}$, while $x_i,y_i\le \alpha$. The reason for this choice of the intervals will be apparent in a moment.
Now let $M$ be very large and call $B$ the set of primes $p_j>n+1$ with $j\le M$ which do not belong to any $A_i$, i.e.
$$B:=\{p_j\mid j\le M\}\setminus\left(\{1,\dots,n+1\}\cup\bigcup_{i=0}^n A_i\right),$$
and set $b:=\prod_{p\in B}p$.
The Chinese Remainder Theorem allows us to solve this system of congruences:
$$\begin{cases}x\equiv 0\pmod{qs_0} \\ x+i\equiv 0\pmod{s_i}\ \forall i=1,\dots,n \\ x-1\equiv 0\pmod{b}\end{cases}$$
We claim that, for $M$ big enough, the smallest positive solution $x$ of this system is the one we are looking for.
In fact, if $p\mid x+i$ (for any $i=0,\dots,n$), then there are three cases:


*

*$p\le n+1$

*$p\in A_i$ 

*$p=p_j$ for some $j>M$. 
There are no other possibilities (otherwise $p\in A_{i'}$ for some $i'\neq i$ or $p\in B$; so $p\mid x+i'$ or $p\mid x-1$ but none of these is possible,
as $p$ would then divide a number $\le n+1$).
Notice that for the first two cases the suitable converse holds, i.e. every prime in $A_i$ divides $x+i$, while every prime $p\le n+1$ divides $x+i$ iff $p\mid i$, thanks to the fact that $p\mid q\mid x$.
Thus $$\frac{\phi(x+i)}{x+i}=\prod_{p\mid (q,i)}\frac{p-1}{p}\prod_{p\in A_i}\frac{p-1}{p}\prod_{p_j\mid x+i,\ j>M}\frac{p_j-1}{p_j}$$
and $\prod_{p\mid (q,i)}\frac{p-1}{p}=\frac{\phi((q,i))}{(q,i)}$, so by the estimates satisfied by $s_i$ we get
$$\prod_{p\mid (q,i)}\frac{p-1}{p}\prod_{p\in A_i}\frac{p-1}{p}=\frac{\phi((q,i))}{(q,i)}s_i\in(x_i,y_i).$$
To conclude we just have to show that the last product tends to $1$ as $M\to \infty$. But by minimality $x<\prod_{j=1}^M p_j$, so
(for $M$ large) $x+i<\prod_{j=1}^{M+1} p_j$, thus $x+i$ has at most $M$ distinct prime factors.
So
$$1\ge \prod_{p_j\mid x+i,\ j>M}\frac{p_j-1}{p_j}=\prod_{p_j\mid x+i,\ j>M}\left(1-\frac{1}{p_j}\right)\ge\left(1-\frac{1}{p_M}\right)^M$$
and hence
$$\liminf_{M\to\infty}\left(1-\frac{1}{p_M}\right)^M\ge\liminf_{M\to\infty}\left(1-\frac{1}{aM}\right)^M=e^{-\frac{1}{a}}$$
for any $a>0$, where we used the very loose estimate $p_M\ge aM$ (for $M$ big enough depending on $a$). Sending $a\to\infty$ we get
$\liminf_{M\to\infty}\left(1-\frac{1}{p_M}\right)^M\ge 1$, which gives $\lim_{M\to\infty}\prod_{p_j\mid x+i,\ j>M}\frac{p_j-1}{p_j}=1$ (note that $x$ depends on $M$!).
This also shows the result mentioned by Erick Wong in the comments.
A: Partial answer: We impose suitable divisibility conditions by performing the following algorithm:


*

*Assign $a_k\leftarrow\frac{\phi(k)}{k}$ for $1\le k\le n+1$. Let $N\leftarrow n+1$. Let $S\leftarrow(n+1)\mathbb N$

*If $a_1<a_2<\ldots <a_n$, terminate.

*Let $i$ be maximal with $a_i\ge a_{i+1}$.

*Let $p$ be the smallest prime $>N$. 

*Let $a_i\leftarrow a_i\cdot\left(1-\frac1p\right)$, $S\leftarrow S\cap\left(p\mathbb Z-i\right)$, $N\leftarrow p$ and go back to step 2.


The algorithm is guaranteed to terminate because $\prod\left(1-\frac1p\right)$ diverges to $0$.
Once it terminates, we have the following situation:
For $1\le i\le n$ and $p$ prime $\le N$, either $p\mid s+i$ for all $s\in S$ or $p\nmid s+i$ for all $s\in S$. In fact we obtain 
$$ \frac{\phi(s+i)}{s+i}=a_i\prod_{p|s+i\atop p>N}\left(1-\frac1p\right)$$
for all $s\in S$ (this condition holds whenever we enter step 2).
This allows us to conclude $\phi(s+1)<\phi(s+2)<\ldots<\phi(s+n+1)$ provided that $\prod_{p|s+i\atop p>N}\left(1-\frac1p\right)$ is always sufficiently close to $1$.
The question is: Can we achieve this?
