10
\$\begingroup\$

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:

enter image description here

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.

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

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'
\$\endgroup\$
8
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ By definition, gcd (r-b) b == gcd r b and you can shave off four more characters. \$\endgroup\$ – Matías Giovannini May 9 '11 at 16:12
3
\$\begingroup\$

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]
\$\endgroup\$
2
\$\begingroup\$

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]}
\$\endgroup\$
2
\$\begingroup\$

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

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

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)
…
\$\endgroup\$

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.