Find Index of Rational Number in Calkin-Wilf Sequence

Question

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}\$.

Calkin-Wilf tree

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 code-golf, the shortest code wins.

Answer 1

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

Answer 2

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}\$

• Aiden Chow: 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}\$?
• alephalpha: @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}\$.
• Aiden Chow: what the hell.... how you thinking of these things? i try convert that equation into something useful but came up short.....

Answer 3

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

Answer 4

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.

• xnor: Selecting with max also seems to work.
• Neil: 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).
• loopy walt: Thanks, @Neil. Using fractions I managed to shave one off.

Answer 5

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.

Answer 6

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 (qi)
 2* NB. double
 ]-~ NB. subtract by qi
 1+ NB. increment
 1% NB. reciprocal
[: NB. then
 # NB. take the length

Answer 7

Arturo, 49 bytes

f:$[p q][(p=q)?->1->(p>q)?->1+f p-q p->2*f p q-p]

Try it

Port of Arnauld's JavaScript answer.

Answer 8

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]
 Ƭ - start with C=[N,D] and collect until a fixed-point applying:
 Ɗ - last three links as a monad - f([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ṚḄ

Answer 9

Rust, (削除) 91 (削除ここまで) (削除) 84 (削除ここまで) (削除) 81 (削除ここまで) 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}

• -7 bytes thanks to AlephaAlpha

• -4 bytes thanks to Neil

Attempt This Online!

• alephalpha: if*n==m{None}else{...;Some(0)} => (*n!=m).then(||{...;0})
• Neil: 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).

Answer 10

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!

• Jo King: 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
• Aiden Chow: @JoKing Huh, thanks for the info! I didn't realize rdiv was a thing...
• Aiden Chow: 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...

Answer 11

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

Answer 12

Charcoal, (削除) 34 (削除ここまで) 24 bytes

NθNηWθ«≦−−η⊗%η±θθ≔ιη→»Ii

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.

NθNη

Input the numerator and denominator.

Wθ«

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.

»Ii

Output the final count.

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

≔E2NθW↨θ±1«⊞υ‹ι0UMθ∨−κ⌊θκ»⊞υ1I↨⮌υ2

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

≔E2Nθ

Input the fraction.

W↨θ±1«

Repeat until the numerator and denominator are equal.

⊞υ‹ι0

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

UMθ∨−κ⌊θκ»

Subtract the smaller element from the larger.

⊞υ1

Push a final 1 bit.

I↨⮌υ2

Convert from base 2.

I could have done better by generating the sequence ((削除) 36 (削除ここまで) 33 bytes):

≔⮌E2NθF2⊞υ1W¬=θυ«≔+−Συ⊗%⊟υυυυ→»Ii

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

≔⮌E2Nθ

Input the fraction in reverse.

F2⊞υ1

Start with 1 as the fraction.

W¬=θυ«

Repeat until the fraction is found.

≔+−Συ⊗%⊟υυυυ

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

→

Increment the loop count.

»Ii

Output the final count.

Answer 13

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.

Answer 14

><>, 36 bytes

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

Try it online!

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

Answer 15

><> (Fish), 59 bytes

1ii114ドル[:{:{:{:\
@=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.

enter image description here