Euler Totient Function

**chiph588@** · June 3rd 2010, 03:01 PM

This thread got me thinking...

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!

**undefined** · June 3rd 2010, 03:51 PM

Originally Posted by chiph588@

This thread got me thinking...

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.

**Bacterius** · June 3rd 2010, 04:05 PM

Originally Posted by chiph588@

This thread got me thinking...

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

But I haven't found anything stronger.

**chiph588@** · June 3rd 2010, 04:33 PM

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

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)$ .

**chiph588@** · June 3rd 2010, 04:37 PM

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.

**Bacterius** · June 3rd 2010, 04:44 PM

Originally Posted by chiph588@

For $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 ?

**chiph588@** · June 3rd 2010, 04:47 PM

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.

**Bacterius** · June 3rd 2010, 04:54 PM

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.

**chiph588@** · June 3rd 2010, 05:30 PM

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?

**Bacterius** · June 3rd 2010, 05:38 PM

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.

Thread: Euler Totient Function

LinkBack

Thread Tools

Display

Euler Totient Function

Similar Math Help Forum Discussions

Euler's Totient Function

Euler totient function

Euler's totient function

Euler's Totient Function

Euler totient function

Search Tags