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

Printable View

- Sep 4th 2006, 11:16 AMbeta12phi(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). - Sep 4th 2006, 12:02 PMCaptainBlackQuote:

Originally Posted by**beta12**

just before this was set?

RonL - Sep 4th 2006, 12:03 PMThePerfectHacker
I do not think you can solve this problem simply.

I assume it should be solved by a table. - Sep 4th 2006, 12:08 PMCaptainBlackQuote:

Originally Posted by**ThePerfectHacker**

RonL - Sep 4th 2006, 03:54 PMThePerfectHacker
Supprisingly this number is the my password :eek:

5186 - Sep 4th 2006, 07:59 PMbeta12phi (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. - Sep 4th 2006, 08:44 PMCaptainBlackQuote:

Originally Posted by**ThePerfectHacker**

RonL - Sep 5th 2006, 04:26 AMCaptainBlackQuote:

Originally Posted by**beta12**

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

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

>

RonL - Sep 5th 2006, 05:42 AMThePerfectHacker
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, $\displaystyle \phi(n)=\phi(n+1)$.

If, $\displaystyle n=p_1^{a_1}...p_s^{a_s}$ then,

$\displaystyle n+1=q_1^{b_1}...q_r^{b_r}$.

With, $\displaystyle p_i\not =q_j$ since, $\displaystyle \gcd (n,n+1)=1$.

Thus, you have,

$\displaystyle p_1^{a_1}...p_s^{a_s}q_1...q_r(p_1-1)...(p_s-1)=$$\displaystyle 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. - Sep 5th 2006, 05:51 AMbeta12thks
I see.

thks Perfect Hacker and Captain Black. - Sep 5th 2006, 06:24 AMCaptainBlackQuote:

Originally Posted by**ThePerfectHacker**

the general solution of this problem is an open question.

RonL - Sep 5th 2006, 07:48 AMThePerfectHackerQuote:

Originally Posted by**CaptainBlack**