The nth numerator

Question

You can create a list of all rationals 0 < r ≤ 1 by listing them ordered first by denominator and then by numerator:

1  1  1  2  1  3  1  2  3  4  1  5  1  2  3  4  5
-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
1  2  3  3  4  4  5  5  5  5  6  6  7  7  7  7  7

Note that we skip any rational number that already occurred before. E.g. 2/4 is skipped because we already listed 1/2.

In this challenge we're interested in the numerators only. Looking at the list above, write a function or program taking a positive integer n that returns the nth numerator from the list.

---

Testcases:

1 -> 1
2 -> 1
3 -> 1
4 -> 2
5 -> 1
6 -> 3
7 -> 1
8 -> 2
9 -> 3
50 -> 4
80 -> 15

Answer 1

MATL, 17 13 bytes

:tt!/XR6#uG))

Try it online! Or verify all test cases.

Input size may be limited by floating point accuracy. All test cases give the correct result.

Explanation

This generates all fractions k/m with k, m in [1 2 ...n], as an n×n matrix. The row indicates the numerator and the column indicates the denominator. Actually the matrix entry contains the inverse fraction m/k, instead of k/m, but this is irrelevant and can be ignored in the rest of the explanation.

Matrix entries are implicitly considered to be sorted in column-major order. In this case this corresponds to the required order: denominator, then numerator.

Three types of entries need to be disregarded from this matrix:

1. Entries k/m, k>m, that have the same value as a previous entry (for example, 2/4 is disregarded because it is the same as 1/2)
2. Entries k/k, k>1. Entries that have a numerator exceeding the denominator
3. Entries k/m, k<m (these are not part of the problem).

Disregarding entries is done with a unique function, which stably removes duplicate values and outputs the indices of the surviving entries. With this, entries of type 1 above are automatically removed. To deal with types 2 and 3, the matrix entries at the diagonal and below are set to 0. This way, all zero entries will be removed except the first (corresponding to the valid fraction 1/1).

Consider input 4 as an example.

:     % Input n implicitly. Push range [1 2 ...n]
      % STACK: [1 2 3 4]
t     % Duplicate
      % STACK: [1 2 3 4], [1 2 3 4]
t!    % Duplicate and transpose
      % STACK: [1 2 3 4], [1 2 3 4], [1; 2; 3; 4]
/     % Divide element-wise with broadcast: gives matrix with all pairs
      % STACK: [1 2 3 4], [1       2       3       4;
                           0.5000  1       1.5000  2;
                           0.3333  0.6667  1       1.3333;
                           0.2500  0.5000  0.7500  1     ]
XR    % Upper triangular part above the diagonal. This sets to 0 all entries
      % corresponding to fractions that equal or exceed 1. (Since the matrix
      % actually contains the inverse fractions, nonzero entries will contain
      % values greater than 1)
      % STACK: [1 2 3 4], [0       2       3       4;
                           0       0       1.5000  2;
                           0       0       0       1.3333;
                           0       0       0       0     ]
6#u   % Indices of first appearance of unique elements
      % STACK: [1 2 3 4], [1; 5; 9; 10; 13; 15]
G     % Push input n again
      % STACK: [1 2 3 4], [1; 5; 9; 10; 13; 15], 4
)     % Index: get the n-th entry from the array of indices of unique elements
      % STACK: [1 2 3 4], 10
)     % Index (modular): get the corresponding real part. Display implicitly
      % STACK: 2

Answer 2

Jelly, 11 9 bytes

gRỊTµ€Fị@

Try it online! or verify all test cases.

How it works

gRỊTµ€Fị@  Main link. Argument: n

    µ€     Map the monadic chain to the left over [1, ..., n]; for each k:
 R           Range; yield [1, ..., k].
g            Compute the GCD of k and each j in [1, ..., k].
  Ị          Insignificant; yield 1 for 1; 0 for 2, ..., k.
   T         Truth; yield all indices of 1's, i.e., all coprimes with k.
      F      Flatten the resulting 2D array.
       ị@    At-index swapped; return the n-th element.

Answer 3

Wolfram Language (Mathematica), 53 49 bytes

