13
\$\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!
Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ This will get loooong.....the output i mean. \$\endgroup\$
    – st0le
    Mar 26, 2011 at 8:49
  • \$\begingroup\$ Is N=0 permitted? \$\endgroup\$
    – Eelvex
    Mar 26, 2011 at 18:50
  • 4
    \$\begingroup\$ What's with the »(I)« in the title? \$\endgroup\$
    – Joey
    Mar 28, 2011 at 16:49
  • 2
    \$\begingroup\$ @Joey: Hmm. there's a Farey Sequence (II) now. Must be first edition! :-) \$\endgroup\$
    – mellamokb
    Mar 30, 2011 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, 2011 at 19:03

15 Answers 15

Reset to default
4
\$\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)
Improve this answer
\$\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, 2011 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, 2011 at 4:51
  • \$\begingroup\$ Ugh... I switched to j602 for wd and now I may need to switch back. :) \$\endgroup\$
    – Jesse Millikan
    Mar 29, 2011 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)
Improve this answer
\$\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")
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ +1,but are you sure this will be fast for 10^6 number of inputs? \$\endgroup\$
    – Quixotic
    Mar 26, 2011 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, 2011 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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Maybe you can omit one of your two x:s? \$\endgroup\$
    – Eelvex
    Mar 30, 2011 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, 2011 at 3:24
  • \$\begingroup\$ oic. Pity ... :( \$\endgroup\$
    – Eelvex
    Mar 30, 2011 at 3:31
2
\$\begingroup\$

Golfscript (101)

~:c[,{){.}c(*}%.c/zip{+}*]zip{~{.@\%.}do;1=},{~<},{~\10c?*\/}${'/'*}%', '*'F'c`+' = {0/1, '+\', 1/1}'
Improve this answer
\$\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*', '}}"
Improve this answer
\$\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, 2011 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, 2011 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
Improve this answer
\$\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
Improve this answer
\$\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}"
Improve this answer
\$\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.

Improve this answer
\$\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.

Improve this answer
\$\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

Improve this answer
\$\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

Improve this answer
\$\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, 2020 at 18:30
  • \$\begingroup\$ Kindly explain what you mean by "specific formatting and handling multiple queries". \$\endgroup\$
    – DavidC
    Oct 31, 2020 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, 2020 at 16:50
  • 1
    \$\begingroup\$ @xigoi, I think I've now addressed your comments. Thanks. \$\endgroup\$
    – DavidC
    Oct 31, 2020 at 18:03
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ "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}. \$\endgroup\$
    – Kevin Cruijssen
    Oct 3, 2022 at 11:36
  • 1
    \$\begingroup\$ Thanks, @KevinCruijssen. Stupid old challenges and their stupid & unnecessarily strict I/O requirements! \$\endgroup\$
    – Shaggy
    Oct 3, 2022 at 11:48
  • \$\begingroup\$ Ikr.. :/ Ah well, you're still the shortest. ;p Group-and-sort by is way too long in 05AB1E (2 separated builtins).. \$\endgroup\$
    – Kevin Cruijssen
    Oct 3, 2022 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.