11
\$\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\$
6
  • \$\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

13 Answers 13

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\$
3
  • \$\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\$
2
  • \$\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\$
3
  • \$\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\$
2
  • \$\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
2
\$\begingroup\$

Haskell, 145 bytes

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]
m@main=readLn>>=putStrLn.f shows div>>m

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

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}"
\$\endgroup\$
1
\$\begingroup\$

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.

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

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.

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

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

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

Mathematica 13 78 bytes

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

Example

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

Farey sequence

\$\endgroup\$
4
  • \$\begingroup\$ It's nice that you have a builtin, but the spec asks for a specific formatting and handling multiple queries. \$\endgroup\$ – xigoi Oct 29 '20 at 18:30
  • \$\begingroup\$ Kindly explain what you mean by "specific formatting and handling multiple queries". \$\endgroup\$ – DavidC Oct 31 '20 at 12:35
  • \$\begingroup\$ 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. \$\endgroup\$ – xigoi Oct 31 '20 at 16:50
  • 1
    \$\begingroup\$ @xigoi, I think I've now addressed your comments. Thanks. \$\endgroup\$ – DavidC Oct 31 '20 at 18:03

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.