0
\$\begingroup\$

User inputs an integer. Print out proper fractions using all positive integers up to the user's input, in ascending order.

Rule 1: Eliminate equal fractions.

Rule 2: Fractions should be in their simplest form.

Rule 3: Use "/" as a fraction symbol and next line (\n or \r as convenient) as a separator between fractions.

Winning Criteria: The shortest code wins.

For example:

4:

1/4
1/3
1/2
2/3
3/4
1

6:

1/6
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
5/6
1
\$\endgroup\$
16
  • 8
    \$\begingroup\$ i would recommend relaxing or removing rule 3, this site values loose input/output constraints. outputting as a list of fractions isnt much different than outputting fractions one per each line, and it probably doesnt add much to the challenge to require a specific format \$\endgroup\$ Oct 1, 2022 at 17:05
  • 3
    \$\begingroup\$ wouldnt the example for 4 end with ...3/4, 1, 2, 3, 4? same idea for 6... Also, if you want to include numbers like 1 (which isnt a fraction) maybe change the wording from "fractions" to "rationals". Otherwise, it should probably end before 1 \$\endgroup\$ Oct 1, 2022 at 17:06
  • 4
    \$\begingroup\$ These are also called Farey sequences. \$\endgroup\$ Oct 1, 2022 at 18:19
  • 4
    \$\begingroup\$ I'm voting to close because this question because it doesn't have a winning criterion. And, please don't edit one in unless you're the question poster. \$\endgroup\$
    – xnor
    Oct 1, 2022 at 22:17
  • 3
    \$\begingroup\$ @graffe No, it's not. While most challenges on this site are code-golf, not all of them are, and that assumption cannot be made. It makes absolutely no sense to me why people are engaging in special pleading to give someone who clearly doesn't understand the rules and purpose of the site more reputation. \$\endgroup\$ Oct 2, 2022 at 17:25

8 Answers 8

3
\$\begingroup\$

Husk, 10 bytes

¶OfεuΣ´Ṫ/ḣ

Try it online!

          ḣ # 1..input
       ´    # argdup: use this range twice
        Ṫ   # to construct a table
         /  # of one element divided by the other
            # (Husk will automatically simplify the fractions);
      Σ     # now flatten the table to a list
     u      # and keep only the unique elements,
   f        # filter to keep only those
    ε       # with value at most 1,
  O         # sort in ascending order,
 ¶          # and split by newlines

