# Find Index of Rational Number in Calkin-Wilf Sequence

Related

From Wikipedia:

In number theory, the Calkin–Wilf tree is a tree in which the vertices correspond one-to-one to the positive rational numbers. The tree is rooted at the number $$\1\$$, and any rational number expressed in simplest terms as the fraction $$\\frac{a}{b}\$$ has as its two children the numbers $$\\frac{a}{a+b}\$$ and $$\\frac{a+b}{b}\$$.

The Calkin–Wilf sequence is the sequence of rational numbers generated by a breadth-first traversal of the Calkin–Wilf tree, $$\frac11, \frac12, \frac21, \frac13, \frac32, \frac23, \frac31, \frac14, \frac43, \frac35, \frac52, \ldots$$

For this challenge, you are given a fraction found in the $$\i\$$th position of the Calkin-Wilf sequence, and must output $$\i\$$. You can start from either 0 or 1.

## Test cases

(Starting from 1.)

$$\a_i\$$ $$\i\$$
$$\\frac11\$$ $$\1\$$
$$\\frac13\$$ $$\4\$$
$$\\frac43\$$ $$\9\$$
$$\\frac34\$$ $$\14\$$
$$\\frac{53}{37}\$$ $$\1081\$$
$$\\frac{37}{53}\$$ $$\1990\$$

Standard loopholes are forbidden. Since this is , the shortest code wins.

# JavaScript (ES6), 33 bytes

Expects a pair of integers (p,q) representing the fraction $$\p/q\$$.

f=(p,q)=>p&&1+f(q+p-(q%p||p)*2,p)


Try it online!

### How?

This version is based on the nice recurrence formula found by alephalpha:

\begin{align}f(0)&=0\\f(x)&=1+f(2\lceil1/x\rceil-1-1/x)\end{align}

It was modified to work with two integers $$\p/q=x\$$ instead of a native fraction and without an explicit ceiling function:

$$\lceil q/p\rceil=\begin{cases} q/p,&q\equiv 0\pmod p\\ (q+p-(q \bmod p))/p,&q\not\equiv 0\pmod p\end{cases}$$

We have:

$$f(2\lceil1/x\rceil-1-1/x)=f(2\lceil q/p\rceil-p/p-q/p)$$

which is turned into the following JS code:

f(q % p ? q + p - q % p * 2 : q - p, p)


which can be further simplified to:

f(q + p - (q % p || p) * 2, p)


# JavaScript (ES6), 40 bytes

Expects a pair of integers (p,q) representing the fraction $$\p/q\$$.

f=(p,q)=>p-q?p>q?f(p-q,p)+1:2*f(p,q-p):1


Try it online!

### Commented

f = (p, q) =>   // (p, q) = input pair
p - q ?         // if p is not equal to q:
p > q ?       //   if p is greater than q:
//     we're located on the right branch
f(p - q, p) //     turn it into the corresponding left branch
+ 1         //     and add 1
:             //   else:
//     we're located on the left branch
2 *         //     double the result of
f(p, q - p) //     a recursive call with the parent fraction
:               // else:
//   we've reached the root
1             //   stop and return 1


# PARI/GP, 29 bytes

f(x)=if(x,1+f(-1\-x*2-1-1/x))


Attempt This Online!

\\begin{align}f(0)&=0\\f(x)&=1+f(2\lceil1/x\rceil-1-1/x)\end{align}\

• How the hell does this even work?? Is it based on the recursive formula on Wikipedia to find the $i$'th term in the sequence $q_{i+1}=\frac1{2\lfloor q_i\rfloor-q_i+1}$? Apr 27 at 2:29
• @AidenChow Yes. $q_{i+1}=1/(2\lfloor{q_i}\rfloor-q_i+1)\Rightarrow 1/q_{i+1}-1=\lfloor{q_i}\rfloor-(q_i-\lfloor{q_i}\rfloor)$. $\lfloor{q_i}\rfloor$ is an integer and $0\le q_i-\lfloor{q_i}\rfloor<1$, so $\lceil{1/q_{i+1}-1}\rceil=\lfloor{q_i}\rfloor$, $q_i-\lfloor{q_i}\rfloor=\lceil{1/q_{i+1}-1}\rceil-(1/q_{i+1}-1)$. Thus $q_i=\lfloor{q_i}\rfloor+(q_i-\lfloor{q_i}\rfloor)=\lceil{1/q_{i+1}-1}\rceil+(\lceil{1/q_{i+1}-1}\rceil-(1/q_{i+1}-1))=2\lceil{1/q_{i+1}}\rceil-1-1/q_{i+1}$. Apr 27 at 2:38
• what the hell.... how you thinking of these things? i try convert that equation into something useful but came up short..... Apr 27 at 2:46

# Vyxal, 12 bytes

g-¨£∨)↔vÞṘṘB


Try it Online!

Takes input as a pair of numbers.

g-¨£∨)↔vÞṘṘB

