9
\$\begingroup\$

Challenge

In this task you would be given an integer N (less than 10^5), output the Farey sequence of order N.

The input N is given in a single line,the inputs are terminated by EOF.

Input

4
3
1
2

Output

F4 = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1}
F3 = {0/1, 1/3, 1/2, 2/3, 1/1}
F1 = {0/1, 1/1}
F2 = {0/1, 1/2, 1/1}

Constraints

  • The number of inputs would not exceed 10^6 values
  • You can use any language of your choice
  • Shortest solution wins!
\$\endgroup\$
  • \$\begingroup\$ This will get loooong.....the output i mean. \$\endgroup\$ – st0le Mar 26 '11 at 8:49
  • \$\begingroup\$ Is N=0 permitted? \$\endgroup\$ – Eelvex Mar 26 '11 at 18:50
  • 4
    \$\begingroup\$ What's with the »(I)« in the title? \$\endgroup\$ – Joey Mar 28 '11 at 16:49
  • 2
    \$\begingroup\$ @Joey: Hmm. there's a Farey Sequence (II) now. Must be first edition! :-) \$\endgroup\$ – mellamokb Mar 30 '11 at 18:08
  • 1
    \$\begingroup\$ @mellamokb: Well, that one's a code challenge, though, so no title clash in any case. But yes, that sort of answers my question. \$\endgroup\$ – Joey Mar 30 '11 at 19:03
5
\$\begingroup\$

J, 96

('F',],' = {0/1',', 1/1}',~('r';'/')rplc~', ',"1":"0@(3 :'}./:~~.,(%~}:\)i.1x+y')&".);._2(1!:1)3

( /:~~.,(%~}:\)i.>:x:y gives the list; the rest is I/O and formatting (with bad style))

E.g:

4
3
1
2
F4 = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1}
F3 = {0/1, 1/3, 1/2, 2/3, 1/1}          
F1 = {0/1, 1/1}                         
F2 = {0/1, 1/2, 1/1}  

Edits

  • (114 → 106) Clearer appending ,
  • (106 → 105) Cap [: to At @
  • (105 → 101) Delete superfluous ": conversion
  • (101 → 99) Use infix \ for the list
  • (99 → 96)
\$\endgroup\$
  • \$\begingroup\$ I get |value error: rplc. Are you sure you didn't load 'strings' earlier in the session and forget about it? \$\endgroup\$ – Jesse Millikan Mar 29 '11 at 4:33
  • 1
    \$\begingroup\$ @Jesse: absolutely. I (almost) never use 'strings'. I just use the default linux-j-7.01 environment. \$\endgroup\$ – Eelvex Mar 29 '11 at 4:51
  • \$\begingroup\$ Ugh... I switched to j602 for wd and now I may need to switch back. :) \$\endgroup\$ – Jesse Millikan Mar 29 '11 at 5:04
3
\$\begingroup\$

Common Lisp, 156

(do((l()()))((not(set'n(read()()))))(dotimes(j n)(dotimes(i(1+ j))(push(/(1+ i
)(1+ j))l)))(format t"~&F~D = {0/1~{, ~A~}/1}"n(sort(delete-duplicates l)'<)))

(newlines not necessary)

Very brutal, but languages with native rationals are an invitation to that.

Ungolfed with comments:

                                        ; at each iteration:
(do ((l()()))                           ; - reset l to nil
    ((not (set 'n (read()()))))         ; - read a term (nil for eof)
                                        ;   assign it to n
                                        ;   stop looping if nil
  (dotimes (j n)                        ; for j in 0..n-1
    (dotimes (i (1+ j))                 ;   for i in 0..j
      (push (/ (1+ i) (1+ j)) l)))      ;     prepend i+1/j+1 to l
  (format t "~&F~D = {0/1~{, ~A~}/1}"   ; on a new line, including 0/1,
                                        ; forcing the format for 1
          n                             ; print sequence index, and
          (sort                         ; sorted sequence of
           (delete-duplicates l)        ;   unique fractions
           '<)))                        ; (in ascending order)
\$\endgroup\$
3
\$\begingroup\$

Python, 186 Chars

import sys
p=sys.stdout.write
while 1:
 a=0;b=c=x=1;d=y=N=input();p("F%d = {%d/%d, %d/%d"%(d,a,b,c,d))
 while y-1:x=(b+N)/d*c-a;y=(b+N)/d*d-b;p(", %d/%d"%(x,y));a=c;c=x;b=d;d=y
 p("}\n")
\$\endgroup\$
  • \$\begingroup\$ +1,but are you sure this will be fast for 10^6 number of inputs? \$\endgroup\$ – Quixotic Mar 26 '11 at 15:11
  • \$\begingroup\$ @Debanjan No. It would be really slow for 10^6 inputs. It is linear in complexity (in terms of the number of terms), though. \$\endgroup\$ – fR0DDY Mar 26 '11 at 15:27
2
\$\begingroup\$

J, 156 135 117 112

d=:3 :0
wd;'F';(":y);' = {';(}.,(', ';2|.'/';|.)"1(<@":)"0(2)x:/:~~.,(-.@>*%)"0/~i.x:>:y),<'}'
)
d@".;._2(1!:1)3

j602 or similar (wd). Input on stdin, output on stdout.

Still puzzling over how to golf the output code, which is 100 characters or so.

Edit: (156->135) Tacit->explicit for long monadic verb chains, less braindead list generation

Edit: (135->117) Found raze. Took me long enough. Switched string handling around.

Edit: (117->112) Slightly less braindead way to exclude fractions above 1. Unnecessary open.

\$\endgroup\$
  • \$\begingroup\$ Maybe you can omit one of your two x:s? \$\endgroup\$ – Eelvex Mar 30 '11 at 1:56
  • \$\begingroup\$ @Eelvex: The left one is 2&x:, e.g. split a rational number into numerator and denominator. \$\endgroup\$ – Jesse Millikan Mar 30 '11 at 3:24
  • \$\begingroup\$ oic. Pity ... :( \$\endgroup\$ – Eelvex Mar 30 '11 at 3:31
2
\$\begingroup\$

Golfscript (101)

~:c[,{){.}c(*}%.c/zip{+}*]zip{~{.@\%.}do;1=},{~<},{~\10c?*\/}${'/'*}%', '*'F'c`+' = {0/1, '+\', 1/1}'
\$\endgroup\$
2
\$\begingroup\$

Ruby, 110 108 102 97 94 92 91 89

#!ruby -lp
$_="F#$_ = {#{a=[];1.upto(eval$_){|d|a|=(0..d).map{|n|n.quo d}};a.sort*', '}}"
\$\endgroup\$
  • \$\begingroup\$ I think you should output "0/1" and "1/1" instead of "0" and "1" respectively. Also, does this only work for ruby 1.9? \$\endgroup\$ – Eelvex Mar 27 '11 at 16:51
  • 1
    \$\begingroup\$ @Eelvex: It does output 0/1 and 1/1 on my system. And yes, it requires 1.9 (because of the character literals). \$\endgroup\$ – Lowjacker Mar 27 '11 at 18:54
1
\$\begingroup\$

Haskell, 148

f n="F"++show n++" = {"++(intercalate", ".("0/1":).map(\(i:%d)->show i++"/"++show d).sort.nub$[i%d|d<-[1..n],i<-[1..d-1]])++"}"
main=interact$f.read
\$\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.