Farey Fractions of level one are defined as a sequence (0/1, 1/1). This sequence

Question

Farey Fractions of level one are defined as a sequence (0/1, 1/1). This sequence is extended in level two to form a sequence (0/1, 1/2, 1/1), sequence (0/1, 1/3, 1/2, 2/3, 1/1) at level three, sequence (0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1) at level four, so that at each level n, a new fraction (a + b)/(c + d) is inserted between two neighbour fractions a/c and b/d only if c + d <= n.
Write a program which for a number n entered by the user creates – by constantly extending – an arraylist of fractiaons at level n and displays them.
A Sample output session is shown here:
Enter n: 5
1: (0/1, 1/1)
2: (0/1, 1/2, 1/1)
3: (0/1, 1/3, 1/2, 2/3, 1/1)
4: (0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1)

5: (0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1)

Explanation / Answer

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));
}

}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.