# function taking a pair and returning its parent:
g-           #   subtract minimum
¨£∨        #   zip and return the last truthy element from each pair
)       # end function
↔      # apply until fixed point and collect intermediate results
vÞṘ   # vectorizing is sorted in reverse?
Ṙ  # reverse
B # convert from binary


# Python, 34 bytes (@Neil)

f=lambda Q:Q and 1+f(1/Q-1-2/Q%-2)


Attempt This Online!

Port of @Arnauld's latest and greatest which ports @alephalpha's.

Expects a Python Fraction object.

#### Previous Python, 44 bytes (@xnor)

f=lambda Q:Q==1or(Q>1)+2*f(max(Q/(1-Q),Q-1))


Attempt This Online!

#### Original Python, 46 bytes

f=lambda Q:Q==1or(Q>1)+2*f([Q/(1-Q),Q-1][Q>1])


Attempt This Online!

Expects a Python Fraction object.

Similar but as far as I can tell not identical to @Arnauld's approach.

• Selecting with max also seems to work.
– xnor
Apr 27 at 5:09
• A port of @Arnauld's latest formula is at most 35 bytes: f=lambda p,q:p and-~f(q-q%-p*2-p,p).
– Neil
Apr 27 at 19:07
• Thanks, @Neil. Using fractions I managed to shave one off. Apr 27 at 21:02

# Raku, 25 bytes

+*o{{1/$_-1-2/$_%-2}...0}


Try it online!

Port of @loopy walt's answer, which is a port of @Arnauld's, which is a port of @alephalpha's.

# J, 24 bytes

*(1+%$:@-~_1+2*>.@%)@.*  -4, port of @Jo King's answer, which is a port of @loopy walt's, which is a port of @Arnauld's, which is a port of @alephalpha's. Attempt This Online! *(1+%$:@-~_1+2*>.@%)@.*
*  NB. signum, 0 for 0, 1 for everything else
@.   NB. index into the gerund list and execute
*                         NB. if 0, use signum again to return 0
(                 )     NB. if 1, execute the recursive function
NB. uses the formula in alephalpha's PARI/GP answer
$:@ NB. recurse here  ### Original 28 bytes [:#[(1%1+]-~2*<.@])^:~:^:a:*  In short, returns the length of the sequence up to the input. Expects a rational number. Attempt This Online! [:#[(1%1+]-~2*<.@])^:~:^:a:* * NB. signum, returns 1 for all inputs to give initial value [ NB. input unchanged ( )^:~:^:a: NB. form for a do-while that uses a: to collect results into an array NB. u^:v^:_ v is a boolean function and u modifies the initial value a: NB. empty box ~: NB. continue if input is not equal to current value <.@] NB. floor the right arg (qᵢ) 2* NB. double ]-~ NB. subtract by qᵢ 1+ NB. increment 1% NB. reciprocal [: NB. then # NB. take the length  # Arturo, 49 bytes f:$[p q][(p=q)?->1->(p>q)?->1+f p-q p->2*f p q-p]


Try it

# Jelly, 11 bytes

Uses AndrovT's method from their Vyxal answer, go upvote!

_ṂoƊƬ</€¬ṚḄ


A monadic Link that accepts a pair of co-prime positive integers, [numerator, denominator] and yields the 1-indexed index of that fraction in

Try it online!

### How?

_ṂoƊƬ</€¬ṚḄ - Link: pair of positive, coprime integers, [N,D]
Ṃ          -     minimum ([N,D])
_           -     ([N,D]) subtract (that) (vectorises)   -> [0,D-N] or [N-D,0]
o         -     (that) logical OR ([N,D]) (vectorises) -> [N,D-N] or [N-D,D]
€    - for each ([numerator, denominator] pair in the collected results):
/     -   reduce by:
<      -     is (the numerator) less than (the denominator)?
¬   - logical NOT (vectorises)
Ṛ  - reverse
Ḅ - convert from binary


Loads of $$\11\$$s, is there a $$\10\$$?

e.g.:

_ṂoƊƬṚUṢƑ€Ḅ
_ṂoƊƬṚZ</¬Ḅ
_ṂoƊƬIF<1ṚḄ


# Rust, 918481 77 bytes

Based on the recursive relation:

$$a_n = b_{n-1}$$ $$b_n = 2\cdot b_{n-1} \cdot \left \lfloor \frac{a_{n-1}}{b_{n-1}} \right \rfloor - a_{n-1} + b_{n-1}$$

0-indexed. Recursion is very verbose in rust so I hope this is shorter than the recursive version most other answers use.

|m|{let mut d=(1,1,1);while(d.0,d.1)!=m{d=(d.1,d.0+d.1-d.0%d.1*2,d.2+1)};d.2}


Attempt This Online!

• if*n==m{None}else{...;Some(0)} => (*n!=m).then(||{...;0}) Apr 27 at 10:24
• d.0+d.1-d.0%d.1*2 is a shorter formula (a(n) = a(n-2) + a(n-1) - 2*(a(n-2) mod a(n-1)) from OEIS A002487).
– Neil
Apr 27 at 19:12

