The complete list of rational numbers with Stern-Brocot and Javascript

The Stern-Brocot sequence is a number sequence not too different from the Fibonacci series but created using a slightly different rule.

Just like with the Fibonacci sequence you sum the last two numbers to get the next, but then you also copy the very last digit and add that as well.

____
1, 1
// Sum the current pair 1+1=2 and copy the second number 1.
   ____
1, 1, 2, 1
// Sum the current pair 1+2=3 and copy the second number 2.
      ____
1, 1, 2, 1, 3, 2
// Sum the current pair 2+1=3 and copy the second number 1.
         ____
1, 1, 2, 1, 3, 2, 3, 1
// Sum the current pair 1+3=4 and copy the second number 3.

1, 1, 2, 1, 3, 2, 3, 1, 4, 3

The exciting thing about the Stern-Brocot sequence is that it can be used to generate every possible fraction in their most simplified form. No misses, no duplicates.

____
1, 1 = 1/1
// 1 as the numerator and 1 as the denominator.
   ____
1, 1, 2 = 1/1, 1/2
// 1 as the numerator and 2 as the denominator.
      ____
1, 1, 2, 1 = 1/1, 1/2, 2/1
// 2 as the numerator and 1 as the denominator.
         ____
1, 1, 2, 1, 3 = 1/1, 1/2, 2/1, 1/3
// 1 as the numerator and 3 as the denominator.

Below is a Stern-Brocot generator written in Javascript as a recursive function.

const addSternBrocot = (seq, n) => {
  const n1 = seq[seq.length/2-1];
  const n2 = seq[seq.length/2];
  const next = seq.concat(n1+n2, n2);
  return --n ? addSternBrocot(next, n) : next;
};

addSternBrocot([1,1], 25); // ==> First 25 numbers.

Keywords