# 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|p<-product[1..n]='F':n!" = {"++unwords[i%g!"/"++p%g![",}"!!(i%p)]|i<-[0..p],g<-[gcd i p],p<=n*g]


Try it online!

This reduces all of $$\\left\{\frac{0}{n!}, \frac{1}{n!}, \dots, \frac{n!}{n!}\right\}\$$ and selects the ones with denominator $$\\leq n\$$.

(The byte count went up a little again because I noticed the problem asks to handle multiple lines of input.)

The other Haskell answer is missing some imports and is missing 1/1 in the output. It also doesn't take multiple lines of input. When fixed, it comes out to 188 bytes:

import GHC.Real
import Data.List
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]])++"}" m@main=readLn>>=putStrLn.f>>m  # 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 # Husk, 55 bytes mλ:'F+s¹+" = "σ"1]""1/1}"σ"[0""{0/1"sOutfεmF/π2ŀ→)fImi¶  Try it online! It was interesting messing with strings in Husk. This gives the exact required output for the given test case. There's a strange husk-ism in the mi¶ function that gives intermediate 0's in the output. Hence, those are filtered out. Here's an explanation from Zgarb. ## Explanation mλ:'F+s¹+" = "σ"1]""1/1}"σ"[0""{0/1"sOutfεmF/π2ŀ→)fImi¶ ¶ split input on newlines mi map to integers fI filter out zeroes mλ ) map each number through this function: ŀ→ range (0..n) π2 all possible pairs mF/ map each to it's fraction fε keep elements ≤ 1 t remove first value (Any) Ou uniquify, sort ascending s convert to string σ"[0""{0/1" change 0 → 0/1 σ"1]""1/1}" change 1 → 1/1 +" = " add an equal sign :'F+s¹ prepend "F{N}"  # Jelly, 44 bytes ƓµŻœċ2g/’$Ðḟ÷/Þj€”/j⁾, ,⁸Ø<,y“F> = {<}”Ṅ
Ç1¿


Try it online!

Could probably be improved if someone told me how to read and write multiline input properly in Jelly. I couldn't find any documentation on it, so I just have a while(true) loop that errors out when it reaches EOF.

# CJam, 73 bytes

'Fqi:T" = {"[[T1]Y,{_'\*',+\W%@_@_2\$+2%Ta.+:/@f*\.-_1=T)<@W%\}g'\*\;]S*'}


Try it online!

Uses an algorithm to generate the terms in traditional order. A lot of maps and vector functions were used here. If anyone wants a write-up then I'll make one, unless I can figure out a better algorithm.

# Python 3, 89 bytes

lambda n:[*zip(*sorted({j/i:(j,i)for i in range(n,0,-1)for j in range(i+1)}.items()))][1]


Try it online!

Basically generating all possible fractions and then using a dictionary comprehension to filter out the duplicates.

# Python 3, 142 bytes

while 1:n=input();print('F%s = {'%n+', '.join([*zip(*sorted({j/i:f'{j}/{i}'for i in range(int(n),0,-1)for j in range(i+1)}.items()))][1])+'}')


Try it online!

Abiding by all of the I/O requirements

# Mathematica 13 78 bytes

Column[Row@{"F",#," = ",FareySequence[ToExpression@#]}&/@StringSplit[#,"\n"]]&


Example

Column[Row@{#," = ",FareySequence[ToExpression@#]}&/@StringSplit[#,"\n"]]&["5\n4\n3"]
`

• It's nice that you have a builtin, but the spec asks for a specific formatting and handling multiple queries. – xigoi Oct 29 '20 at 18:30
• Kindly explain what you mean by "specific formatting and handling multiple queries". – DavidC Oct 31 '20 at 12:35
• Per the specification, you have to find Farey sequences for multiple integers separated by newlines and output them in the format "F3 = {0/1, 1/3, 1/2, 2/3, 1/1}". Your code takes only one integer and has a different output format. – xigoi Oct 31 '20 at 16:50
• @xigoi, I think I've now addressed your comments. Thanks. – DavidC Oct 31 '20 at 18:03