Working with Fractions in Java

by Michael Gilleland

Introduction

In his book Mathematics for the Nonmathematician (NY: Dover, 1985), pp. 64-65, Morris Kline points out:

The disappointing feature of the decimal representation of fractions is that some simple fractions cannot be represented as fractions with a finite number of digits. Thus when we seek to express 1/3 as a decimal, we find that neither 0.3, nor 0.33, nor 0.333, and so on, suffices. All one can say in this and similar cases is that by carrying more and more decimal digits, one comes closer and closer to the fraction, but no finite number of digits will ever be the exact answer. This fact is expressed by the notation 1/3 = 0.333..., where the dots indicate that we must keep on adding threes to approach the fraction 1/3 more and more closely.

double f = 1.0/7.0;
double sum = 0.0;
for (int i = 0; i < 7; i++) {
  sum += f;
}
System.out.println (sum);

0.9999999999999998

Close, but no cigar. Although the workarounds to such problems are as well-known as the problems themselves, it often pays to dispense with the decimal representation of fractions altogether, and instead deal with fractions simply as fractions. Doug Lea of the State University of New York at Oswego has written a very useful Java class, Fraction.java, which allows us to do just that. The source code for Fraction.java is available here and is part of package EDU.oswego.cs.dl.util.concurrent.misc -- if I ruled the universe, it would be part of core package java.math.

Let's rewrite the code fragment shown above with its equivalent using Fraction.java:

Fraction f = new Fraction (1, 7);
Fraction sum = new Fraction (0, 1);
for (int i = 0; i < 7; i++) {
  sum = sum.plus (f);
}
System.out.println (sum);

1

This paper shows how easy it is, with the help of Fraction.java, to explore some interesting highways and byways of fractions, such as Egyptian fractions, Farey sequences, and continued fractions.

In some cases, we need fractions with very large numerators and denominators, and so this paper also contains a modification of Fraction.java, called BigFraction.java. With BigFraction.java as a tool, we also explore harmonic numbers, test numbers for primality using Wolstenholme's Theorem, and implement an unusual algorithm (Fractran) which can be used to generate prime numbers.

The mathematics in this paper can all be understood, with a little patience, by anyone who grasps the simple concepts of fractions as learned in elementary school.

All source code in this paper is free for you to use as you wish, with no restrictions and no guarantees.

Egyptian Fractions

The ancient Egyptians represented fractions such as 3/5 as a sum of distinct unit fractions, that is, fractions whose numerators are one, e.g. 1/2 and 1/10. The sum 1/5 + 1/5 + 1/5 would be unacceptable, because the unit fractions (while adding up to 3/5) are not distinct.

Egyptian fractions have been the subject of much research by mathematicians, who have devised a number of clever algorithms to find Egyptian fractions for a given proper fraction. One of the easiest to understand is the so-called greedy algorithm, which works like this:

1. Start with an empty list, set denominator = 2 and remainder = fraction we're trying to decompose.
2. Create a candidate unit fraction = 1/denominator.
3. Increment denominator.
4. If candidate > remainder, go to step 2.
5. Add candidate to list.
6. Subtract candidate from remainder. Result is new remainder.
7. If remainder is 0, go to step 10.
8. If remainder is a unit fraction, add it to the list and go to step 10.
9. Go to to step 2.
10. Hurrah, we're done! List contains Egyptian fractions adding up to original fraction.

Let's "play computer" and follow these steps in an attempt to decompose 3/7 into Egyptian fractions.

The following Java class, EgyptianFractions.java, computes Egyptian fractions for a specified fraction between zero and one using the greedy algorithm discussed above.

//------------------------------------------------
// Egyptian fractions have a numerator of 1.
// Any fraction can be decomposed into a series of
// unique Egyptian fractions.
//------------------------------------------------

import java.util.Vector;
import EDU.oswego.cs.dl.util.concurrent.misc.Fraction; 

public abstract class EgyptianFractions {

  //----------
  // Constants
  //----------

  private static Fraction ZERO = new Fraction (0, 1);
  private static Fraction ONE = new Fraction (1, 1);

  //---------------------------------------
  // Get sum of Vector of Fraction objects.
  // Used to check accuracy of algorithm.
  //---------------------------------------

  public static Fraction getSum (Vector v) {
    Fraction sum = new Fraction (ZERO);
    for (int i = 0; i < v.size (); i++) {
      sum = sum.plus ((Fraction) v.elementAt (i));
    }
    return sum;
  }

