27
$\begingroup$

Let $\phi(n)$ be the Euler totient function: $$ \phi(2)=1 \;,\; \phi(11)=10 \;,\; \phi(12)=4\;,$$ etc. Define $\Phi(n)$ to be the number of iterations $k$ so that $\phi^k(n)$ reaches $1$. For example, $\Phi(25)=5$ because $\phi(25)=20$ and continuing, it takes $5$ applications to reach $1$: $$25,20,8,4,2,1 \;.$$ Another example: $\Phi(113)=7$: $$113,112,48,16,8,4,2,1 \;.$$ Here is a plot of $\Phi(n)$:


          Phi_n100
          Red curve: $0.43 + 1.22 \ln( n )$.
$\Phi(n)$ is fit quite well (and well beyond what's shown above) by $c \ln(n)$.

Two questions:

Q1. What explains the logarithmic growth, at a high-level?

Q2. What explains the constant $c \approx 1.22$?

Likely both of these questions are answered in the literature.

$\endgroup$
  • 4
    $\begingroup$ See whether this helps you: oeis.org/A003434 $\endgroup$ – Rohan Dec 4 '17 at 11:58
  • $\begingroup$ @Rohan: Thanks! Here's one fact from that OEIS entry: "Pillai proved that log(n/2)/log(3) + 1 <= a(n) <= log(n)/log(2) + 1," where a(n) is what I call $\Phi(n)$. $\endgroup$ – Joseph O'Rourke Dec 4 '17 at 12:09
  • 3
    $\begingroup$ (@stefan4024: I would prefer the title not use LaTeX so it can be cited elsewhere.) $\endgroup$ – Joseph O'Rourke Dec 4 '17 at 12:13
  • 3
    $\begingroup$ For the fun of it: Iterated phi sequence, a coding challenge to output $\Phi(n)$ from $n=2$ to $n=100$. $\endgroup$ – Simply Beautiful Art Dec 4 '17 at 15:53
  • 2
    $\begingroup$ I don't think unicode phi symbol is better than "iterated phi(n) function". But n in the title is awkward. I think the best (most citable / searchable) is "iterated Euler totient function" or "Iterated phi function" or "Iterated Euler's phi function" $\endgroup$ – 6005 Dec 4 '17 at 19:10
17
$\begingroup$

Note that $\phi(n)$ is even (for $n\ge3$), and if $n$ is even then $\phi(n)\le n/2$. This immediately gives you Pillai's logarithmic upper bound.

$\endgroup$
  • $\begingroup$ This is quite insightful, and certainly makes the $\alpha \log n$ conjecture that @lhf found plausible. $\endgroup$ – Joseph O'Rourke Dec 5 '17 at 0:38
10
$\begingroup$

Erdős et al. say this in On the Normal Behavior of the Iterates Of some Arithmetic Functions:

[...] it is easy to see that the set of numbers of the form $k(n)/ \log n$ is dense in $[1/ \log 3,1/ \log 2]$. What is still in doubt about $k(n)$ is its average and normal behavior. We conjecture that there is some constant $\alpha$ such that $k(n) \sim \alpha \log n$ on a set of asymptotic density $1$.

Here, $k(n)$ is what the OP calls $\Phi(n)$.

The original paper was published in 1990. Perhaps it is still the state of the art.

$\endgroup$
  • $\begingroup$ The other authors of that paper are still around and active. Maybe one of them would know whether there has been any progress. $\endgroup$ – Gerry Myerson Dec 5 '17 at 2:58
1
$\begingroup$

I would like to show Pillai's lower bound. Here we use $ \varphi^*(n) $ to denote $ \Phi(n) $ because of the famous log-star function ($ \log^* $) in complexity.

To get started, we need a special variety of Euler's totient function $ \hat\varphi $, which is $\varphi$ without considering 2, namely $ \hat \varphi(x):=\begin{cases}\varphi(x), x\text{ odd}\\ 2\cdot\varphi(x), x\text{ even}\end{cases} $.

When $ k $ goes sufficiently large(actually it is just $ \varphi^*(x) $), it is easy to see that $ \varphi^k $ approaches $1$ and $ \hat\varphi^k $ approaches some power of $ 2$. Let's denote it as $2^{\sigma(x)} \le2^k=2^{\varphi^*(x)} $. The inequility is obvious. Then we make a claim.

Claim. For all odd number $ x $, there holds $ x\le 3^{\sigma(x)} $. The equality holds iff $ x $ is some power of $3$.

Proof of the claim. Obviously $ \sigma(2)=\sigma(3)=1, \sigma(3^k)=k $. And it is also easy to check that $ \sigma(pq)=\sigma(p)+\sigma(q) $. So we just need to deal with the prime numbers. By induction, we consider the prime $ p>3 $. We have known that $ p-1\le 3^{\sigma(p-1)}=:t $, and the equality never holds, so $ p-1<t $. Since $ \sigma(p-1)=\sigma(p) $ for prime $p$, and notice that $ p\neq 3^{\sigma(p)}=t $, from $ p-1<t,p\neq t $, we get $ p<t $.

Eventually the final step.

When $x $ is odd, $ \varphi^*(x)\ge\sigma(x)+1\ge\log_3n+1 $.

When $ x $ is even, we write $ x=2^d\cdot c, d\ge1, c\text{ odd} $, then $ \varphi^*(x)\ge \sigma(x)=d+\sigma(c)\ge d+\log_3c\ge1+ \log_3{x\over2}$. Easy to check the equality holds iff $ x =2\cdot3^k $ for some $ k $.

Here the proof ends.

The proof comes from a proof sketch by Deng Mingyang(moorhsum), the IMO 2019 gold medal winner from China, posted on Zhihu(Chinese), a chinese version of Quora. I prove the claim here which the sketch not contains. I am curious about why to construct such $ \hat\varphi $ and make such a claim.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.