14
\$\begingroup\$

The positive rational numbers can be shown to be numerable with the following process:

  1. Zero has the ordinal 0
  2. Arrange the other numbers in a grid so that row a, column b contains a/b
  3. Plot a diagonal zig-zag top right to bottom left
  4. Keep a running tally of the unique numbers encountered along the zig-zag

Here's a picture of the zig-zag:

Start at 1/1, initial move right

So, the numbers encountered are, in order

1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 2/4, 3/3, 4/2, 5/1, 6/1, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 2/6, 3/5, 4/4, 5/3 ...

And the simplified, unique numbers encountered are

1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5, 5, 6, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 3/5, 5/3, ...

Challenge:

  • Given two greater-than-zero integers p and q, output the ordinal number of p/q
  • p and q are not necessarily co-prime
  • Shortest code wins
  • Standard loopholes are prohibited

Test cases:

Here are the first 24 rational numbers encountered, and the desired output for each:

1/1: 1
2/1: 2
1/2: 3
1/3: 4
2/2: 1
3/1: 5
4/1: 6
3/2: 7
2/3: 8
1/4: 9
1/5: 10
2/4: 3
3/3: 1
4/2: 2
5/1: 11
6/1: 12
5/2: 13
4/3: 14
3/4: 15
2/5: 16
1/6: 17
1/7: 18
2/6: 4
3/5: 19

And, for further test cases, here are the 200 first positive rational numbers in order:

1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5, 
5, 6, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 3/5, 5/3, 
7, 8, 7/2, 5/4, 4/5, 2/7, 1/8, 1/9, 3/7, 7/3, 
9, 10, 9/2, 8/3, 7/4, 6/5, 5/6, 4/7, 3/8, 2/9, 
1/10, 1/11, 5/7, 7/5, 11, 12, 11/2, 10/3, 9/4, 8/5, 
7/6, 6/7, 5/8, 4/9, 3/10, 2/11, 1/12, 1/13, 3/11, 5/9, 
9/5, 11/3, 13, 14, 13/2, 11/4, 8/7, 7/8, 4/11, 2/13, 
1/14, 1/15, 3/13, 5/11, 7/9, 9/7, 11/5, 13/3, 15, 16, 
15/2, 14/3, 13/4, 12/5, 11/6, 10/7, 9/8, 8/9, 7/10, 6/11, 
5/12, 4/13, 3/14, 2/15, 1/16, 1/17, 5/13, 7/11, 11/7, 13/5, 
17, 18, 17/2, 16/3, 15/4, 14/5, 13/6, 12/7, 11/8, 10/9, 
9/10, 8/11, 7/12, 6/13, 5/14, 4/15, 3/16, 2/17, 1/18, 1/19, 
3/17, 7/13, 9/11, 11/9, 13/7, 17/3, 19, 20, 19/2, 17/4, 
16/5, 13/8, 11/10, 10/11, 8/13, 5/16, 4/17, 2/19, 1/20, 1/21, 
3/19, 5/17, 7/15, 9/13, 13/9, 15/7, 17/5, 19/3, 21, 22, 
21/2, 20/3, 19/4, 18/5, 17/6, 16/7, 15/8, 14/9, 13/10, 12/11, 
11/12, 10/13, 9/14, 8/15, 7/16, 6/17, 5/18, 4/19, 3/20, 2/21, 
1/22, 1/23, 5/19, 7/17, 11/13, 13/11, 17/7, 19/5, 23, 24, 
23/2, 22/3, 21/4, 19/6, 18/7, 17/8, 16/9, 14/11, 13/12, 12/13, 
11/14, 9/16, 8/17, 7/18, 6/19, 4/21, 3/22, 2/23, 1/24, 1/25 

Shout out to the inverse question, where the first move is down so you can't use the answers to generate additional test cases.

\$\endgroup\$
4
\$\begingroup\$

Jelly,  21  20 bytes

Probably beatable by a number of bytes using some clever mathematics...

:g/
ǵSRRUĖ€UÐeẎÇ€Qi

A monadic link accepting a list of [p,q] which returns the natural number assigned to p/q.

Try it online! Or see the test-suite.

How?

First note that the Nth diagonal encountered contains all of the grid's rational numbers for which the sum of the numerator and denominator equals N+1, so given a function which reduces a [p,q] pair to simplest form ([p/gcd(p,q),q/gcd(p,q)]) we can build the diagonals as far as need be*, reduce all the entries, de-duplicate and find the index of the simplified input.

* actually one further here to save a byte

:g/ - Link 1, simplify a pair: list of integers, [a, b]
  / - reduce using:
 g  - Greatest Common Divisor -> gcd(a, b)
