# 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. Mar 26, 2011 at 8:49
• Is N=0 permitted? Mar 26, 2011 at 18:50
• What's with the »(I)« in the title?
– Joey
Mar 28, 2011 at 16:49
• @Joey: Hmm. there's a Farey Sequence (II) now. Must be first edition! :-) Mar 30, 2011 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, 2011 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? Mar 29, 2011 at 4:33
• @Jesse: absolutely. I (almost) never use 'strings'. I just use the default linux-j-7.01 environment. Mar 29, 2011 at 4:51
• Ugh... I switched to j602 for wd and now I may need to switch back. :) Mar 29, 2011 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? Mar 26, 2011 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. Mar 26, 2011 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? Mar 30, 2011 at 1:56
• @Eelvex: The left one is 2&x:, e.g. split a rational number into numerator and denominator. Mar 30, 2011 at 3:24
• oic. Pity ... :( Mar 30, 2011 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? Mar 27, 2011 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). Mar 27, 2011 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. Oct 29, 2020 at 18:30
• Kindly explain what you mean by "specific formatting and handling multiple queries". Oct 31, 2020 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. Oct 31, 2020 at 16:50

# 05AB1E, 40 bytes

|εÝ2.Æ2Å1ª.¡/}€нΣ/}'/ý„, ýy"Fÿ = {ÿ}",


Try it online.

Explanation:

|                     # Get all input-lines as a list
ε                    # Map over each input-integer:
Ý                   #  Pop and push a list in the range [0,n]
2.Æ                #  Get all 2-element combinations of this list
2Å1ª            #  Append pair [1,1]
.¡                  #  Group the pairs by:
#   Pop and push both values separated to the stack
/                #   Divide them
}€                 #  After the group-by: map over each group
н                #   Only leave the first pair of each group
Σ  }            #  Then sort the pairs by:
/             #   Similar as above: dump and divide
'/ý                '#  Then join each inner pair with "/"-delimiter
„, ý             #  Join these strings with ", "-delimiter
y            #  Push the current map-integer
"Fÿ = {ÿ}"  #  Push this string, where the ÿ are automatically filled with
#  the integer and formatted list
, #  Pop and output it with trailing newline


# Japt-R, 18 38 bytes

Stupid old challenges and their stupid & unnecessarily strict I/O requirements costing me 20 bytes!

N£"F{X} = \{{Xõ c_ô+'/+ZÃü!xO mÎqSi,}}


Try it

N£"F{X} = \{{Xõ c_ô+'/+ZÃü!xO mÎqSi,}}
N                                          :Array of all inputs
£                                         :Map each X
"F   = \{                          }     :  Build a string
{X}                                    :  Interpolate X
{                               :  Interpolate
Xõ                             :    Range [1,X]
c                          :    Flat map by
_                         :    Passing each Z through the following function
ô                        :      Range [0,Z]
+'/+Z                   :      Append "/" followed by Z to each
Ã                  :    End map
ü                 :    Group & sort by
!xO              :      Evaluating each as JavaScript
m            :    Map
Î           :      First element
q          :    Join with
S         :      Space
i,       :      Prepend comma
}      :  End interpolation
:Implicit output joined with new lines

• "OK, what am I missing?" There are multiple inputs, separated by newlines from STDIN. And the STDOUT output format you see in the challenge description is mandatory, with the F# = {comma_and_space_separated_results}`. Oct 3, 2022 at 11:36
• Thanks, @KevinCruijssen. Stupid old challenges and their stupid & unnecessarily strict I/O requirements! Oct 3, 2022 at 11:48
• Ikr.. :/ Ah well, you're still the shortest. ;p Group-and-sort by is way too long in 05AB1E (2 separated builtins).. Oct 3, 2022 at 12:00