2
\$\begingroup\$

(I was suggested to post here from stack overflow so hey guys!)

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?

\$\endgroup\$
1
\$\begingroup\$
  1. In first for loop we can stop when i*i>=n. As we need two different divisors, smallest must be less than Math.sqrt(n)
  2. Second for loop looks like simple integer division.

Whole code is equivalent to this:

    private static int[] provideFactorsSmallest_v(int n) {
        for (int firstTerm = 2; firstTerm*firstTerm < n; firstTerm++) {
            if (n % firstTerm == 0) {
                int secondTerm = n / firstTerm;
                return new int[]{
                        (firstTerm + secondTerm) * firstTerm,
                        (firstTerm + secondTerm) * secondTerm
                };
            }
        }
        return null;
    }


\$\endgroup\$
  • \$\begingroup\$ wow that return new int[] that got me spiced up! \$\endgroup\$ – MKUltra Mar 28 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.