Sunday 2 November 2014

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;
      }
}


No comments:

Post a Comment