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<primeSieve.length && primeSieve[i]);
			}
		}while(n > 1);
 
		double calc = nO;
		for(int k=0; k<result.length; k++){
			if(!result[k]) continue;
			calc *= (1 - 1.0/k);
		}
		return calc;
	}
	public static boolean[] primeSieve(int limit){
		boolean[] arr = new boolean[limit];
		arr[0] = true; arr[1] = true;
 
		for(int i=2; i<limit;i++){
			if(arr[i]){ continue; }
			int j=i+i;
			while(j<arr.length){
				arr[j] = true;
				j+=i;
			}
		}
		return arr;
	}
 
	static boolean[] primeSieve;
	public static void main (String[] args) throws java.lang.Exception
	{
		long time = System.currentTimeMillis();
 
		int limit = 2311;
		primeSieve = primeSieve(limit);
 
		double b1=0,b2=0;
		for(int n=2;n<limit;n++){
			if(!primeSieve[n]){
				//System.out.println(n+ " "+(n-1));
			}else{				
				double calc = findTotient(n);
				calc = n/calc;
				if(calc > b2){ b2 = calc; b1=n;}
			//System.out.println(n+" "+calc);
			}
		}
		System.out.println(b1+" "+b2);
		System.out.println("time: "+(System.currentTimeMillis() - time));
	}
}