  //---------------------------------
  // Decompose using greedy algorithm
  //---------------------------------

  public static Vector greedyAlgorithm (Fraction f) {

    // Make sure we're starting out with a
    // fraction between 0 and 1, exclusive

    if (f.compareTo (ZERO) <= 0) {
      throw new IllegalArgumentException (f.toString ());
    }
    if (f.compareTo (ONE) >= 0) {
      throw new IllegalArgumentException (f.toString ());
    }

    Fraction remainder = new Fraction (f); // remainder
    long denominator = 2; // first candidate will be 1/2
    Vector v = new Vector (); // list of successful candidates
    boolean done = false; // completion flag

    while (!done) {

      // Get the next candidate

      Fraction candidate = new Fraction (1, denominator);

      // If the candidate is less than the current remainder,
      // add it to the "successful" list and subtract it from the remainder

      if (candidate.compareTo (remainder) <= 0) {
        v.addElement (candidate);
        remainder = remainder.minus (candidate);
      }

      // If the remainder is 0, we're done.

      if (remainder.equals (ZERO)) {
        done = true;
      }
      else {

        // If the remainder's numerator is 1, add it to
        // the list and we're done.

        if (remainder.numerator () == 1) {
          v.addElement (remainder);
          done = true;
        }
        else {

          // Increment the denominator for the next candidate

          denominator++;
        }
      }
    }

    return v;

  }

  //-----
  // Test
  //-----

  public static void main (String[] args) {
    Fraction f = new Fraction (3, 7);
    Vector v = EgyptianFractions.greedyAlgorithm (f);
    System.out.println (v.toString ());
    System.out.println (EgyptianFractions.getSum (v).toString ());
  }

}

Here are some useful links on Egyptian fractions. Those by Ron Knott and Jim Loy are the easiest to understand.

• David Eppstein, Egyptian Fractions
• Kevin Gong, Egyptian Fractions
• Ron Knott, Egyptian Fractions
• Jim Loy, Egyptian Fractions
• Eric Weisstein, Egyptian Fractions

• The Akhmin Papyrus
• Irrationality of Quadratic Sums
• Minimizing the Denominators of Unit Fraction Expansions
• Odd, Greedy, and Stubborn (Unit Fractions)
• On a Unit Fraction Question of Erdos and Graham
• Reverse Greed for Unit Fractions
• The Rhind Papyrus 2/n Table
• Unit Fractions and Fibonacci
• Unit Fraction Partitions
• Wagon Trains and Sticky Wickets
• Why Unit Fractions?

Farey Sequences

Suppose you were asked for a list of all fractions between 0 and 1 inclusive, whose denominator does not exceed a given number n.

• When n is 1, the list contains just 0 and 1, that is, 0/1 and 1/1.
• When n is 2, the list contains 0/1, 1/2, 1/1.
• When n is 3, the list contains 0/1, 1/3, 1/2, 2/3, 1/1.
• When n is 4, the list contains 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1. Note that we have excluded 2/4, as being equivalent to 1/2.

[0/1,                                                        1/1]
[0/1,                          1/2,                          1/1]
[0/1,                1/3,      1/2,      2/3,                1/1]
[0/1,           1/4, 1/3,      1/2,      2/3, 3/4,           1/1]
[0/1,      1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5,      1/1]
[0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1]

For every sequence of order >= 2, the fraction 1/2 stands in the middle. Any two terms equidistant from 1/2 are complementary, that is to say, they add up to 1. Looking at the Farey sequence of order 6, we see that

• 2/5 and 3/5 are both one away from 1/2. Their sum is 1.
• 1/3 and 2/3 are both two away from 1/2. Their sum is 1.
• 1/4 and 3/4 are both three away from 1/2. Their sum is 1.
• 1/5 and 4/5 are both four away from 1/2. Their sum is 1.
• 1/6 and 5/6 are both five away from 1/2. Their sum is 1.
• 0/1 and 1/1 are both six away from 1/2. Their sum is 1.

Another curious property is this. Choose any two adjacent terms, say 1/3 and 2/5 in the Farey sequence of order 6. Their difference is equal to the reciprocal of the product of their denominators. For example, the difference between 1/3 and 2/5 is 1/15. The product of the denominators of 1/3 and 2/5 is 15, whose reciprocal is also 1/15.

The following Java class, FareySequence.java, generates Farey sequences.

//-------------------------
// Farey sequence generator
//-------------------------

import java.util.Vector;
import EDU.oswego.cs.dl.util.concurrent.misc.Fraction; 

public class FareySequence {

  private Vector seq;
  private long order;

  //------
  // Reset
  //------

  public void reset () {
    seq = null;
    order = 0;
  }

  //--------------------------------------------
  // The mediant of a/b and c/d is (a+c) / (b+d)
  //--------------------------------------------

  public static Fraction getMediant (Fraction f1, Fraction f2) {
    return new Fraction (f1.numerator () + f2.numerator (),
                         f1.denominator () + f2.denominator ());
  }

  public static boolean isMediant (Fraction candidate, Fraction f1, Fraction f2) {
    return (candidate.numerator () == f1.numerator () + f2.numerator ()) &&
           (candidate.denominator () == f1.denominator () + f2.denominator ());
  }

  //------------------
  // Get next sequence
  //------------------

  public Vector getNext () {

    if (order == 0) {
      seq = new Vector ();
      seq.addElement (new Fraction (0, 1));
      seq.addElement (new Fraction (1, 1));
      order = 1;
    }
    else {
      order++;
      Vector v = new Vector ();
      for (int i = 0; i < seq.size (); i++) {
        Fraction f1 = (Fraction) seq.elementAt (i);
        v.addElement (f1);
        if (i < seq.size () - 1) {
          Fraction f2 = (Fraction) seq.elementAt (i + 1);
          if ((f1.denominator () + f2.denominator ()) <= order) {
            Fraction child = getMediant (f1, f2);
            v.addElement (child);
          }
        }
      }
      seq = v;
    }
    return seq;

  }

  //--------------------------------------------
  // Get the order of the last sequence computed
  //--------------------------------------------

  public long getOrder () {
    return order;
  }

  //--------------------------------
  // Get sequence of specified order
  //--------------------------------

  public Vector getSequence (long order) {
    if (order <= 0) {
      return null;
    }
    reset ();
    while (this.order <= order ) {
      getNext ();
    }
    return seq;
  }

  //-----
  // Test
  //-----

  public static void main (String[] args) {
    FareySequence fs = new FareySequence ();
    Vector next;
    for (int i = 0; i < 10; i++) {
      next = fs.getNext ();
      System.out.println (next);
    }
    fs.reset ();
    System.out.println (fs.getSequence (9));
  }

}

Here are some useful links on Farey sequences.

• Alexander Bogomolny, Farey Series
• Alexander Bogomolny, Farey Series, a Story
• Alexander Bogomolny, Pick's Theorem Applies to Farey Series
• BCF Group, The Bins of the Farey Sequence
• Matthew R. Watkins, Farey Sequences
• University of Ferrara, Bibliography on Farey Fractions and Ford Circles
• Eric Weisstein, Farey Sequence

Here are also some references from books:

• Albert H. Beiler, Recreations in the Theory of Numbers, 2nd edition (NY: Dover, 1966), pp. 168-172 = "Farey Tails"
• John H. Conway and Richard K. Guy, The Book of Numbers (NY: Copernicus, 1996), pp. 152-154 = "Farey Fractions and Ford Circles"
• Ross Honsberger, Ingenuity in Mathematics (Washington: The Mathematical Association of America, 1970), pp. 24-37 = "The Farey Series"
• Manfred Schroeder, Fractals, Chaos, and Power Laws (NY: W.H. Freeman, 1991), pp. 334-340 = "Mediants, Farey Sequences, and the Farey Tree"

Continued Fractions

A general continued fraction has the form:

           a1                                
b0 + --------------------------------------             
                a2                        
      b1 + --------------------------------             
                        a3                
            b2 + --------------------------             
                        b3 +              
                              . . .       
                                       an 
                                    + -----
                                       bn 

If this looks intimidating, let's consider the slightly less complicated simple continued fraction, which has the form:

           1                                
b0 + --------------------------------------             
                1                        
      b1 + --------------------------------             
                        1                
            b2 + --------------------------             
                        b3 +              
                              . . .       
                                       1 
                                    + -----
                                       bn 

If you compare the general with the simple form, you'll see that we've just replaced all of the "b"s with "1"s. If this still looks intimidating, let's look at a concrete example. Any rational number can be represented as a simple continued fraction, and so we'll try 45/16. Its representation as a simple continued fraction looks like this:

        1                                
