# Rational Counting Function

Create a function that takes a natural number (starting from 0 inclusive), and returns a pair of positive integers, which are the numerator and denominator respectively. Use the diagonal traversal. Previous-counted numbers must be skipped. (you can memorize the set of skipped values)

Diagram:

Red are skipped values

Values:

• f(0) = 1, 1
• f(1) = 2, 1
• f(2) = 1, 2
• f(3) = 1, 3
• f(4) = 3, 1 (notice the skip)
• f(5) = 4, 1
• f(6) = 3, 2
• f(7) = 2, 3
• f(8) = 1, 4
• f(9) = 1, 5
• f(10) = 5, 1 (notice the skip)

You may use the Rational data structure and their operations if they exist. Shortest code wins.

• The number of counted rational numbers in each diagonal is the totient function of that diagonal's common sum. – Leaky Nun Aug 11 '16 at 15:49
• I know this challenge is old, but there exists a shorter answer than the accepted one, so you might want to re-accept. – Esolanging Fruit Nov 3 '17 at 4:19

## J, 41 36 characters

Takes an integers and returns a vector comprising two integers. My first solution that is neither entirely tacit nor entirely explicit.

{3 :'~.;<(<@|.)/.(,%+.)"0/~1+i.1+y'


Here is the solution with spaces inserted where appropriate:

{ 3 : '~. ; <(<@|.)/. (, % +.)"0/~ 1 + i. 1 + y'


An explanation:

1. x (, % +.) y–a vector of length 2 representing the fraction with numerator x and denominator y reduced to the smallest denominator
2. 1 + i. 1 + y–a vector of integers from 1 to y + 1
3. (, % +.)"0/~ 1 + i. 1 + y–a matrix of all reduced fractions with unreduced denominator and numerator in the range from 1 to y + 1.
4. <(<@|.)/. y–an array of the oblique diagonals of matrix y, each other diagonal flipped
5. ~. ; y–an array of diagonals collapsed into a vector of elements with duplicates removed
6. x { y–the item at position x in y
7. (u v) y–the same as y u v y. In this particular use case, u is { and v is 3 : '~. ; <(<@|.)/. (, % +.)"0/~ 1 + i. 1 + y'

q(r,f)=[(r-b,b)|b<-f[1..r-1],rgcdb==1]
d=reverse:id:d
f=((zip[2..]d>>=q)!!)


Sample run:

> map f [0..10]
[(1,1),(2,1),(1,2),(1,3),(3,1),(4,1),(3,2),(2,3),(1,4),(1,5),(5,1)]
> f 100
(17,1)
> f 1000
(3,55)


• Edit: (100 → 87) silly me, just testing the gcd is enough!
• Edit: (87 → 85) clever trick with cycle and functions to alternate row order
• Edit: (85 → 82) replace cycle with the hand-built infinite list d
• Edit: (82 → 78) applied gcd identity as suggested by Matías
• By definition, gcd (r-b) b == gcd r b and you can shave off four more characters. – Matías Giovannini May 9 '11 at 16:12

## Python, 144 chars

def F(i):
r,d,z=[1],1,[]
while z[:i]==z:z+=[(x,y)for x,y in zip(r[::d],r[::-d])if all(x%j+y%j for j in r[1:])];d=-d;r+=[r[-1]+1]
return z[i]


## Ruby 1.9, 109 106

F=->n{x=y=d=1
e=0
n.times{(x+=d).gcd(y+=e)>1&&redo
x<2?d<0?d=0:(d,e=1,-1):y<2?e<0?e=0:(d,e=-1,1):0}
[x,y]}


# OCaml + Batteries, 182 168 characters

This is what would be natural in Haskell but is only barely possible in OCaml:

open LazyList
let rec r(i,j)=lazy(let a,b=if(i+j)mod 2=0then i,j else j,i in
Cons((a,b),filter(fun(c,d)->a*d<>c*b)(r(if j=1 then 1,i+1else i+1,j-1))))
let f=nth(r(1,1))


Edit: The diagonal is unnecessary

# Perl 6, 75 bytes

{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique[$_]}  Test it This basically generates the entire sequence of rational values, only stopping once the indexed value is generated. (Based on my golf to another challenge.) ## Expanded: { # bare block lambda with implicit parameter$_

(
( # 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
.[ $_ ] # index into the sequence }  ({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)
…