:   - integer division (vectorises) -> [a/gcd(a,b), b/gcd(a,b)]

ǵSRRUĖ€UÐeẎÇ€Qi - Main Link: list of integers, [p, q]
Ç                - call last Link as a monad (simplify)
 µ               - start a new monadic chain (call that V)
  S              - sum -> the diagonal V will be in plus one
   R             - range -> [1,2,3,...,diag(V)+1]
    R            - range (vectorises) -> [[1],[1,2],[1,2,3],...,[1,2,3,...,diag(V)+1]]
     U           - reverse each       -> [[1],[2,1],[3,2,1],[diag(V)+1,...,3,2,1]]
      Ė€         - enumerate €ach     -> [[[1,1]],[[1,2],[2,1]],[[1,3],[2,2],[3,1]],[[1,diag(V)+1],...,[diag(V)-1,3],[diag(V),2],[diag(V)+1,1]]]
         Ðe      - apply only to the even indexed items:
        U        -   reverse each     -> [[[1,1]],[[2,1],[1,2]],[[1,3],[2,2],[3,1]],[[4,1],[3,2],[2,3],[1,4]],...]
           Ẏ     - tighten            -> [[1,1],[2,1],[1,2],[1,3],[2,2],[3,1],[4,1],[3,2],[2,3],[1,4],...]
            Ç€   - for €ach: call last Link as a monad (simplify each)
                 -                    -> [[1,1],[2,1],[1,2],[1,3],[1,1],[3,1],[4,1],[3,2],[2,3],[1,4],...]
              Q  - de-duplicate       -> [[1,1],[2,1],[1,2],[1,3],[3,1],[4,1],[3,2],[2,3],[1,4],...]
               i - index of V in that list
\$\endgroup\$
3
\$\begingroup\$

Perl 6,  94  90 bytes

->\p,\q{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique.first(p/q,:k)+1}

Test it

{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique.first($^p/$^q):k+1}

Test it

This basically generates the entire sequence of values, and stops when it finds a match.

Expanded:

{  # bare block lambda with placeholder parameters $p,$q

  (
      ( # sequence of numerators

        {
          |( # slip into outer sequence (flatten)

            1      # start at one
            …
            (
              $    # state variable
              += 2 # increment it by two each time this block is called
            )
            …
            1      # finish at one
          )

        }
        … * # never stop generating values
      )


    Z/   # zip using &infix:« /  » (generates Rats)


      ( # sequence of denominators

        1,  # start with an extra one

        {
          |( # slip into outer sequence (flatten)

            1
            …
            (
              ( $ ||= 1 ) # state variable that starts with 1 (rather than 0)
              += 2        # increment it by two each time this is called
            )
            …
            1
          )
        }
        … * # never stop generating values
      )


  ).unique            # get only the unique values
  .first( $^p / $^q ) # find the first one that matches the input
  :k                  # get the index instead (0 based)
  + 1                 # add one               (1 based)
}

({1…($+=2)…1}…*) generates the infinite sequence of numerators (|(…) is used above to flatten)

(1 2 1)
(1 2 3 4 3 2 1)
(1 2 3 4 5 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1)
…

(1,{1…(($||=1)+=2)…1}…*) generates the infinite sequence of denominators

1
(1 2 3 2 1)
(1 2 3 4 5 4 3 2 1)
(1 2 3 4 5 6 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 5 4 3 2 1)
…
\$\endgroup\$
3
\$\begingroup\$

Python 2, 157 144 137 134 126 125 bytes

def f(p,q):a=[((j-i)/(i+1.))**(j%-2|1)for j in range(p-~q)for i in range(j)];return-~sorted(set(a),key=a.index).index(p*1./q)

Try it online!

4 bytes saved due to Mr. Xcoder; 1 byte from Jonathon Frech.

As noted by Mr. Xcoder, we can do a bit better in Python 3 since, amongst other things, integer division defaults to float results, and we can more easily unpack lists:

Python 3, 117 bytes

def f(p,q):a=[((j-i)/-~i)**(j%-2|1)for j in range(p-~q)for i in range(j)];return-~sorted({*a},key=a.index).index(p/q)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 128 bytes (-6) by swapping the fraction and using **(j%-2|1) and p-~q. \$\endgroup\$ – Mr. Xcoder Jun 17 '18 at 20:48
  • \$\begingroup\$ @Mr. Xcoder: You're all about the negative modulo today! :) I think I still need the +1 at the end, since 1,1 'must' give 1, not 0. \$\endgroup\$ – Chas Brown Jun 17 '18 at 21:04
  • \$\begingroup\$ 125 bytes. \$\endgroup\$ – Jonathan Frech Jun 17 '18 at 21:14
  • \$\begingroup\$ 124 bytes :) Yeah the negative modulo turns out to be really helpful! \$\endgroup\$ – Mr. Xcoder Jun 17 '18 at 21:17
  • \$\begingroup\$ Actually 117 bytes in Python 3 \$\endgroup\$ – Mr. Xcoder Jun 17 '18 at 21:21
