Results 1 to 12 of 12

Math Help - phi(n) = phi (n+1) = phi (n+2)

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    83

    Question phi(n) = phi (n+1) = phi (n+2)

    I got stuck in solving this question. Can you help me?

    Find a positive integer n such that phi(n) = phi (n+1) = phi (n+2).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by beta12
    I got stuck in solving this question. Can you help me?

    Find a positive integer n such that phi(n) = phi (n+1) = phi (n+2).
    Is this a home work problem? What had you been covering in class
    just before this was set?

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    I do not think you can solve this problem simply.
    I assume it should be solved by a table.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker
    I do not think you can solve this problem simply.
    I assume it should be solved by a table.
    A solution can be found using the google technique

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Supprisingly this number is the my password
    5186
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2006
    Posts
    83

    Thumbs up phi (5186)

    Hi perfect hacker,

    phi ( 5186) is just fited into my problem. How do you come up with this answer. Could you please teach me? Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker
    Supprisingly this number is the my password
    5186
    But you will have to change it now

    RonL
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by beta12
    Hi perfect hacker,

    phi ( 5186) is just fited into my problem. How do you come up with this answer. Could you please teach me? Thank you very much.
    Two ways:

    1. Google for Euler Totient function and look through the hits.

    2. Write some code to conduct a search:


    Define the EulerTotient function
    Code:
     
    function EulerTotient(m)
    ##
    ##  Euler Totient function using the formula from
    ##  Hardy and Wright 5th Ed, p53.
    ##
    ##  CB 2006
    ##
     
      ff=factor1(m);..find prime factors and multiplicities
     
      ff=ff(:,1);  ..extract the distinct prime factors
     
      ll=length(ff);
     
      prd=m;
     
    ..this next bit is for the benefit of causual readers
    ..the vectorised method is prd=prd*prod(1-1/ff');
     
      for idx=1 to ll  
        prd=prd*(1-1/ff(idx));
      end ..for
     
      rv=round(prd,0);
     
      return rv
    endfunction
    Then a console session to do the search:

    Code:
    >
    >.. load the EulerTotient definition
    >
    >load "D:\user\temp\EulerTotient.e";
    >
    >.. test it
    >
    >EulerTotient(7^2)
               42 
    >
    >.. set up a search between lo and hi
    >
    >function search(lo,hi)
    $  rv=[];
    $  lst=EulerTotient(lo);
    $  for idx=lo+1 to hi
    $    nxt=EulerTotient(idx);
    $    if nxt==lst
    $       nxtnxt=EulerTotient(idx+1);
    $       if nxtnxt==nxt
    $          rv=rv|idx-1;
    $       endif
    $    endif
    $    lst=nxt;
    $  end ..for
    $
    $  return rv
    $endfunction
    >
    >.. run the search and time it
    >
    >t=time;search(10,10000),time-t
             5186 
            6.031 
    >
    Total time to hack the code ~30m, and to run it 6s.

    RonL
    Last edited by CaptainBlack; June 15th 2007 at 01:32 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    3.Look up in your Number Theory textbook and this problem appears. It does not ask to solve it, rather it asks to confirm it wokrs for this number.

    I do not think there is a simple way to solve this problem. I have tried to find a neccesarilly and sufficient condition for, \phi(n)=\phi(n+1).
    If, n=p_1^{a_1}...p_s^{a_s} then,
    n+1=q_1^{b_1}...q_r^{b_r}.
    With, p_i\not =q_j since, \gcd (n,n+1)=1.
    Thus, you have,
    p_1^{a_1}...p_s^{a_s}q_1...q_r(p_1-1)...(p_s-1)= q_1^{b_1}...q_r^{b_r}p_1...p_s(q_1-1)...(q_s-1)
    You can cancel the q's and p's but that brings you nowhere.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Sep 2006
    Posts
    83

    thks

    I see.
    thks Perfect Hacker and Captain Black.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker
    3.Look up in your Number Theory textbook and this problem appears. It does not ask to solve it, rather it asks to confirm it wokrs for this number.

    I do not think there is a simple way to solve this problem. I have tried to find a neccesarilly and sufficient condition for, \phi(n)=\phi(n+1).
    If, n=p_1^{a_1}...p_s^{a_s} then,
    n+1=q_1^{b_1}...q_r^{b_r}.
    With, p_i\not =q_j since, \gcd (n,n+1)=1.
    Thus, you have,
    p_1^{a_1}...p_s^{a_s}q_1...q_r(p_1-1)...(p_s-1)= q_1^{b_1}...q_r^{b_r}p_1...p_s(q_1-1)...(q_s-1)
    You can cancel the q's and p's but that brings you nowhere.
    There is evidence on the MathWorld page for the totient function that
    the general solution of this problem is an open question.

    RonL
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by CaptainBlack
    There is evidence on the MathWorld page for the totient function that
    the general solution of this problem is an open question.

    RonL
    The major problem is that we do not know the relatively primeness between p_i-1 and q_k.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum