Results 1 to 10 of 10

Math Help - Euler Totient Function

  1. #1
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163

    Euler Totient Function

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by chiph588@ View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by chiph588@ View Post
    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.
    Last edited by Bacterius; June 3rd 2010 at 05:20 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bacterius View Post
    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) .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by chiph588@ View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by chiph588@ View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bacterius View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bacterius View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by chiph588@ View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's Totient Function
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: July 12th 2010, 10:41 AM
  2. Euler totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 10:33 AM
  3. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 12th 2009, 07:11 PM
  4. Euler's Totient Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2009, 08:16 PM
  5. Euler totient function
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 25th 2007, 08:10 AM

Search Tags


/mathhelpforum @mathhelpforum