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