8
\$\begingroup\$

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 an 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: 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!

Improve this question
\$\endgroup\$

5 Answers 5

Reset to default
14
\$\begingroup\$

JavaScript (ES11), 46 bytes

-2 thanks to @Shaggy
-2 thanks to @tsh

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

f=(n,d)=>[N]=n%d?[f(d,n%d)[1]+n/d*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] = // save in N the new numerator n % d ? // if d is not a divisor of n: [ // the numerator 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, // use n - 1 as the numerator d // use d = 1 as the denominator ] //
Improve this answer
\$\endgroup\$
6
  • 1
    \$\begingroup\$ 54? \$\endgroup\$ Commented Dec 12, 2024 at 2:30
  • 1
    \$\begingroup\$ That was an insomnia-driven-byte-shaving! Hence n/=d over n/d! \$\endgroup\$ Commented Dec 12, 2024 at 9:26
  • 1
    \$\begingroup\$ I don't know if this helps, but: if the last two convergents are \$[a_0;a_1,a_2,\dots,a_{k-1}] = m/c\$ and \$[a_0;a_1,a_2,\dots,a_k] = n/d\$, then another way of computing the parent is \$n'/d' = (n-m)/(d-c)\$. \$\endgroup\$ Commented Dec 12, 2024 at 9:29
  • 1
    \$\begingroup\$ Looks like you should be able to replace 1n at the end with d. \$\endgroup\$ Commented Dec 12, 2024 at 9:51
  • 1
    \$\begingroup\$ f=(n,d)=>[N]=n%d?[f(d,n%d)[1]+n/d*N,N]:[-~n,d] \$\endgroup\$ Commented Dec 21, 2024 at 3:28
5
\$\begingroup\$

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)!

Improve this answer
\$\endgroup\$
1
  • 3
    \$\begingroup\$ of course there would be a builtin \$\endgroup\$ Commented Dec 12, 2024 at 9:35
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Or 88 bytes but failed for large testcases: f=lambda x,y,a=1j,c=1,*q:(int(c.real),int(c.imag))*(a+c==x+y*1j)or f(x,y,*q,a,a+c,c,a+c) \$\endgroup\$ Commented Dec 13, 2024 at 6:05
  • \$\begingroup\$ 106 tio.run/… \$\endgroup\$ Commented Dec 13, 2024 at 13:07
2
\$\begingroup\$

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.)

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.