**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 there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d [≤] 12,000?

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 there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d [≤] 12,000?

**Solution:**

4179871

**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 23

* By Nayuki Minase

*

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

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

*/

public final class p023 implements EulerSolution {

public static void main(String[] args) {

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

}

private static final int LIMIT = 28123;

private boolean[] isAbundant = new boolean[LIMIT + 1];

public String run() {

// Compute look-up table

for (int i = 1; i < isAbundant.length; i++)

isAbundant[i] = isAbundant(i);

int sum = 0;

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

if (!isSumOf2Abundants(i))

sum += i;

}

return Integer.toString(sum);

}

private boolean isSumOf2Abundants(int n) {

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

if (isAbundant[i] && isAbundant[n - i])

return true;

}

return false;

}

private static boolean isAbundant(int n) {

if (n < 1)

throw new IllegalArgumentException();

int sum = 1; // Sum of factors less than n

int end = Library.sqrt(n);

for (int i = 2; i <= end; i++) {

if (n % i == 0)

sum += i + n / i;

}

if (end * end == n)

sum -= end;

return sum > n;

}

}

## No comments :

## Post a Comment