JUnit: EgyptianFractionTest.java

As explained on the Wikipedia page "Egyptian fraction", ancient Egyptians had a curious way to represent arbitrary positive integer fractions a/b by breaking them down into sums of distinct unit fractions of the form 1/n. Such breakdown could even be done in inYinitely many different ways for any rational number, depending on what additional obligations we wish to impose on this breakdown. However, the number of unit fractions needed to express a number as a sum of unit fractions tends to grow exponentially with respect to its absolute value. Even though the following construction algorithms would work for arbitrarily large rational numbers, we will only consider those fractions a/b < 1 that satisfy a < b to allow the JUnit test methods to terminate within a reasonable time and without running out of memory.

This lab has you implement two different algorithms to construct the Egyptian fraction breakdown. To ensure correct results even when they involve thousands of digits, you must do all your integer arithmetic using the BigInteger type from java.math. You probably should also add the Fraction example class into your labs project and use its operations to perform the arithmetic of rational numbers needed here. Instead of reinventing that rusty old wheel all by yourself, you get to have more time to not merely walk but also do your arithmetic like an ancient Egyptian!

Create a new class called EgyptianFractions into your labs project, and there a method

public static List greedy(Fraction f)

that constructs the Egyptian fraction breakdown of the fraction f = a/b with the greedy algorithm originally proven to always terminate by Mr. Fibonacci himself! The simplest situation is when a = 1, so the result is 1/b. Otherwise, compute the smallest positive integer n whose reciprocal 1/n is less than the fraction a/b. This can be done by dividing b by a using the truncating integer division, and then add one to the result of that division. Add the term 1/n to the result, and extend the result with the greedy breakdown of the remaining fraction a/b - 1/n that is hopefully simpler.

To ensure unique results for the fuzz testing, this method should return the Egyptian fraction as a list of denominators of these terms in sorted ascending order each term of course represented as a BigInteger in our problem. For example, when called with the fraction 2/3, this method would return the list [2, 6], and with the fraction 4/17, return [5, 29, 1233, 3039345]. As you can see there, restricting the breakdown to use only distinct unit fractions can cause quite a blowup in terms for even some seemingly simple fractions. As is typical with greedy algorithms, the result is not necessarily the simplest or the most balanced possible subdivision into unit fractions, since the last term can be a pretty thin sliver compared to the greedily chosen "thicc" terms that precede it.

The next method introduces another algorithm to construct an Egyptian fraction that usually produces a rather different result than the previous greedy method. Same as Fibonacci's greedy method, the following technique is not guaranteed to return the simplest or the most balanced

breakdown. (It sure seems like some general pattern that underlies our visible fabric of reality is slowly emerging from its slumber!) Write the method

public static List splitting(Fraction a)

that maintains some Set to keep track which terms have already been chosen to be part of the Egyptian fraction. Initially this set is empty. To break down a fraction a/b, we Yirst split into in two terms (a-1)/b + 1/b. Repeating this step allows us to "carve" unit fractions off the bulk of the remaining fraction one at the time, as if carving delicious slices off the Christmas ham! Slice off one unit fraction 1/b by adding b to your chosen set of terms, and construct the Egyptian fraction representation for the remaining fraction (a-1)/b until the entire number has been carved out so that only a zero remains. Often, a-1 and b have common factors to further simplify this task.

Comparing the breakdowns for some randomly chosen simple fractions, the greedy algorithm seems to typically produce fewer terms, but not always. For example, 5/91 breaks down greedily into unit fractions [19, 433, 249553, 93414800161, 17452649778145716451681],

whereas splitting produces a far more balanced subdivision [23, 91, 2093] for the same quantity. As so often in all walks of life, we have ample time to regret in leisure our greedy initial choices as they slowly take us towards their inevitable ends. On the entire way down there we can only dream of what could have been, had we initially stayed our hand and not shot that bloody albatross, but followed the dove and taken the road less traveled instead. (Making your choices inside a computer program instead of directly in the physical reality does not affect the poetic justice of the tragic consequences of such choices. As above, so below.)