(or, also 10 bytes: ¶uOṁṠM`/ḣḣ try it)

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 77 bytes

Based on the algorithm given in Wikipedia.

f=(d,a,b=(n=d,1),c=1)=>a^b?[a&&a+`/${b}
`]+f((k=(n+b)/d|0)*d-b,c,d,k*c-~~a):1

Try it online!

Commented

f = (             // f is a recursive function taking:
  d,              //   the input n and the parameters (a, b, c, d)
  a,              //   which are initially set to:
  b = (n = d, 1), //   (undefined, 1, 1, n)
  c = 1           //
) =>              //
a ^ b ?           // if a is not equal to b:
  [ a &&          //   append either a + '/' + b + '\n' if a is defined
    a + `/${b}\n` //   or just an empty string if a is undefined (which
  ] +             //   happens only for the first iteration)
  f(              //   append the result of a recursive call:
    (k = (n + b)  //     set k = floor((n + b) / d)
         / d | 0) //
    * d - b,      //     update d to k * d - b
    c,            //     update a to c
    d,            //     update b to d
    k * c - ~~a   //     update c to k * c - a
                  //     (with a coerced to 0 if undefined)
  )               //   end of recursive call
:                 // else:
  1               //   stop the recursion and append the final '1'
\$\endgroup\$
2
  • \$\begingroup\$ Super cool. What's happening with a=!(n=d)? I just can't figure out what's going on there and I'm not sure what to search. Is it declaring two parameters, a and n and setting the default value of a to true if... n and d are 0? \$\endgroup\$ Oct 2, 2022 at 0:38
  • 1
    \$\begingroup\$ @ErtySeidohl It sets n to the value of d, and then sets a to true if n is 0, or false otherwise. \$\endgroup\$
    – naffetS
    Oct 2, 2022 at 0:46
2
\$\begingroup\$

APL(Dyalog Unicode), 56 bytes SBCS

{↑↑'1',⍨(⊣,'/',⊢)⍥⍕/¨m[⍋÷/¨m←w/⍨≠÷/¨w←⊃⍵,.(¯1↓,¨)⍨,\⍵]}⍳

Try it on APLgolf!

\$\endgroup\$
2
\$\begingroup\$

Pyth, 28 bytes

j{mj\//Ri.*dd<oc.*N^SQ2sUQ)1

Try it online!

Explanation
j{mj\//Ri.*dd<oc.*N^SQ2sUQ)1 | Full code
-----------------------------+------------------------------------------------------------------------------------------
                   ^SQ2      | Generate all pairs of integers [1..input]
              oc.*N          | Sort by division
             <         sUQ   | Keep only the first <input>th triangular number of pairs (the next pair is always [1, 1])
  m   /Ri.*dd                | Divide each pair by its GCD
  mj\/                       | Join each pair by '/'
 {                           | Remove duplicates
j                         )  | Join all by '\n'
                             | Print (implicit)
                           1 | Print 1
\$\endgroup\$
2
\$\begingroup\$

Factor + math.matrices,  83 76  71 bytes

[ [1,b] 1 over n/v outer [ [ 1 min ] map ] gather natural-sort stack. ]

Attempt This Online!

How?

In Factor, division produces ratios that automatically reduce to simplified form, so that helps a lot.

  • [1,b] 1 over n/v outer If \$x\$ is the input, \$\Bigl[1\ldots x\Bigr]\otimes\Bigl[\frac{1}{1}\ldots\frac{1}{x}\Bigr]\$ (where \$\otimes\$ is the tensor/outer product).
  • [ [ 1 min ] map ] gather Get a list of the unique elements of the above matrix whose values are clamped to a maximum of 1.
  • natural-sort Sort into ascending order.
  • stack. Print each ratio to stdout with a newline.
\$\endgroup\$
2
\$\begingroup\$

Goruby, 77 bytes

Very direct port of the code from Wikipedia

-4 bytes thanks to Raztime

->n{a,b,d=0,c=1,n
dw{k=(n+b)/d
a,b,c,d=c,d,k*c-a,k*d-b
sa b<2?a:a*1r/b
n>=c}}

Attempt This Online!

Ruby, 85 bytes

->n{a,b,d=0,c=1,n
while n>=c
k=(n+b)/d
a,b,c,d=c,d,k*c-a,k*d-b
puts b<2?a:a*1r/b
end}

Attempt This Online!

\$\endgroup\$
4
  • \$\begingroup\$ I think you need n>=c for the case n=1. \$\endgroup\$
    – Arnauld
    Oct 1, 2022 at 22:58
  • \$\begingroup\$ @Arnauld Looks like you’re right, thanks. \$\endgroup\$
    – Jordan
    Oct 1, 2022 at 23:33
  • 1
    \$\begingroup\$ -4 using ruby's fractions \$\endgroup\$
    – Razetime
    Oct 2, 2022 at 9:56
  • \$\begingroup\$ @Razetime Thanks! I had tried that but used p instead of puts, which gives output formatted like (1/6). I didn't realize puts would give the right output! \$\endgroup\$
    – Jordan
    Oct 2, 2022 at 15:57
1
\$\begingroup\$

Python, 99 bytes

def f(n):
 a,b,c,d=0,1,1,n
 while~n+c:k=(n+b)//d;a,b,c,d=c,d,k*c-a,k*d-b;print([1,f"{a}/{b}"][b>1])

Attempt This Online!

Another port of the Farey sequence generation algorithm, though this one's a bit cheaty since the code on the Wikipedia article is given in Python.

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 10 bytes

¨Vv/fU~ṅs⁋

Try it Online!

¨Vv/fU~ṅs⁋
¨Vv/        # Create a division table from [1, input]
    fU      # Flatten and uniquify
      ~ṅ    # Keep only elements <= 1
        s   # Sort
         ⁋  # Join on newlines
\$\endgroup\$

Your Answer

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

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