Rational Counting Function
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 listd
- Edit: (82 → 78) applied
gcd
identity as suggested by Matías
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:
x (, % +.) y
–a vector of length 2 representing the fraction with numeratorx
and denominatory
reduced to the smallest denominator1 + i. 1 + y
–a vector of integers from1
toy + 1
(, % +.)"0/~ 1 + i. 1 + y
–a matrix of all reduced fractions with unreduced denominator and numerator in the range from1
toy + 1
.<`(<@|.)/. y
–an array of the oblique diagonals of matrixy
, each other diagonal flipped~. ; y
–an array of diagonals collapsed into a vector of elements with duplicates removedx { y
–the item at positionx
iny
(u v) y
–the same asy u v y
. In this particular use case,u
is{
andv
is3 : '~. ; <`(<@|.)/. (, % +.)"0/~ 1 + i. 1 + y'
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]