1
$\begingroup$

(I have asked this question on stackoverflow and received a suggestion to try posting here 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 (If helps for anyone):

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;
}
$\endgroup$
  • $\begingroup$ So your question is: what is the longest sequence of unique unit fractions $ \ge \frac{1}{1000}$ whose sum equals $1$? $\endgroup$ – Jens Mar 29 at 1:12
  • $\begingroup$ A lower bound would be the reciprocals of the proper positive divisors of $496$, giving $9$ terms. $\endgroup$ – Jens Mar 29 at 1:19
  • $\begingroup$ @Jens yes that is correct between 1/2 - 1/1000 and pair the fractions in such a way to create the longest sequence. $\endgroup$ – MKUltra Mar 29 at 1:27
  • $\begingroup$ How do you know pairings would create the longest sequence? Also, what is the longest sequence you found? $\endgroup$ – Jens Mar 29 at 1:30
  • $\begingroup$ @Jens I would know the pairings create the longest sequence by running code and build a tree from 1/2 + 1/3 + 1/6 my longest sequence is 304 $\endgroup$ – MKUltra Mar 29 at 1:36

Your Answer

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

Browse other questions tagged or ask your own question.