Find a fraction's parent in the Stern-Brocot tree

Question

Objective

Given a positive reduced fraction, output its parent in the Stern-Brocot tree. The outputted fraction shall also be reduced.

The Stern-Brocot tree

The Stern-Brocot tree is a infinite-height complete binary (search) tree that accommodates every positive reduced fraction exactly once. It is defined as follows:

• \$1/1\$ is the root.
• For every positive reduced fraction \$n/d\$, its left child is \$(n+n')/(d+d')\$ provided that \$n'/d'\$ is the biggest smaller ancestor of \$n/d\$, or \$n/(d+1)\$ if there's no such ancestor.
• Likewise, for every positive reduced fraction \$n/d\$, its right child is \$(n+n')/(d+d')\$ provided that \$n'/d'\$ is the smallest bigger ancestor of \$n/d\$, or \$(n+1)/d\$ if there's no such ancestor.

For illustrative purposes, here's the few shallowest entries of the Stern-Brocot tree:

Since \$1/1\$ doesn't have a parent, it is considered to be an invalid input.

Examples

Input -> Output

1/2 -> 1/1
2/1 -> 1/1
3/7 -> 2/5
4/7 -> 3/5
7/3 -> 5/2
7/4 -> 5/3
1/16 -> 1/15
16/1 -> 15/1
53/72 -> 39/53

Ungolfed Solution (Haskell)

import Data.Ratio

findParent :: Rational -> Rational
findParent x
  | x <= 0 = error "Nonpositive input"
  | otherwise = go 1 1 (0,1) (1,0) where
    go :: Rational -> Rational -> (Integer, Integer) -> (Integer, Integer) -> Rational
    go y z l@(ln, ld) r@(rn, rd) = case compare x z of
        EQ -> y
        LT -> go z ((numerator z + ln) % (denominator z + ld)) l (numerator z, denominator z)
        GT -> go z ((numerator z + rn) % (denominator z + rd)) (numerator z, denominator z) r

Try it online!

Answer 1

JavaScript (ES11), 48 bytes

-2 thanks to @Shaggy

Expects (n,d) as BigInts and returns [n',d'].

f=(n,d)=>n%d?[N]=[f(d,n%d)[1]+n/d*N,N]:[N=~-n,d]

Try it online!

Method

This is based on the relationship between Stern–Brocot trees and continued fractions.

Namely, if a rational number is represented by the continued fraction expression:

$$[a_0;a_1,a_2,\dots,a_k]$$

then its parent in the Stern-Brocot tree is represented by:

$$[a_0;a_1,a_2,\dots,a_k-1]$$

The function builds the continued fraction of the input \$n/d\$ during its recurse phase and then generates a new rational \$n'/d'\$ during its decurse phase using almost the same continued fraction, only with the last term decremented.

This algorithm is, quite surprisingly, very suitable for golfing.

Commented

f = (          // f is recursive function taking:
  n,           //   n = numerator
  d            //   d = denominator
) =>           //
n % d ?        // if d is not a divisor of n:
  [N] = [      //   save in N the new numerator
               //   which is obtained by:
    f(         //     doing a recursive call with:
      d,       //       d as the numerator
      n % d    //       n % d as the denominator
    )[1] +     //     taking the denominator returned by f
    n / d * N, //     adding floor(n / d) * N
    N          //   use N as the denominator
  ]            //   NB: the variable N, which is defined in
               //       the global scope, is first set by
               //       the last call and updated during the
               //       'decurse' phase, up to the root call
:              // else (end of recursion):
  [            //
    N = ~-n,   //   use N = n - 1 as the numerator
    d          //   use d = 1 as the denominator
  ]            //

Answer 2

Wolfram Language (Mathematica), 48 bytes

(r=ResourceFunction@"SternBrocot")@Floor[r@#/2]&

... yeah, there's a builtin (Mathematica has to load the builtin in a way that TIO can't handle), which we name r because it's used twice. The first use, r@#, takes the input rational number and returns its index in the flattened Stern–Brocot sequence. Conveniently, the index of the parent of a node in a binary tree is just half (rounded down) of the index of the node itself, which Floor[r@#/2] computes; then r applied to this new index returns the rational number at that index.

Wolfram Language (Mathematica), 67 bytes

FromContinuedFraction@Append[Most@#,Last@#-1]&@ContinuedFraction@#&

Try it online!

A direct port of Arnauld's solution—please upvote that one (which is even shorter than this ported version)!

Answer 3

R, 168 bytes

f=\(x,m=diag(2)[2:1,],a=cbind(m,m[,-1]+m[,-ncol(m)]),n=a[,order(a[1,]/a[2,])],p=n[,which(apply(n,2,identical,x))+c(-1,1)])`if`(ncol(p),p[,which.max(colSums(p))],f(x,n))

Attempt This Online!

Answer 4

Python3, 146 bytes

u=lambda a,b:[a[0]+b[0],b[1]+a[1]]
def f(n):
 q=[([0,1],[1,1],[1,0],0)]
 for a,b,c,p in q:
  if b==n:return p
  q+=[(a,u(a,b),b,b),(b,u(b,c),c,b)]

Try it online!

Answer 5

Charcoal, 52 49 bytes

≔Ｅ²ＮθＷ¬№υθ≔⊞ＯＥυ⟦§κ¹⁻Σκ⊗﹪§κ⁰§κ¹⟧Ｅ²¦¹υＩ§υ±⍘Φ⍘Ｌυ²⊖κ²

Try it online! Link is to verbose version of code. Explanation: Works by generating the Stern-Brocot sequence (formula now visible on my answer to Output the nth rational number according to the Stern-Brocot sequence) until the desired term and then deleting the second bit of the 1-indexed position of that term to find the 1-indexed position of the parent term.

≔Ｅ²Ｎθ

Input the desired term.

Ｗ¬№υθ

Repeat until the desired term is found.

≔⊞ＯＥυ⟦§κ¹⁻Σκ⊗﹪§κ⁰§κ¹⟧Ｅ²¦¹υ

For each term, calculate the next term, appending 1/1 to the end. This makes the program O(n²), which means that the last test case now times out on TIO, but that's code golf for you.

Ｉ§υ±⍘Φ⍘Ｌυ²⊖κ²

Index to find the parent term. (This works because the terms are in reverse order and negative indices are -1-based.)