(Join@@Array[Pick[r=Range@#,r~GCD~#,1]&,#])[[#]]&

Try it online!

Answer 4

Haskell, 40 bytes

((0:[n|d<-[1..],n<-[1..d],gcd n d<2])!!)

An anonymous function. Pretty straightforward: uses a list comprehension to generate an infinite list, looping over all numerators n and relatively prime denominators d. To convert zero-index to one-indexed, we prepend a 0, which takes 4 bytes.

Answer 5

Pyth, 13 bytes

@smfq1idTUhdh

Try it online. Test suite.

Answer 6

Pyth, 11 bytes

@sm.mibdhdS

Try it online: Demonstration

Explanation:

@sm.mibdhdSQQ   implicit Qs at the end (Q = input number)
  m       SQ    map each denominator d from [1, 2, ..., Q] to:
   .m   hd        select the numerators b from [0, 1, ..., d]
     ibd             for which gcd(b, d) == 1 (which is the smallest possible gcd)
                  this gives [0, 1] for d=1, [1] for d=2, [1,2] for d=3, ...
 s              combine all lists to a big one
@           Q   print the Qth element

Answer 7

Actually, 15 bytes

This answer is based on Dennis' Jelly answer. I use HN at the end to avoid issues with 0-indexing and needing to decrement n and swap at the beginning or end. H gets the first n members of the list of numerators that results and N gets the last member of that selection, i.e. the nth numerator, all without fiddling about with stack operations. Golfing suggestions welcome. Try it online!

;R`;r;)♀┤░`MΣHN

Ungolfing

          Implicit input n.
;         Duplicate n. Leave one n on the stack for getting the nth numerator at the end.
R`...`M   Map the following function over the range [1..n]. Variable m.
  ;         Duplicate m. Leave one m on the stack for checking coprimality later.
  r         Push the range [0...m].
  ;)        Move a duplicate of range [0...m] to BOS.
  ♀┤        Push a list of 0's and 1's where a 1 denotes a number coprime to m (a numerator),
             and 0 denotes a fraction we have counted before.
  ░         Filter the second list (range [0...m]) 
             by the truthy values in the first list (our coprime check).
Σ         Sum all of the lists in the result into one list.
H         Push result[:n] using the duplicate of n from the beginning of the program.
N         Push result[:n][:-1], which is the same as result[n-1], our nth numerator.
          Implicit return.

Answer 8

Python, 111 110 bytes

from fractions import*
def g(n):
 x,y=1,1
 while n>1:
  x+=1
  if x>y:x,y=1,y+1
  if gcd(x,y)<2:n-=1
 return x

The fraction is represented with x/y. The argument n is decremented when a new fitting fraction is found (the gcd from fractions checks can the fraction be reduced). In each iteration of the loop, x is incremented, then, if x>=y, a new series of fractions with y+1 is started, > because of the "special case" (x,y)=(2,1), golfed to x>y.

I am sure this can be golfed more, but I am missing where I could improve it. Found it.

Link to code and test cases

Answer 9

JavaScript (ES6), 95 bytes

n=>[...Array(n*n).keys()].filter(i=>i%n<=i/n&g(i%n+1,i/n+1|0)<2,g=(a,b)=>b?g(b,a%b):a)[n-1]%n+1

Works by generating all n² fractions with numerators and denominators from 1 to n and filtering out those greater than 1 or previously seen, then taking the nth.

Answer 10

Perl, 82 + 2 (-pl flag) = 84 bytes

perl -ple '{{$d>$n?($n++,(grep!($n%$_||$d%$_),2..$d)&&redo):($n=1,$d++)}++$i!=$_&&redo;$_=$n}'

Ungolfed:

while (<>) {  # -p flag
    chomp();  # -l flag

    my $i = 0;
    my $n = 0;
    my $d = 0;

    for (;;) {
        for (;;) {
            if ($d <= $n) {
                $n = 1;
                $d++;
                last;
            }
            else {
                $n++;
                last unless grep { !($n % $_) && !($d % $_) } 2 .. $d;
            }
        }
        if (++$i == $_) {
            $_ = $n;
            last;
        }
    }
}
continue {
    print($_, "\n");
}

Answer 11

JavaScript (ES6), 76

x=>eval("for(g=(a,b)=>b?g(b,a%b):a,d=n=0;x;g(n,d)-1||--x)n=++n>d?(++d,1):n")

Less golfed

x=>{
  g=(a,b) => b ? g(b,a%b) : a; // gcd
  for (d=n=0; x; )
  {
     ++n;
     if (n > d)
     {
        ++d;
        n=1;
     }
     if (g(n,d) == 1) // if the fraction is irreducible 
        --x;
  }
  return n
}

Test

f=
x=>eval("for(g=(a,b)=>b?g(b,a%b):a,d=n=0;x;g(n,d)-1||--x)n=++n>d?(d++,1):n")

;`1 -> 1
2 -> 1
3 -> 1
4 -> 2
5 -> 1
6 -> 3
7 -> 1
8 -> 2
9 -> 3
50 -> 4
80 -> 15`.split`\n`.forEach(
  r=>{
    var [a,k]=r.match(/\d+/g),r=f(a)
    console.log(r==k?'OK':'KO',a,r)
  }
)  

Answer 12

Clojure, 85 bytes

#(if(= 1 %)1(numerator(nth(distinct(for[i(range)j(range 1(inc i))](/ j i)))(dec %))))

Uses list comprehension to generate list of all rationals, then filters it to get only distinct ones. Takes nth item of the list and returns its numerator. Also separate condition is needed for the first element because Clojure isn't able to take numerator of an integer. (for whatever reason considering an integer to be not Rational – https://goo.gl/XETLo2)

See it online – https://ideone.com/8gNZEB