Problem 69: Find the value of n < 1,000,000 for which n/φ(n) is a maximum.
Note the following:
n | φ(n) | n/φ(n) |
2 | 1 | 2 |
… | … | … |
5 | 4 | 1.25 |
6 | 2 | 3 |
7 | 6 | 1.167 |
… | … | … |
30 | 8 | 3.75 |
… | … | … |
210 | 48 | 4.375 |
… | … | … |
2310 | 480 | 4.8125 |
… | … | … |
One can note from this are the divisors that make up n:
ie 2 = 2; 6 = 2×3; 30 = 2x3x5; 210 = 2x3x5x7.. etc
It then becomes trivial to deduce the maximum n/φ(n) where 1<n<10^7
class runner
{
public static double findTotient(int nO){
int n = nO;
boolean[] result = new boolean[n];
int i=2;
do{
if(n % i == 0){
n /= i;
result[i] = true;
}else{
do{
i++;
}while(i 1);
double calc = nO;
for(int k=0; k b2){ b2 = calc; b1=n;}
//System.out.println(n+" "+calc);
}
}
System.out.println(b1+" "+b2);
System.out.println("time: "+(System.currentTimeMillis() - time));
}
}