16
\$\begingroup\$

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

Improve this question
\$\endgroup\$

15 Answers 15

Reset to default
15
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
13
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ 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}\$? \$\endgroup\$
    – Aiden Chow
    Apr 27 at 2:29
  • 2
    \$\begingroup\$ @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}\$. \$\endgroup\$
    – alephalpha
    Apr 27 at 2:38
  • \$\begingroup\$ what the hell.... how you thinking of these things? i try convert that equation into something useful but came up short..... \$\endgroup\$
    – Aiden Chow
    Apr 27 at 2:46
10
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
9
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Selecting with max also seems to work. \$\endgroup\$
    – xnor
    Apr 27 at 5:09
  • \$\begingroup\$ 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). \$\endgroup\$
    – Neil
    Apr 27 at 19:07
  • \$\begingroup\$ Thanks, @Neil. Using fractions I managed to shave one off. \$\endgroup\$
    – loopy walt
    Apr 27 at 21:02
6
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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ṚḄ
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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}

Attempt This Online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ if*n==m{None}else{...;Some(0)} => (*n!=m).then(||{...;0}) \$\endgroup\$
    – alephalpha
    Apr 27 at 10:24
  • \$\begingroup\$ 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). \$\endgroup\$
    – Neil
    Apr 27 at 19:12
4
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ 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 \$\endgroup\$
    – Jo King ♦
    Apr 27 at 6:25
  • \$\begingroup\$ @JoKing Huh, thanks for the info! I didn't realize rdiv was a thing... \$\endgroup\$
    – Aiden Chow
    Apr 27 at 7:05
  • \$\begingroup\$ 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... \$\endgroup\$
    – Aiden Chow
    Apr 27 at 7:09
3
\$\begingroup\$

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))
  }
}
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

><>, 36 bytes

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

Try it online!

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

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

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

enter image description here

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.