Rational Counting Function

Question

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.

Answer 1

Haskell, 78 characters

q(r,f)=[(r-b,b)|b<-f[1..r-1],r`gcd`b==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

Answer 2

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'

Answer 3

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]

Answer 4

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

Answer 5

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

Answer 6

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