2 + ---------------             
             1                        
      1 + ---------             
                 1                
            4 + ---             
                 3              

In order to evaluate this still rather complicated-looking expression, let's start at the bottom and work upwards.

• 4 + 1/3 is 13/3
• 1 / (13/3) is the reciprocal of 13/3, or 3/13.
• 1 + 3/13 is 16/13
• 1 / (16/13) is the reciprocal of 16/13, or 13/16.
• 2 + 13/16 is 45/16, which is what we started with. Eureka!

• [0; 3] is the list form of the continued fractions for 1/3
• [2] is the list form of the continued fractions for 2/1
• [0; 1, 1, 2] is the list form of the continued fractions for 3/5
• [0; 2] is the list form of the continued fractions for 1/2

The following Java class, ContinuedFractions.java, converts to and from simple continued fractions.

//------------------------------------------------
// Converts to and from simple continued fractions
//------------------------------------------------

import java.util.Vector;
import EDU.oswego.cs.dl.util.concurrent.misc.Fraction; 

public abstract class ContinuedFractions {

  //-----------------------------------------------------
  // Given a proper fraction, return its simple continued
  // fraction representation in list form
  //-----------------------------------------------------

  public static Vector to (Fraction f) {
    Vector v = new Vector ();
    if (f.denominator () == 1) {
      v.addElement (new Long (f.numerator ()));
    }
    else if (f.numerator () == 1) {
      v.addElement (new Long (0));
      v.addElement (new Long (f.denominator ()));
    }
    else {
      Fraction x = new Fraction (f);
      long quotient, remainder;
      while (x.denominator () > 1) {
        quotient = x.numerator () / x.denominator ();
        remainder = x.numerator () % x.denominator ();
        v.addElement (new Long (quotient));
        x = new Fraction (x.denominator (), remainder);
        if (x.denominator () == 1) {
          v.addElement (new Long (x.numerator ()));
        }
      }
    }
    return v;
  }

  //-----------------------------------------------
  // Given a continued fraction in list form,
  // return the proper fraction which it represents
  //-----------------------------------------------

  public static Fraction from (Vector v) {
    if (v.size () == 1) {
      return new Fraction (getLong (v, 0), 1);
    }
    Fraction sum = null;
    Fraction f;
    long a;
    for (int i = v.size () - 1; i >= 1; i--) {
      a = getLong (v, i - 1);
      if (sum == null) {
        Fraction f1 = new Fraction (a, 1);
        Fraction f2 = new Fraction (1, getLong (v, i));
        sum = f1.plus (f2);
      }
      else {
        sum = sum.inverse ().plus (a);
      }
    }
    return sum;
  }

  //-----------------------------------------------
  // Utility function to extract long from a Vector
  //-----------------------------------------------

  private static long getLong (Vector v, int idx) {
    Long longObj = (Long) v.elementAt (idx);
    return longObj.longValue ();
  }

  //-----
  // Test
  //-----

  public static void main (String[] args) {
    Fraction fractions[] = {new Fraction (45, 16),
                            new Fraction (1, 3),
                            new Fraction (2, 1),
                            new Fraction (3, 5),
                            new Fraction (8, 16)};
    Vector v;
    Fraction f;
    for (int i = 0; i < fractions.length; i++) {
      f = fractions[i];
      v = ContinuedFractions.to (f);
      System.out.println (v.toString ());
      f = ContinuedFractions.from (v);
      System.out.println (f.toString ());
    }
  }

}

Here are some useful links about continued fractions. The best introductions for amateurs are those by Ron Knott and Adam Van Tuyl.

• John D. Barrow, Chaos in Numberland: The Secret Life of Continued Fractions
• M. Beeler, R.W. Gosper, and R. Schroeppel, Continued Fractions
• Darren C. Collins, Continued Fractions
• Robert M. Corless, Continued Fractions and Chaos
• Edward G. Dunne, Pianos and Continued Fractions
• Mark Herkommer, Continued Fractions
• Ron Knott, An Introduction to Continued Fractions
• Christopher Reed, A Little about Continued Fractions
• Adam Van Tuyl, Continued Fractions...an Introduction
• Eric Weisstein, Continued Fractions