3
\$\begingroup\$

Python 3, 157, 146, 140, 133 bytes

def f(p,q):a=[(i+i-abs(j-i-i))/(abs(j-i-i+.5)+.5)for i in range(p+q)for j in range(4*i)];return sorted(set(a),key=a.index).index(p/q)

Try it online!

won 11 bytes thanks to Jonathan Frech

won 6 more bytes and then 7 thanks to Chas Brown

\$\endgroup\$
  • 1
    \$\begingroup\$ 146 bytes. \$\endgroup\$ – Jonathan Frech Jun 17 '18 at 21:07
  • \$\begingroup\$ 140 bytes. \$\endgroup\$ – Chas Brown Jun 17 '18 at 21:12
  • \$\begingroup\$ @bobrobbob: Welcome to PPCG! I'm not quite sure how your algorithm works (although it clearly does); but experimentally, it seems you can save some more bytes by replacing range(max(p,q)+1) with range(p+q). \$\endgroup\$ – Chas Brown Jun 18 '18 at 3:46
  • 1
    \$\begingroup\$ You can save some more bytes by using {*a} instead of set(a). \$\endgroup\$ – Mr. Xcoder Jun 18 '18 at 9:18
2
\$\begingroup\$

J, 41, 35, 30 bytes

-11 bytes thanks to FrownyFrog

%i.~0~.@,@,[:]`|./.[:%/~1+i.@*

Try it online!

original 41 bytes post with explanation

%>:@i.~[:([:~.@;[:<@|.`</.%"1 0)~(1+i.@*)

ungolfed

