# Number the positive rationals

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:

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.

• I wonder if there are alternative numbering schemes that make for shorter code.
– qwr
Commented Jun 17, 2018 at 23:32
• Numerators of fractions: oeis.org/A157807 denominators: oeis.org/A157813 No matches for ordinal sequence: oeis.org/…
– qwr
Commented Jun 17, 2018 at 23:38
• i see. you have to reduce the fraction and then count. its not the zig-zag only Commented Jun 19, 2018 at 4:36
• Commented Jun 21, 2018 at 14:12

# 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]
µ               - 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


# 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)
…


# Python 2, 157144137134126 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!

• 128 bytes (-6) by swapping the fraction and using **(j%-2|1) and p-~q. Commented Jun 17, 2018 at 20:48
• @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. Commented Jun 17, 2018 at 21:04
• Commented Jun 17, 2018 at 21:14
• 124 bytes :) Yeah the negative modulo turns out to be really helpful! Commented Jun 17, 2018 at 21:17
• Actually 117 bytes in Python 3 Commented Jun 17, 2018 at 21:21

# 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

• Commented Jun 17, 2018 at 21:07
• Commented Jun 17, 2018 at 21:12
• @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). Commented Jun 18, 2018 at 3:46
• You can save some more bytes by using {*a} instead of set(a). Commented Jun 18, 2018 at 9:18

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

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

# 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


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


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

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

• (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...) Commented Jun 17, 2018 at 14:22