Project Euler – Problem 69

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

 

The highlighted are the next maximum values of n/φ(n), as n approaches 10^7.
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));
	}
}