• Albert H. Beiler, Recreations in the Theory of Numbers, 2nd edition (NY: Dover, 1966), pp. 257-267
• John H. Conway and Richard K. Guy, The Book of Numbers (NY: Copernicus, 1996), pp. 176-179
• Richard Courant and Herbert Robbins, What is Mathematics?, revised by Ian Stewart, 2nd edition (Oxford: Oxford University Press, 1996), pp. 49-51, 301-303
• A.A. Klaf, Arithmetic Refresher (NY: Dover, 1964), pp. 98-101
• W.W. Rouse Ball and H.S.M. Coxeter, Mathematical Recreations and Essays, 13th edition (NY: Dover, 1987), pp. 54-56, 86-87

Big Fractions

System.out.println (Long.MAX_VALUE);
System.out.println (Long.MAX_VALUE + 1);
System.out.println (Long.MIN_VALUE);

9223372036854775807
-9223372036854775808
-9223372036854775808

//-------------------------------------------------------
// An adaptation of Doug Lea's Fraction.java with
// BigInteger (instead of long) numerator and denominator
//-------------------------------------------------------

import java.math.BigDecimal;
import java.math.BigInteger;
import java.io.Serializable;

public class BigFraction implements Cloneable, Comparable, Serializable {
  protected final BigInteger numerator_;
  protected final BigInteger denominator_;

  //-----------------
  // Accessor methods
  //-----------------

  public BigInteger numerator () {
    return numerator_;
  }

  public BigInteger denominator () {
    return denominator_;
  }

  //-------------
  // Constructors
  //-------------

  public BigFraction (BigInteger num, BigInteger den) {
    // Reduce to lowest terms
    boolean numNonnegative = gteq (num, BigInteger.ZERO);
    boolean denNonnegative = gteq (den, BigInteger.ZERO);
    BigInteger a = numNonnegative? num : num.negate ();
    BigInteger b = denNonnegative? den : den.negate ();
    BigInteger g = a.gcd (b);
    if (numNonnegative == denNonnegative) {
      numerator_ = a.divide (g);
    }
    else {
      numerator_ = a.negate ().divide (g);
    }
    denominator_ = b.divide (g);
  }

  public BigFraction (BigFraction f) {
    numerator_ = f.numerator();
    denominator_ = f.denominator();
  }

  public BigFraction (String s) {
    this (new BigInteger (s.substring (0, s.indexOf ('/'))),
          new BigInteger (s.substring (s.indexOf ('/') + 1)));
  }

  public BigFraction (long num, long den) {
    this (new BigInteger (Long.toString (num)),
          new BigInteger (Long.toString (den)));
  }

  //------------------
  // Override toString
  //------------------

  public String toString () {
    return numerator ().toString () + "/" +
           denominator ().toString ();
  }

  //--------------------------------
  // Required to implement Cloneable
  //--------------------------------

  public Object clone () {
    return new BigFraction (this);
  }

  //----------------------------
  // Utility comparison routines
  //----------------------------

  private boolean gt (BigInteger x, BigInteger y) {
    return x.compareTo (y) > 0;
  }

  private boolean gteq (BigInteger x, BigInteger y) {
    return x.compareTo (y) >= 0;
  }

  private boolean lt (BigInteger x, BigInteger y) {
    return x.compareTo (y) < 0;
  }

  private boolean lteq (BigInteger x, BigInteger y) {
    return x.compareTo (y) <= 0;
  }

  //------------
  // Get minimum
  //------------

  public BigFraction min (BigFraction val) {
    if (compareTo (val) <= 0) {
      return this;
    }
    else {
      return val;
    }
  }

  //------------
  // Get maximum
  //------------

  public BigFraction max (BigFraction val) {
    if (compareTo (val) > 0) {
      return this;
    }
    else {
      return val;
    }
  }

  //-------------------------------------------------------
  // Convert to BigDecimal
  // Rounding mode is any of BigDecimal.ROUND_xxx constants
  //-------------------------------------------------------

  public BigDecimal asBigDecimal (int scale, int roundingMode) {
    BigDecimal num = new BigDecimal (numerator ());
    BigDecimal den = new BigDecimal (denominator ());
    return num.divide (den, scale, roundingMode);
  }

  //------------------
  // Get negated value
  //------------------

  public BigFraction negate () {
    return new BigFraction (numerator ().negate (), denominator ());
  }

  //---------------------------
  // Get multiplicative inverse
  //---------------------------

  public BigFraction inverse () {
    return new BigFraction (denominator (), numerator ());
  }