To maintain the discipline of using each denominator at most once, we need to somehow handle the situation where the new slice 1/b is already in the set of chosen terms. To do this in an orderly fashion, maintain a local variable List buffer that contains the denominators of the unit fractions that are waiting to get into the set of chosen terms. Start by initializing this buffer to contain exactly one value b, the term that is currently waiting to enter the club. While this buffer is non-empty, pop out any one of the items there, let's call it n. (In the Yirst round of popping, the value n must therefore be equal to b, but can and will equal other values during the later rounds of this corrective dance.)

If n is not already a member of the set of chosen terms, add it there. Otherwise you have a conYlict of two equal terms 1/n trying to become a member of the set of chosen terms, even though only at most one of them can actually be part of the Yinal set of chosen terms. Resolution of this conYlict depends on the parity of n:

• If n is even, remove n from the set of chosen terms, and add n/2 in the buffer.
• If n is odd, add terms n+1 and n(n+1) into the buffer.

For example, two equal unit fractions 1/10 and 1/10 can be replaced by a single 1/5 without affecting the total. If the conYlict is between two equal unit fractions 1/5 and 1/5 that unfortunately cannot be combined into 1/2.5, leave one 1/5 in the set of chosen terms as is, and replace the other term by pushing two new terms 1/6 and 1/30 into the buffer, the total again unaffected by this since 1/5 = 1/6 + 1/30. Rinse and repeat until all terms are distinct and the buffer is empty. Until

then, the individual terms will enter, exit and re-enter the set of chosen terms and the waiting room of the buffer, the exact details of this back-and-forth depending on the terms waiting inside the buffer and the needs of the rest of the number (a-1)/b that is still waiting to be broken down.

We often like to think of integers being composed of prime factors multiplied together. For natural numbers, this prime factorization is unique, the result modestly known as the "Fundamental theorem of arithmetic" although this famous result is actually quite not as trivial as it might initially seem, and certainly is not true just because of some hand waving in the likes of "But, like, it's the primes, so how could it even be otherwise, maaaan, so much confusion here sweaty that I can't even!" As we just saw, a whole another way to think of not just integers but all rational numbers is to see them as Yinite sums of tactically chosen subsets of unit fractions. However, unlike the unique prime factors that make up each integer, any rational number (and thus all integers) can be broken down an inYinite number of different representations as sums of distinct unit fractions.

These Egyptian fractions boggle the mind as a way to express any one of the inYinitely many positive rational numbers in an inYinite number of ways of adding up smaller positive rationals. Kinda makes us wonder if those ancient Egyptians really were connected to something that we have forgotten... but up here in the present timeline of cyberpunk future so bright that we need to wear shades, anybody interested to learn more about this topic can start on the page "Egyptian Fractions" by that David Eppstein guy again. ("Once is happenstance, twice is coincidence...") Most of the external links emanating from the page are as dead as the ancient Egyptian culture that they echoed, but at least "Algorithms for Egyptian Fractions" fortunately is still alive at the time of this writing. (On the page "ConYlict resolution methods", Eppstein calls the algorithm "pairing" that we call "splitting", and the algorithm called "splitting" on that page is then something else altogether.)

TEST CODE:

