# Euler Totient Function

• Jun 3rd 2010, 03:01 PM
chiph588@
Euler Totient Function

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

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

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

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

-Thanks!
• Jun 3rd 2010, 03:51 PM
undefined
Quote:

Originally Posted by chiph588@

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

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

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

My question is, what the formula for $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.
• Jun 3rd 2010, 04:05 PM
Bacterius
Quote:

Originally Posted by chiph588@

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

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

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

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

-Thanks!

Well I can put a logarithmic bound on it easily.

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

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

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

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

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

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

But I haven't found anything stronger.
• Jun 3rd 2010, 04:33 PM
chiph588@
Quote:

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

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

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

But I haven't found anything stronger.

We get $u_n\leq \frac{N}{2^{n/2}}$

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

Thus we get $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 $\phi(n)$.
• Jun 3rd 2010, 04:37 PM
chiph588@
Quote:

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

For $n\geq6,\;\phi(n)\geq\sqrt{n}$ so your bound is better.
• Jun 3rd 2010, 04:44 PM
Bacterius
Quote:

Originally Posted by chiph588@
For $n\geq6,\;\phi(n)\geq\sqrt{n}$ so your bound is better.

Yay ! Finally I succeed in something (Cool)
There should be a way to improve the bound, but I don't yet see how to do it without involving probabilities ?
• Jun 3rd 2010, 04:47 PM
chiph588@
Quote:

Originally Posted by Bacterius
Yay ! Finally I succeed in something (Cool)
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.
• Jun 3rd 2010, 04:54 PM
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.
• Jun 3rd 2010, 05:30 PM
chiph588@
Quote:

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 $I(n)\leq 2\log_2(N)+1$ or if you'd like we could just say $I(n)=O(\log(n))$.

What is the project you're working on?
• Jun 3rd 2010, 05:38 PM
Bacterius
Quote:

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 $I(n)\leq 2\log_2(N)+1$ or if you'd like we could just say $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.