  //----
  // Add
  //----

  public BigFraction add (BigFraction b) {
    BigInteger an = numerator ();
    BigInteger ad = denominator ();
    BigInteger bn = b.numerator ();
    BigInteger bd = b.denominator ();
    return new BigFraction (an.multiply (bd).add (bn.multiply (ad)), ad.multiply (bd));
  }

  public BigFraction add (BigInteger n) {
    return add (new BigFraction (n, BigInteger.ONE));
  }

  public BigFraction add (long n) {
    return add (new BigInteger (Long.toString (n)));
  }

  //---------
  // Subtract
  //---------

  public BigFraction subtract (BigFraction b) {
    BigInteger an = numerator();
    BigInteger ad = denominator();
    BigInteger bn = b.numerator();
    BigInteger bd = b.denominator();
    return new BigFraction(an.multiply (bd).subtract (bn.multiply (ad)), ad.multiply (bd));
  }

  public BigFraction subtract (BigInteger n) {
    return subtract (new BigFraction (n, BigInteger.ONE));
  }

  public BigFraction subtract (long n) {
    return subtract (new BigInteger (Long.toString (n)));
  }

  //---------
  // Multiply
  //---------

  public BigFraction multiply (BigFraction b) {
    BigInteger an = numerator();
    BigInteger ad = denominator();
    BigInteger bn = b.numerator();
    BigInteger bd = b.denominator();
    return new BigFraction (an.multiply (bn), ad.multiply (bd));
  }

  public BigFraction multiply (BigInteger n) {
    return multiply (new BigFraction (n, BigInteger.ONE));
  }

  public BigFraction multiply (long n) {
    return multiply (new BigInteger (Long.toString (n)));
  }

  //-------
  // Divide
  //-------

  public BigFraction divide (BigFraction b) {
    BigInteger an = numerator ();
    BigInteger ad = denominator ();
    BigInteger bn = b.numerator ();
    BigInteger bd = b.denominator ();
    return new BigFraction (an.multiply (bd), ad.multiply (bn));
  }

  public BigFraction divide (BigInteger n) {
    return divide (new BigFraction (n, BigInteger.ONE));
  }

  public BigFraction divide (long n) {
    return divide (new BigInteger (Long.toString (n)));
  }

  //---------------------------------
  // Required to implement Comparable
  //---------------------------------

  public int compareTo (Object other) {
    BigFraction b = (BigFraction) (other);
    BigInteger an = numerator ();
    BigInteger ad = denominator ();
    BigInteger bn = b.numerator ();
    BigInteger bd = b.denominator ();
    BigInteger left = an.multiply (bd);
    BigInteger right = bn.multiply (ad);
    if (lt (left, right)) {
      return -1;
    }
    if (left.equals (right)) {
      return 0;
    }
    else {
      return 1;
    }
  }

  public int compareTo (BigInteger n) {
    Object obj = new BigFraction (n, BigInteger.ONE);
    return compareTo (obj);
  }

  //----------------
  // Override equals
  //----------------

  public boolean equals (Object other) {
    return compareTo ((BigFraction) other) == 0;
  }

  public boolean equals (BigInteger n) {
    return compareTo (n) == 0;
  }

  public boolean equals (long n) {
    return equals (new BigInteger (Long.toString (n)));
  }

  //------------------
  // Override hashCode
  //------------------

  public int hashCode() {
    int num = numerator().intValue ();
    int den = denominator ().intValue ();
    return num ^ den;
  }

  //-----
  // Test
  //----- 

  public static void main (String[] args) {
    BigFraction f1, f2, f3;

    // Start out with a big fraction whose numerator is 3 followed by 500 zeros
    // and whose denominator is 6 followed by 500 zeros

    StringBuffer sb = new StringBuffer ("3");
    for (int i = 0; i < 500; i++) {
      sb.append ("0");
    }
    BigInteger bi1 = new BigInteger (sb.toString ());
    sb.setCharAt (0, '6');
    BigInteger bi2 = new BigInteger (sb.toString ());
    f1 = new BigFraction (bi1, bi2);
    System.out.println (f1);

    // Add 2/8 to it

    f2 = new BigFraction (2, 8);
    System.out.println (f2);
    f3 = f1.add (f2);
    System.out.println (f3);

    // Express result as decimal

    System.out.println (f3.asBigDecimal (2, BigDecimal.ROUND_UNNECESSARY));

    // Subtract 16/64 from result

    System.out.println (f3.subtract (new BigFraction ("16/64")));

    // Divide result by result * negative inverse of result (i.e. -1)

    System.out.println (f3.divide (f3.multiply (f3.inverse ().negate ())));

  }
}