import org.junit.Test; import java.io.UnsupportedEncodingException; import java.math.BigInteger; import java.util.List; import java.util.Random; import java.util.zip.CRC32; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertTrue; public class EgyptianFractionsTest { private static boolean addsUp(List egyptian, Fraction f) { Fraction sum = new Fraction(BigInteger.ZERO); for(BigInteger n: egyptian) { sum = sum.add(new Fraction(BigInteger.ONE, n)); } return sum.equals(f); } @Test public void testGreedy() { /* Explicit test cases */ assertEquals("[4, 28]", EgyptianFractions.greedy(new Fraction(2, 7)).toString()); assertEquals("[2, 3, 10, 240]", EgyptianFractions.greedy(new Fraction(15, 16)).toString()); assertEquals("[2, 3, 14, 231]", EgyptianFractions.greedy(new Fraction(10, 11)).toString()); assertEquals("[2, 3, 21, 714]", EgyptianFractions.greedy(new Fraction(30, 34)).toString()); assertEquals("[3, 263, 138075]", EgyptianFractions.greedy(new Fraction(59, 175)).toString()); assertEquals("[3, 8, 264]", EgyptianFractions.greedy(new Fraction(61, 132)).toString()); assertEquals("[2, 3, 13, 168, 46350, 3222437400]", EgyptianFractions.greedy(new Fraction(175, 191)).toString()); assertEquals("[4, 23, 1564]", EgyptianFractions.greedy(new Fraction(5, 17)).toString()); assertEquals("[2, 25, 674, 964663, 1861148442475]", EgyptianFractions.greedy(new Fraction(124, 229)).toString()); assertEquals("[2, 13, 199, 52603, 4150560811, 34454310087467394631]", EgyptianFractions.greedy(new Fraction(71, 122)).toString()); /* Pseudorandom fuzz tester */ CRC32 check = new CRC32(); Random rng = new Random(444); for(int i = 0; i < 400; i++) { int a, b; do { b = rng.nextInt(10 * i + 1) + 6; a = rng.nextInt(b - 1) + 1; } while(a % 2 == 0 && b % 2 == 0); Fraction apb = new Fraction(a, b); List gRes = EgyptianFractions.greedy(apb); try { check.update(gRes.toString().getBytes("UTF-8")); } catch(UnsupportedEncodingException ignored) {} assertTrue(addsUp(gRes, apb)); } assertEquals(93321355L, check.getValue()); } @Test public void testSplitting() { /* Explicit test cases */ assertEquals("[2, 4, 8, 16]", EgyptianFractions.splitting(new Fraction(15, 16)).toString()); assertEquals("[2, 7, 14]", EgyptianFractions.splitting(new Fraction(20, 28)).toString()); assertEquals("[7, 8, 56]", EgyptianFractions.splitting(new Fraction(2, 7)).toString()); assertEquals("[3, 9, 10, 27, 90]", EgyptianFractions.splitting(new Fraction(16, 27)).toString()); assertEquals("[3, 11, 33, 132]", EgyptianFractions.splitting(new Fraction(61, 132)).toString()); assertEquals("[9, 10, 17, 90, 153, 154, 23562]", EgyptianFractions.splitting(new Fraction(5, 17)).toString()); assertEquals("[5, 15]", EgyptianFractions.splitting(new Fraction(4, 15)).toString()); assertEquals("[11, 21, 22, 41, 42, 231, 431, 462, 492, 861, 862, 1722, 371091, 742182]", EgyptianFractions.splitting(new Fraction(121, 492)).toString()); assertEquals("[6, 11, 12, 66, 132]", EgyptianFractions.splitting(new Fraction(132, 363)).toString()); assertEquals("[13, 14, 65, 66, 182, 4290]", EgyptianFractions.splitting(new Fraction(12, 65)).toString()); assertEquals("[9, 10, 17, 90, 153, 154, 23562]", EgyptianFractions.splitting(new Fraction(5, 17)).toString()); assertEquals("[3, 4, 12, 27, 28, 756]", EgyptianFractions.splitting(new Fraction(20, 27)).toString()); /* Pseudorandom fuzz tester */ CRC32 check = new CRC32(); Random rng = new Random(444); for(int i = 0; i < 400; i++) { int a, b; do { b = rng.nextInt(10 * i + 1) + 6; a = rng.nextInt(b - 1) + 1; } while(a % 2 == 0 && b % 2 == 0); Fraction apb = new Fraction(a, b); List gRes = EgyptianFractions.splitting(apb); try { check.update(gRes.toString().getBytes("UTF-8")); } catch(UnsupportedEncodingException ignored) {} assertTrue(addsUp(gRes, apb)); } assertEquals(2886553470L, check.getValue()); } }