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

Results 1 to 12 of 12

- Sep 4th 2006, 11:16 AM #1

- Joined
- Sep 2006
- Posts
- 83

- Sep 4th 2006, 12:02 PM #2

- Joined
- Nov 2005
- From
- someplace
- Posts
- 14,972
- Thanks
- 5

- Sep 4th 2006, 12:03 PM #3

- Joined
- Nov 2005
- From
- New York City
- Posts
- 10,616
- Thanks
- 10

- Sep 4th 2006, 12:08 PM #4

- Joined
- Nov 2005
- From
- someplace
- Posts
- 14,972
- Thanks
- 5

- Sep 4th 2006, 03:54 PM #5

- Joined
- Nov 2005
- From
- New York City
- Posts
- 10,616
- Thanks
- 10

- Sep 4th 2006, 07:59 PM #6

- Joined
- Sep 2006
- Posts
- 83

- Sep 4th 2006, 08:44 PM #7

- Joined
- Nov 2005
- From
- someplace
- Posts
- 14,972
- Thanks
- 5

- Sep 5th 2006, 04:26 AM #8

- Joined
- Nov 2005
- From
- someplace
- Posts
- 14,972
- Thanks
- 5

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 AM #9

- Joined
- Nov 2005
- From
- New York City
- Posts
- 10,616
- Thanks
- 10

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 AM #10

- Joined
- Sep 2006
- Posts
- 83

- Sep 5th 2006, 06:24 AM #11

- Joined
- Nov 2005
- From
- someplace
- Posts
- 14,972
- Thanks
- 5

- Sep 5th 2006, 07:48 AM #12

- Joined
- Nov 2005
- From
- New York City
- Posts
- 10,616
- Thanks
- 10