Harmonic Numbers

The harmonic series is the series of reciprocals of positive integers, i.e. 1/1 + 1/2 + 1/3 + 1/4 .... A harmonic number is a partial sum of that series. The first harmonic number is 1/1; the second is 1/1 + 1/2, or 3/2; the third is 1/1 + 1/2 + 1/3, or 11/6; etc.

Here is a table of the first 100 harmonic numbers.

Some columns of this table correspond to sequences in Neil Sloane's On-Line Encyclopedia of Integer Sequences:

• The "Numerator" column is sequence A001008
• The "Denominator" column is sequence A002805

Using the BigInteger.java class, it is an easy matter to write a harmonic number generator (HarmonicNumbers.java). In fact, the table just shown was generated automatically with the aid of this class.

import java.util.Vector;
import java.math.BigInteger;

public class HarmonicNumbers {

  private BigFraction term = null;
  private BigFraction sum = null;

  public BigFraction getNext () {
    if (term == null) {
      term = new BigFraction (1, 1);
      sum = new BigFraction (0, 1);
    }
    else {
      BigInteger num = BigInteger.ONE;
      BigInteger denom = term.denominator ().add (BigInteger.ONE);
      term = new BigFraction (num, denom);
    }
    sum = sum.add (term);
    return sum;
  }

  public static void main (String[] args) {
    HarmonicNumbers gen = new HarmonicNumbers ();
    BigFraction next;
    for (int i = 0; i < 20; i++) {
      next = gen.getNext ();
      System.out.println (next.toString ());
    }
  }

}

Here are some useful links about the harmonic series and harmonic numbers. The best introduction for amateurs is the one by John Webb, which explains the relationship between the harmonic series and such phenomena as rainfall records and traffic flow.

• Kevin Brown, Bernoulli Numbers and the Harmonic Series
• Kevin Brown, Recurrences for Harmonic Sums
• Kevin Brown, Zeta Function and Harmonic Series
• Robert M. Dickau, Harmonic Numbers and the Book-Stacking Problem
• Jim Loy, Harmonic Series
• Torsten Sillke, The Harmonic Numbers and Series
• Thinned-Out Harmonic Series
• John Webb, In Perfect Harmony
• Eric Weisstein, Harmonic Number
• Eric Weisstein, Harmonic Series

