# Thread: phi(n) = phi (n+1) = phi (n+2)

1. ## 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).

2. 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

3. I do not think you can solve this problem simply.
I assume it should be solved by a table.

4. 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

5. Supprisingly this number is the my password
5186

6. ## 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.

7. Originally Posted by ThePerfectHacker
Supprisingly this number is the my password
5186
But you will have to change it now

RonL

8. 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:
>
>
>
>.. 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

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.

10. ## thks

I see.
thks Perfect Hacker and Captain Black.

11. 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

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