# Prolog (SWI), 59 53 bytes

Thanks @Jo King for -6 bytes and fixing the floating point issue

0+0.
N+X:-A is 2*ceiling(1/N)-1-1rdiv N,A+B,X is B+1.


Took the recursive formula from @alephalpha's answer, so make sure to upvote his answer as well!

Try it online!

• You can avoid the float inaccuracies by passing in rational numbers, e.g. 53 bytes. In updated versions of Prolog SWI, you can do 1r2 to represent a rational number
– Jo King
Apr 27 at 6:25
• @JoKing Huh, thanks for the info! I didn't realize rdiv was a thing... Apr 27 at 7:05
• Huh, also didn't realize that putting the 0+0. case on its own would work... usually when i do that the N isn't evaluated or smth and the code doesn't work, so I now just put everything in one line so that the N<(number) would evaluate the N without me having to worry about anything. I guess it just works in this case... Apr 27 at 7:09

# Scala, 72 bytes

Golfed version. Try it online!

def f(p:Int,q:Int):Int=if(p-q!=0)if(p>q)f(p-q,p)+1 else 2*f(p,q-p)else 1


Ungolfed version. Try it online!

object Main {
def main(args: Array[String]): Unit = {
def f(p: Int, q: Int): Int = {
if (p - q != 0) {
if (p > q) {
f(p - q, p) + 1
} else {
2 * f(p, q - p)
}
} else {
1
}
}

println(f(1,1))
println(f(1,3))
println(f(4,3))
println(f(3,4))
println(f(53,37))
println(f(37,53))
}
}


# Charcoal, 34 24 bytes

ＮθＮηＷθ«≦⁻⁻η⊗﹪η±θθ≔ιη→»Ｉⅈ


Try it online! Link is to verbose version of code. 1-indexed. Takes input as two integers. Explanation: Port of @Arnauld's port of @alephalpha's answer.

ＮθＮη


Input the numerator and denominator.

Ｗθ«


Repeat until the numerator is zero.

≦⁻⁻η⊗﹪η±θθ


Calculate the next numerator. This uses true modulus, so instead of writing q + p - (q % p || p) I can write q - q % -p; the final expression is then q - q % -p * 2 - p.

≔ιη


Save the copy of the numerator that conveniently happens to be in the loop variable to the denominator.

→


Increment the count.

»Ｉⅈ


Output the final count.

Previous 34-byte version based on @AndrovT's answer:

≔Ｅ²ＮθＷ↨θ±¹«⊞υ‹ι⁰ＵＭθ∨⁻κ⌊θκ»⊞υ¹Ｉ↨⮌υ²


Try it online! Link is to verbose version of code. 1-indexed. Takes input as two integers. Explanation:

≔Ｅ²Ｎθ


Input the fraction.

Ｗ↨θ±¹«


Repeat until the numerator and denominator are equal.

⊞υ‹ι⁰


If the numerator was larger than push a 1 bit otherwise push a 0 bit.

ＵＭθ∨⁻κ⌊θκ»


Subtract the smaller element from the larger.

⊞υ¹


Push a final 1 bit.

Ｉ↨⮌υ²


Convert from base 2.

I could have done better by generating the sequence (36 33 bytes):

≔⮌Ｅ²ＮθＦ²⊞υ¹Ｗ¬⁼θυ«≔⁺⁻Συ⊗﹪⊟υυυυ→»Ｉⅈ


Try it online! Link is to verbose version of code. 0-indexed. Takes input as two integers. Explanation:

≔⮌Ｅ²Ｎθ


Input the fraction in reverse.

Ｆ²⊞υ¹


Start with 1 as the fraction.

Ｗ¬⁼θυ«


Repeat until the fraction is found.

≔⁺⁻Συ⊗﹪⊟υυυυ


Find the next fraction. (And yes, that is legitimately 4 υs in a row.)

→


Increment the loop count.

»Ｉⅈ


Output the final count.

# Ruby, 38 28 bytes

->m{m>0?1+f[1/m-1-2/m%-2]:0}


Try it online!

Using @alephalpha/@Arnauld formula like most of the answers.

# ><>, 36 bytes

ii$\l2-nao; :?!\$&:::&+:@$:@%:?$~2*-


Try it online!

Port of Arnauld's answer. Takes input as codepoints, e.g. 53/37 is 5%

# ><> (Fish), 59 bytes

1ii11$4[:{:{:{:\ @=r@={+2(?v]{n;\ *-+{1+}40.\r{]$:@$:@$:@%2


Try it

Despite not having a easy way to check tuple equality still shorter than rust. Uses the formula Neil suggested under my Rust answer.

## Explanation

1ii11 pushes the initial state.

$4[:{:{:{:@=r@={+2(?vr{] Checks if the 2 tuples are equal $:@$:@$:@\$2*-+ Performs the basic calculation of the next value for B

{1+} Adds one to the counter

]{n; Prints the result and exits, if the tuples are equal.