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

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

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

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

Supprisingly this number is the my password
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.

Originally Posted by ThePerfectHacker

Supprisingly this number is the my password
5186

But you will have to change it now

RonL

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

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, .
If, then,
.
With, since, .
Thus, you have,

You can cancel the q's and p's but that brings you nowhere.

I see.
thks Perfect Hacker and Captain Black.

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, .
If, then,
.
With, since, .
Thus, you have,

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

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