• John H. Conway and Richard K. Guy, The Book of Numbers (NY: Copernicus, 1996), pp. 258-259
• Martin Gardner, Sixth Book of Mathematical Games from Scientific American (NY: Charles Scribner's Sons, 1975), pp. 165-170
• Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd edition (Boston: Addison-Wesley, 1994), pp. 272-282

Wolstenholme's Theorem

In The Book of Prime Number Records (NY: Springer-Verlag, 1988), p. 21, Paulo Ribenboim states that "In 1862, Wolstenholme proved the following interesting result: If p is a prime, p >= 5, then the numerator of 1 + 1/2 + 1/3 + ... + 1/(p-1) is divisible by p^2."

The character Augustus Carmichael in Virginia Woolf's novel To the Lighthouse is based on Joseph Wolstenholme (1829-1891), according to a short biography in the MacTutor History of Mathematics archive.

Note that 1 + 1/2 + 1/3 + ... + 1/(p-1) in Wolstenholme's Theorem is a harmonic number. The following table shows how prime numbers >= 5 are related to harmonic numbers by Wolstenholme's Theorem.

Some columns of this table correspond to sequences in Neil Sloane's On-Line Encyclopedia of Integer Sequences:

• The "Harmonic Number Numerator" column is sequence A076637
• The "Harmonic Number Denominator" column is sequence A076638
• The "Harmonic Number Numerator / Prime^2" column is sequence A0610002

Here is a class, WolstenholmeTheorem.java, which applies the primality test inherent in Wolstenholme's Theorem to successive harmonic numbers. It re-uses the Harmonic Number Generator class presented above.

import java.math.BigInteger;

public abstract class WolstenholmeTheorem {

  public static boolean isPrime (BigInteger toCheck, BigFraction harmonicNum) {
    BigInteger squared = toCheck.multiply (toCheck);
    BigInteger mod = harmonicNum.numerator ().mod (squared);
    return mod.equals (BigInteger.ZERO);
  }

  public static void main (String[] args) {
    BigFraction harmonicNumber;
    BigInteger intObj;
    HarmonicNumbers gen = new HarmonicNumbers ();
    int toCheck;
    for (int i = 1; i < 20; i++) {
      harmonicNumber = gen.getNext ();
      toCheck = i + 1;
      if (toCheck >= 5) {
        intObj = new BigInteger (Integer.toString (toCheck));
        System.out.println ("Testing " + toCheck + ", harmonic number " +
                            harmonicNumber.toString ());
        if (WolstenholmeTheorem.isPrime (intObj, harmonicNumber)) {
          System.out.println (toCheck + " is prime");
        }
      }
    }
   }

}

Fractran Algorithm

The mathematician John Horton Conway invented an algorithm known as Fractran:

1. Start with a list of fractions (f) and an integer (n).
2. Find the first fraction in f where the product of f(i) and n is an integer. If there is none, stop. If there is, set n equal to the product and repeat step 2.

Here are some useful links about the Fractran algorithm.

• Ken Monks, Fun Facts: Chaos and Fractals
• Eric Weisstein, Fractran Algorithm

import java.math.BigInteger;

//-------------------
// Fractran algorithm
//-------------------

public class Fractran {

  private BigFraction[] fractions; 
  private BigInteger seed;
  private BigInteger current;

  //------------
  // Constructor
  //------------

  public Fractran (BigFraction[] fractions, BigInteger seed) {
    this.fractions = fractions;
    this.seed = seed;
    current = null;
  }

  //----------------------------------------
  // Get log base 2 (-1 if not a power of 2)
  //----------------------------------------

  public static int getLogBase2 (BigInteger n) {
    int result = -1;
    if (n.bitCount () == 1) {
      result = n.getLowestSetBit ();
    }
    return result;
  }

  //-----------------------------
  // Get next term (0 if no more)
  //-----------------------------

  public BigInteger getNext () {
    if (current == null) {
      current = seed;
      return current;
    }

    BigFraction fraction = null;
    BigFraction product = null;
    BigInteger result = BigInteger.ZERO;
    for (int i = 0; i < fractions.length; i++) {
      fraction = fractions[i];
      product = fraction.multiply (current);
      if (product.denominator ().equals (BigInteger.ONE)) {
        result = product.numerator ();
        current = result;
        break;
      }
    }
    return result;
  }

}

Conway's Prime Game

The Fractran algorithm is an interesting (but terribly inefficient) way to generate prime numbers. John H. Conway and Richard K. Guy, in The Book of Numbers (NY: Copernicus, 1996), pp. 147-148, give "Fourteen Fruitful Fractions" which yield prime numbers when the Fractran algorithm is applied to them. Here is a Java implementation (PrimeGame.java):

import java.math.BigInteger;

public class PrimeGame {

  public static void main (String[] args) {
    BigFraction[] fractions = {
      new BigFraction ("17/91"),
      new BigFraction ("78/85"),
      new BigFraction ("19/51"),
      new BigFraction ("23/38"),
      new BigFraction ("29/33"),
      new BigFraction ("77/29"),
      new BigFraction ("95/23"),
      new BigFraction ("77/19"),
      new BigFraction ("1/17"),
      new BigFraction ("11/13"),
      new BigFraction ("13/11"),
      new BigFraction ("15/2"),
      new BigFraction ("1/7"),
      new BigFraction ("55/1")
    };

    Fractran app = new Fractran (fractions, new BigInteger ("2"));
    BigInteger next = null;
    int logBase2 = 0;
    for (int i = 0; i < 10000; i++) {
      next = app.getNext ();
      if (next.equals (BigInteger.ZERO)) {
        System.out.println ("Terminated");
        break;
      }
      else {
        logBase2 =  Fractran.getLogBase2 (next);
        if (logBase2 >= 2) {
          System.out.println (logBase2 + " (at iteration " + i + ")");
        }
      }
    }
    System.out.println ("Done");
  }
}

Output from the program just shown is

2 (at iteration 19)
3 (at iteration 69)
5 (at iteration 281)
7 (at iteration 710)
11 (at iteration 2375)
13 (at iteration 3893)
17 (at iteration 8102)
Done