Code-Golf: Farey sequence (I)

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!
• This will get loooong.....the output i mean. – st0le Mar 26 '11 at 8:49
• Is N=0 permitted? – Eelvex Mar 26 '11 at 18:50
• What's with the »(I)« in the title? – Joey Mar 28 '11 at 16:49
• @Joey: Hmm. there's a Farey Sequence (II) now. Must be first edition! :-) – mellamokb Mar 30 '11 at 18:08
• @mellamokb: Well, that one's a code challenge, though, so no title clash in any case. But yes, that sort of answers my question. – Joey Mar 30 '11 at 19:03

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)
• I get |value error: rplc. Are you sure you didn't load 'strings' earlier in the session and forget about it? – Jesse Millikan Mar 29 '11 at 4:33
• @Jesse: absolutely. I (almost) never use 'strings'. I just use the default linux-j-7.01 environment. – Eelvex Mar 29 '11 at 4:51
• Ugh... I switched to j602 for wd and now I may need to switch back. :) – Jesse Millikan Mar 29 '11 at 5:04

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.

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

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")
• +1,but are you sure this will be fast for 10^6 number of inputs? – Quixotic Mar 26 '11 at 15:11
• @Debanjan No. It would be really slow for 10^6 inputs. It is linear in complexity (in terms of the number of terms), though. – fR0DDY Mar 26 '11 at 15:27

J, 156135117 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.

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

~:c[,{){.}c(*}%.c/zip{+}*]zip{~{.@\%.}do;1=},{~<},{~\10c?*\/}${'/'*}%', '*'F'c`+' = {0/1, '+\', 1/1}' Ruby, 11010810297949291 89 #!ruby -lp$_="F#$_ = {#{a=[];1.upto(eval$_){|d|a|=(0..d).map{|n|n.quo d}};a.sort*', '}}"
• 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? – Eelvex Mar 27 '11 at 16:51
• @Eelvex: It does output 0/1 and 1/1 on my system. And yes, it requires 1.9 (because of the character literals). – Lowjacker Mar 27 '11 at 18:54

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