PROJECT EULER SOLUTION # 69

PROBLEM 69

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

n	Relatively Prime	φ(n)	n/φ(n)
2	1	1	2
3	1,2	2	1.5
4	1,3	2	2
5	1,2,3,4	4	1.25
6	1,5	2	3
7	1,2,3,4,5,6	6	1.1666...
8	1,3,5,7	4	2
9	1,2,4,5,7,8	6	1.5
10	1,3,7,9	4	2.5

It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

SOLUTION 69

Pe69.java

package pe69c;

/*

 * third attempt for the correct answer

 * The Execution time got down to around 15 seconds

 */

import java.util.LinkedList;

public class pe69

{

      public static void main(String args[])

      {

            int num=1000000;

            long start=System.currentTimeMillis();

            long numerator,denominator;

            Fraction maxFraction=new Fraction(1,1);

            int maxi=0;

            LinkedList lst[]=new LinkedList[num+1];

            for(int i=0;i<lst.length;i++)

                  lst[i]=new LinkedList<String>();

            System.out.println("started");

            boolean primes[]=new boolean[num+1];

            for(int i=2;i<=num;i++)

                  if(!primes[i])

                        for(int j=i;j<=num;j+=i)

                        {

                              primes[j]=true;

                              lst[j].add(i+"");

                        }

            System.out.println("completed");

            System.out.println("Execution time = "+((System.currentTimeMillis()-start)/1000.0));

           

            for(int i=1;i<=num;i++)

            {

                  numerator=1;

                  denominator=1;

                  for(int j=0;j<lst[i].size();j++)

                  {

                        int temp=Integer.parseInt(lst[i].get(j)+"");

                        numerator*=temp;

                        denominator*=(temp-1); 

                  }

                 

                  Fraction f=new Fraction(numerator,denominator);

                  if(Fraction.compare(f,maxFraction)==1)

                  {

                        maxi=i;

                        maxFraction=f;

                  }

            }

            System.out.println("Answer = "+maxi);

            System.out.println("Execution time = "+((System.currentTimeMillis()-start)/1000.0));

      }

}

Fraction.java

package pe69c;

public class Fraction

{

      public long n,d;

      public Fraction(long n,long d)

      {

            this.n=n;

            this.d=d;

            simplifyFraction();

      }

     

      public void simplifyFraction()

      {

            long h=hcf(Math.abs(n),Math.abs(d));

            n/=h;

            d/=h;

            if(d<0 && n<0)

            {

                  d=-d;

                  n=-n;

            }

      }

     

      public static long hcf(long a,long b)

      {

            if(b==0)

                  return a;

            return hcf(b,a%b);

      }

     

      public static long lcm(long a,long b)

      {

            return (a*b)/hcf(a,b);

      }

     

      public boolean equals(Fraction f)

      {

            if((this.n==f.n && f.n==0) || (this.n==f.n && this.d==f.d))

                  return true;

            return false;

      }

     

      public static int compare(Fraction a,Fraction b)

      {

            long l=lcm(a.d,b.d);

           

            if((l/a.d * a.n) > (l/b.d * b.n))

                  return 1;

            else if((l/a.d * a.n) == (l/b.d * b.n))

                  return 0;

            else

                  return -1;

      }

      public String toString()

      {

            return this.n+"/"+this.d;

      }

}