2

I have been given a problem where fractions between 1/2 - 1/1000 have to be added to create the longest sequence of all unique unit fractions.

The rules on constructing these fractions:

Let create a set: D , D is only to hold unique unit fractions , sub-fractions can add up to the same fraction for example:

          1/10             
        /      \
1/110 + 1/11    1/35 + 1/14

All sub-fractions can be held within the set as long as they themselves are not the same fractions once we are adding them together it is ok for them to total up to the same root.

The goal:

The fractions have to be added in a way to sum up to exactly 1. Any sub-fractions are not allowed to be over 1000 it is explicitly between 2 and 1000 hence the fractions which make up 1/1000 would not be applicable ( 1/1004 + 1/251000 ).

What currently I found to be the most effective:

Find the two lowest multiples which make-up the current fraction that I am looking at so for e.g 1/6 = A = 3 , B = 2. And now we complete the following equation: C = (A+B)*A , D = (A+B)*B. Now C & D are the sub-fractions which add up to my initial fraction

              1/6
           /       \
        1/15       1/10

In code:

public static int[] provideFactorsSmallest(int n) {
    int k[] = new int[2];

    for(int i = 2; i <= n - 1; i++) { 
        if(n % i == 0) {
            k[0] = i;
            break;
        }
    }

    for(int i = k[0] + 1; i <= n - 1 && k[0] != 0; i++) {
        //System.out.println("I HAVE BEEN ENTERED");
        if(k[0] * i == n) {
            k[1] = i;
            int firstTerm =  k[0];
            int secondTerm = k[1];
            k[0] = (firstTerm + secondTerm) * firstTerm;
            k[1] = (firstTerm + secondTerm) * secondTerm;
            return k;
        }
    }
    return null;
}

My question:

What would be the most effective way to pair and group the numbers to achieve possible longest fraction sequence?

Thank you in advance!

4
  • 1
    If the code works, then maybe this question would fit code review
    – Lino
    Mar 28, 2019 at 13:08
  • I had been thinking a bit about your first question (without posting anything), but you’ve come further than I ever got. It seems to me that you are on the right track. I don’t have any ideas for improvement.
    – Anonymous
    Mar 28, 2019 at 15:30
  • Possible duplicate of Longest unique unit fractions that add up to 1
    – CryptoFool
    Mar 28, 2019 at 16:57
  • Guess it not easy?
    – user11238130
    Apr 1, 2019 at 23:48

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.