Unique fraction generator

Given a positive integer N, generate all unique fractions you can create using integers from 1 to N and follow the rules below:

• Use numbers 1 through N only (no zero).
• Create fractions like numerator/denominator.
• List them in ascending order (from smallest to largest).
• If two fractions have the same value (like 1/2 and 2/4) only show the one with the smallest numerator.

Examples

Example 1
Input: $int = 3
Output: 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1

Example 2
Input: $int = 4
Output: 1/4, 1/3, 1/2, 2/3, 3/4, 1/1, 4/3, 3/2, 2/1, 3/1,
   4/1

Example 3
Input: $int = 1
Output: 1/1

Example 4
Input: $int = 6
Output: 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4,
        4/5, 5/6, 1/1, 6/5, 5/4, 4/3, 3/2, 5/3, 2/1,
        5/2, 3/1, 4/1, 5/1, 6/1

Example 5
Input: $int = 5
Output: 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1,
        5/4, 4/3, 3/2, 5/3, 2/1, 5/2, 3/1, 4/1, 5/1

Analysis

This is another challenge which is solved more or less by translating the description into Perl.

The fractions are generated by iterating over numerator and denominator from 1 to N. I save each decimal value in a hash key, unless it already exists (which willl be with a smaller numerator), and use the textual fraction as the hash value.

It's then just a case of sorting by the hash key.

A thorough explanation of the solution (both tasks) is provided in the post. The Perl code included is easy to read and closely adheres to the descriptions of each problem. Furthermore, the code has been written such that it handles 'non-convergence' where applicable, with clear and logical outputs as well as analyses of each step helping the reader to learn about the algorithms and their correctness.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2026-01-19
use utf8;     # Week 357 - task 2 - Unique fraction generator
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

unique_fraction_generator(3);
unique_fraction_generator(4);
unique_fraction_generator(1);
unique_fraction_generator(6);
unique_fraction_generator(5);
unique_fraction_generator(10);

sub unique_fraction_generator {
    
    my ($n, $i, $j, $q, %quotient, $result);
    
    # initialise
    $n = $_[0];
    
    # generate fractions
    for $i (1 .. $n) {
        for $j (1 .. $n) {
            $q = $i / $j;
            
            # save result unless an equal earlier one
            $quotient{$q} .= qq[$i/$j] unless $quotient{$q};
        }
    }
    
    # sort them by value
    $result = '';
    for $q (sort {$a <=> $b} keys %quotient) {
        $result .= qq[$quotient{$q}, ];
    }
    
    say qq[\nInput:  $n];
    say qq[Output: ] . substr($result, 0, -2);
}

12 lines of code

Output from script

Input:  3
Output: 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1

Input:  4
Output: 1/4, 1/3, 1/2, 2/3, 3/4, 1/1, 4/3, 3/2, 2/1, 3/1,
   4/1

Input:  1
Output: 1/1

Input:  6
Output: 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5,
   5/6, 1/1, 6/5, 5/4, 4/3, 3/2, 5/3, 2/1, 5/2, 3/1, 4/1,
   5/1, 6/1

Input:  5
Output: 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1,
   5/4, 4/3, 3/2, 5/3, 2/1, 5/2, 3/1, 4/1, 5/1

Input:  10
Output: 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7,
   3/10, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8,
   2/3, 7/10, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9,
   9/10, 1/1, 10/9, 9/8, 8/7, 7/6, 6/5, 5/4, 9/7, 4/3,
   7/5, 10/7, 3/2, 8/5, 5/3, 7/4, 9/5, 2/1, 9/4, 7/3, 5/2,
   8/3, 3/1, 10/3, 7/2, 4/1, 9/2, 5/1, 6/1, 7/1, 8/1, 9/1,
   10/1