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

• September 4th 2006, 11:16 AM
beta12
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).
• September 4th 2006, 12:02 PM
CaptainBlack
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
• September 4th 2006, 12:03 PM
ThePerfectHacker
I do not think you can solve this problem simply.
I assume it should be solved by a table.
• September 4th 2006, 12:08 PM
CaptainBlack
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 :D

RonL
• September 4th 2006, 03:54 PM
ThePerfectHacker
Supprisingly this number is the my password :eek:
5186
• September 4th 2006, 07:59 PM
beta12
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.
• September 4th 2006, 08:44 PM
CaptainBlack
Quote:

Originally Posted by ThePerfectHacker
Supprisingly this number is the my password :eek:
5186

But you will have to change it now :D

RonL
• September 5th 2006, 04:26 AM
CaptainBlack
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
• September 5th 2006, 05:42 AM
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.
• September 5th 2006, 05:51 AM
beta12
thks
I see.
thks Perfect Hacker and Captain Black.
• September 5th 2006, 06:24 AM
CaptainBlack
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
• September 5th 2006, 07:48 AM
ThePerfectHacker
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$.