Problem Statement
For any $n$ let $F(n)$ be the largest $k$ such that any of the $k!$ possible ordering patterns appears in some sequence of $\phi(m+1),\ldots,\phi(m+k)$ with $m+k\leq n$. Is it true that\[F(n)=(c+o(1))\log\log\log n\]for some constant $c$? Is the first pattern which fails to appear always\[\phi(m+1)>\phi(m+2)>\cdots \phi(m+k)?\]Is it true that 'natural' ordering which mimics what happens to $\phi(1),\ldots,\phi(k)$ is the most likely to appear?
Categories:
Number Theory
Progress
Erdős [Er36b] proved that\[F(n)\asymp \log\log\log n,\]and similarly if we replace $\phi$ with $\sigma$ or $\tau$ or $\nu$ or any 'decent' additive or multiplicative function.Weisenberg has observed that the same questions could be asked for ordering patterns which allow equality (indeed, the final problem only makes sense if we allow equality).
Source: erdosproblems.com/415 | Last verified: January 15, 2026