# Thread: Euler Totient Function

1. ## Euler Totient Function

This thread got me thinking...

Define $\displaystyle \varphi_0(n)=n,\; \varphi_1(n)=\varphi(n),\; \varphi_2(n)=\varphi(\varphi(n))$ and so on...

Now Define $\displaystyle I(n)$ to be the smallest integer such that $\displaystyle \varphi_{I(n)}(n)=1$.

I've found some bounds of $\displaystyle I(n)$: it's easy to see $\displaystyle I(n)\leq n-1$ and a delicate strong induction shows $\displaystyle I(n)\leq\varphi(n)$.

My question is, what the formula for $\displaystyle I(n)$, or at least what are some tighter bounds?

-Thanks!

2. Originally Posted by chiph588@
This thread got me thinking...

Define $\displaystyle \varphi_0(n)=n,\; \varphi_1(n)=\varphi(n),\; \varphi_2(n)=\varphi(\varphi(n))$ and so on...

Now Define $\displaystyle I(n)$ to be the smallest integer such that $\displaystyle \varphi_{I(n)}(n)=1$.

I've found some bounds of $\displaystyle I(n)$: it's easy to see $\displaystyle I(n)\leq n-1$ and a delicate strong induction shows $\displaystyle I(n)\leq\varphi(n)$.

My question is, what the formula for $\displaystyle I(n)$, or at least what are some tighter bounds?

-Thanks!
Found some interesting references.

[thread at another forum] Iteration of Euler's phi function

[pdf] On the Sum of Iterations of the Euler Function

Possibly something could be done with the inequalities in this Wikipedia article.

3. Originally Posted by chiph588@
This thread got me thinking...

Define $\displaystyle \varphi_0(n)=n,\; \varphi_1(n)=\varphi(n),\; \varphi_2(n)=\varphi(\varphi(n))$ and so on...

Now Define $\displaystyle I(n)$ to be the smallest integer such that $\displaystyle \varphi_{I(n)}(n)=1$.

I've found some bounds of $\displaystyle I(n)$: it's easy to see $\displaystyle I(n)\leq n-1$ and a delicate strong induction shows $\displaystyle I(n)\leq\varphi(n)$.

My question is, what the formula for $\displaystyle I(n)$, or at least what are some tighter bounds?

-Thanks!
Well I can put a logarithmic bound on it easily.

Let $\displaystyle u_0 = N$, and $\displaystyle u_{n + 1} = \varphi{(u_n)}$

If $\displaystyle u_n$ is odd, then $\displaystyle u_{n + 1}$ will be even.

If $\displaystyle u_n$ is even, then $\displaystyle u_{n + 1}$ will lose at least a factor of $\displaystyle 2$ due to Euler's totient, thus $\displaystyle u_{n + 1} \leqslant \frac{u_n}{2}$.

Thus, regardless of $\displaystyle u_n$, $\displaystyle u_{n + 2} \leqslant \frac{u_n}{2}$.

Then $\displaystyle u_n = 1 \implies n \leqslant \log_{\sqrt{2}}{(N)}$.

Thus $\displaystyle I(N) \leqslant \log_{\sqrt{2}}{(N)}$. I hope this is right

But I haven't found anything stronger.

4. Originally Posted by Bacterius
Thus, regardless of $\displaystyle u_n$, $\displaystyle u_{n + 2} \leqslant \frac{u_n}{2}$.

Then $\displaystyle u_n = 1 \implies n \leqslant \log_{\sqrt{2}}{(N)}$.

Thus $\displaystyle I(N) \leqslant \log_{\sqrt{2}}{(N)}$. I hope this is right

But I haven't found anything stronger.
We get $\displaystyle u_n\leq \frac{N}{2^{n/2}}$

So if $\displaystyle 1=u_n=\frac{N}{2^{n/2}}\implies 2^{n/2}=N\implies n=2\log_2(N)$

Thus we get $\displaystyle n\leq2\log_2(N)$ (roughly speaking... throw in a floor/ceiling in there)

I'll now have to do some research to see whether this is a better bound than $\displaystyle \phi(n)$.

5. Originally Posted by chiph588@
I'll now have to do some research to see whether this is a better bound than $\displaystyle \phi(n)$.
For $\displaystyle n\geq6,\;\phi(n)\geq\sqrt{n}$ so your bound is better.

6. Originally Posted by chiph588@
For $\displaystyle n\geq6,\;\phi(n)\geq\sqrt{n}$ so your bound is better.
Yay ! Finally I succeed in something
There should be a way to improve the bound, but I don't yet see how to do it without involving probabilities ?

7. Originally Posted by Bacterius
Yay ! Finally I succeed in something
There should be a way to improve the bound, but I don't yet see how to do it without involving probabilities ?
Well undefined has led me to believe no one knows much about this problem. I'd say the easiest thing next would be to find a lower bound.

8. A lower bound, ... I'll have to be thinking about it, it's quite interesting. And any bounds found will be highly valuable to my final project (I'm going to use the result proved in my thread into a bigger algorithm).

First I have to see if there are any lower bounds existing yet. It could be a starting point.

9. Originally Posted by Bacterius
A lower bound, ... I'll have to be thinking about it, it's quite interesting. And any bounds found will be highly valuable to my final project (I'm going to use the result proved in my thread into a bigger algorithm).

First I have to see if there are any lower bounds existing yet. It could be a starting point.
If you're using these bounds for a project, let's be a little more rigorous with the last bound we found.

It should be $\displaystyle I(n)\leq 2\log_2(N)+1$ or if you'd like we could just say $\displaystyle I(n)=O(\log(n))$.

What is the project you're working on?

10. Originally Posted by chiph588@
If you're using these bounds for a project, let's be a little more rigorous with the last bound we found.

It should be $\displaystyle I(n)\leq 2\log_2(N)+1$ or if you'd like we could just say $\displaystyle I(n)=O(\log(n))$.

What is the project you're working on?
I'm building up an improvement to Pollard's p-1 integer factorization algorithm. The project is going to use the general theorem proved in my thread, the bounds on the iteration of the totient function, and a variant of a quick modular exponentiation method. It should work.