% >:@i.~ [: ([: ~.@; [: <@|.`</. %"1 0)~ 1 + i.@*

explanation

                  +
                  | Everything to the right of this
                  | calculates the list
p (left arg)      |                                      create the
divided by q      |                                      diagonals.  yes,
      (right)     |                                     +this is a         +create this list
   |              |        ++ finally rmv ^alternately  |primitive ADVERB  |1..(p*q), and pass
   |   + the index          | the boxes,  |box, or      |in J              |it as both the left
   |   | of that  |         | and remove  |reverse and  |                  |and right arg to the
   |   | in the   |         | any dups    |box, each    |                  |middle verb, where each
   |   | list on  |         |             |diagonal     |                  |element will divide the
   |   | the right|         |             |             |       +----------+entire list, producing
   |   | plus 1   |         |             |             |       |          |the undiagonalized grid
   |   |          |         |             |             |       |          |
   |   |          |         |             |             |       |          |
   |   |          +         |             |             |       |          |
  ┌+┬──|──────────┬─────────|─────────────|─────────────|───────|──────────|─────────────┐
  │%│┌─+───────┬─┐│┌──┬─────|─────────────|─────────────|───────|────────┬─|────────────┐│
  │ ││┌──┬─┬──┐│~│││[:│┌────|─────────────|─────────────|───────|─────┬─┐│┌+┬─┬────────┐││
  │ │││>:│@│i.││ │││  ││┌──┬|───────┬─────|─────────────|───────|────┐│~│││1│+│┌──┬─┬─┐│││
  │ ││└──┴─┴──┘│ │││  │││[:│+──┬─┬─┐│┌──┬─|─────────────|─┬─────|───┐││ │││ │ ││i.│@│*││││
  │ │└─────────┴─┘││  │││  ││~.│@│;│││[:│┌|───────────┬─+┐│┌─┬─┬+──┐│││ │││ │ │└──┴─┴─┘│││
  │ │             ││  │││  │└──┴─┴─┘││  ││+────────┬─┐│/.│││%│"│1 0││││ ││└─┴─┴────────┘││
  │ │             ││  │││  │        ││  │││┌─┬─┬──┐│<││  ││└─┴─┴───┘│││ ││              ││
  │ │             ││  │││  │        ││  ││││<│@│|.││ ││  ││         │││ ││              ││
  │ │             ││  │││  │        ││  │││└─┴─┴──┘│ ││  ││         │││ ││              ││
  │ │             ││  │││  │        ││  ││└────────┴─┘│  ││         │││ ││              ││
  │ │             ││  │││  │        ││  │└────────────┴──┘│         │││ ││              ││
  │ │             ││  │││  │        │└──┴─────────────────┴─────────┘││ ││              ││
  │ │             ││  ││└──┴────────┴────────────────────────────────┘│ ││              ││
  │ │             ││  │└──────────────────────────────────────────────┴─┘│              ││
  │ │             │└──┴──────────────────────────────────────────────────┴──────────────┘│
  └─┴─────────────┴──────────────────────────────────────────────────────────────────────┘

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 35: 1+~.@;@([:<@|.`</.%~/~)@(1+i.@*)i.% \$\endgroup\$ – FrownyFrog Jun 17 '18 at 20:47
  • \$\begingroup\$ thank you, very nice! i will update it fully later since it will require redoing the explanation... \$\endgroup\$ – Jonah Jun 17 '18 at 20:53
  • \$\begingroup\$ And 30: %i.~0~.@,@,[:]`|./.[:%/~1+i.@* \$\endgroup\$ – FrownyFrog Jun 17 '18 at 21:09
  • \$\begingroup\$ that’s clever, use 0 and ~. to avoid the boxing and the increment, i love it \$\endgroup\$ – Jonah Jun 17 '18 at 21:44
2
\$\begingroup\$

Python 3, 121 bytes

import math
def o(x,y):
 p=q=n=1
 while x*q!=p*y:a=p+q&1;p+=1+a*~-~-(p<2);q+=1-~-a*~-~-(q<2);n+=math.gcd(p,q)<2
 return n
\$\endgroup\$
2
\$\begingroup\$

Rust, 244 bytes

I created a simple formula to find the "plain" ordinal of a "plain" zigzag, without the constraints of the puzzle, using triangular numbers formulas: https://www.mathsisfun.com/algebra/triangular-numbers.html . This was modified with modulo 2 to account for the zig-zags flipping their direction each diagonal row in the puzzle. This is function h()

Then for the main trick of this puzzle: how to 'not count' certain repeating values, like 3/3 vs 1/1, 4/2 vs 2/1, in the zig-zag trail. I ran the 1-200 examples, and noticed the difference between a plain zig-zag triangular counter, and the one the puzzle wishes for, has a pattern. The pattern of "missing" numbers is 5, 12, 13, 14, 23, etc, which resulted in a hit in the OEIS. It is one described by Robert A Stump, at https://oeis.org/A076537 , in order to "deduplicate" numbers like 3/3, 4/2, and 1/1, you can check whether GCD>1 for the x,y of all "previous" ordinals in the zigzag. This is the 'for' loops and g() which is the gcd.

I guess with some builtin gcd it would have been shorter, but I kind of couldn't find one very easily (im kind of new at Rust and Integer confused me), and I like the fact that this one uses straight up integer arithmetic, and no builtins or libraries of any kind.

fn f(x:i64,y:i64)->i64 {
        fn h(x:i64,y:i64)->i64 {let s=x+y;(s*s-3*s+4)/2-1+(s+1)%2*x+s%2*y}
        fn g(x:i64,y:i64)->i64 {if x==0 {y} else {g(y%x,x)}}
        let mut a=h(x,y);
        for i in 1..x+y {for j in 1..y+x {if h(i,j)<h(x,y) && g(i,j)>1 {a-=1;}}}
        a
}
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 86 bytes

Takes input in currying syntax (p)(q).

p=>q=>(g=x=>x*y?x*q-y*p?g(x+d,g[x/=y]=g[x]||++n,y-=d):n:g(x+!~d,y+=!~(d=-d)))(d=n=y=1)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Javascript, 79 bytes

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

(I am new to code golfing, so this can probably be improved easily)

Explanation

let a = (p, q) => p * q == 1 // If they are both 1
    ? 1
    // Do a recursive call and increment the result by 1
    : 1 + (
        (p + q) % 2 // If on an even-numbered diagonal
        ? q == 1 // If at the beginning of the diagonal
            ? a(p - 1, q) // Go to previous diagonal
            : a(p + 1, q - 1) // Go one back
        : p == 1 // rougly the same
            ? a(p, q - 1)
            : a(p - 1, q + 1)
    )
\$\endgroup\$
  • 4
    \$\begingroup\$ (3,5) should result in 19 (not 24) since (1,1)==(2,2)==(3,3), (2,4)==(1,2), (4,2)==(2,1) and (2,6)==(1,3). (i.e. (2,2) should result in 1 not 5, etc...) \$\endgroup\$ – Jonathan Allan Jun 17 '18 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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