**Problem:**

Consider the fraction, n/d, where n and d are positive integers. If n[<]d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d [≤] 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d [≤] 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

If we list the set of reduced proper fractions for d [≤] 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d [≤] 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

**Solution:**

31626

**Code:**

The solution may include methods that will be found here: Library.java .

The solution may include methods that will be found here: Library.java .

public interface EulerSolution{

public String run();

}

/*

* Solution to Project Euler problem 21

* By Nayuki Minase

*

* http://nayuki.eigenstate.org/page/project-euler-solutions

* https://github.com/nayuki/Project-Euler-solutions

*/

public final class p021 implements EulerSolution {

public static void main(String[] args) {

System.out.println(new p021().run());

}

public String run() {

int sum = 0;

for (int i = 1; i < 10000; i++) {

if (isAmicable(i))

sum += i;

}

return Integer.toString(sum);

}

private static boolean isAmicable(int n) {

int m = divisorSum(n);

return m != n && divisorSum(m) == n;

}

private static int divisorSum(int n) {

int sum = 0;

for (int i = 1; i < n; i++) {

if (n % i == 0)

sum += i;

}

return sum;

}

}

## No comments :

## Post a Comment