Fractions nobody needs (because they can be reduced to a simpler form)

Question

It happened in the 19th century. Georg was bored and started counting the rational numbers. Surprisingly, he discovered that there were no more of them than natural numbers. This insight made Georg famous. (OEIS A352911, only added in 2022!)

But was Georg right? He didn't even count half of the fractions! He left the others aside. The part that nobody needs because they can be reduced to a simpler form. There are a lot more of them! Or are there not? We have to check and recount this part of the fractions.

Challenge

Write a function that enumerates the pairs (i, j) of noncoprime positive integers sorted first by i + j then by i.

We write them one after the other, numerator, denominator, without a pair of brackets and without the '/' sign.

Rules

Standard I/O rules apply and no standard loopholes.

This is code-golf, so the shortest code in bytes wins.

Answer 1

JavaScript (ES6), 59 bytes

-13 thanks to @tsh!

Prints the sequence indefinitely.

for(a=b=c=1;;)a%c+b%c--||(c&&print(a-b+`
`+b),c=b=b-1||a++)

Try it online!

More readable output

Answer 2

05AB1E, 19 bytes

∞εL¨Ryδ‚ʒ¿≠}εηíÆR€,

Port of @Arnauld's JavaScript answer, so make sure to upvote that answer as well!
Also outputs the infinite sequence on separated newlines.

Try it online.
Try it online with more readable format.

Explanation:

∞          # Push an infinite positive list: [1,2,3,...]
 ε         # Map each value to:
  L        #  Convert it to a list in the range [1,value]
   ¨R      #  Remove the last item and reverse it: range (value,1]
      δ    #  Map over each inner number
     y ‚   #   Pair it with the current value
  ʒ        #  Filter this list of pairs by:
   ¿       #   Check the pair's GCD (Greatest Common Divisor)
    ≠      #   Check that this is NOT 1
  }ε       #  After the filter: map over each pair [b,a]:
    η      #   Get its prefixes: [[b],[b,a]]
     í     #   Reverse each: [[b],[a,b]]
      Æ    #   Reduce each by subtracting: [b,a-b]
       R   #   Reverse the pair: [a-b,b]
        €  #   Map over both values:
         , #    Output it with trailing newline

Answer 3

Jelly, 14 bytes

żṚṄ€g/Ḋ$¡€ṛŻ‘ß

A full program that prints the sequence values forever.

Try it online!

How?

żṚṄ€g/Ḋ$¡€ṛŻ‘ß - Main Link: no arguments (X = implicit integer zero)
 Ṛ             - reverse {X} (0 -> [0])
ż              - {zip X} with {that}
         €     - for each pair:
        ¡      -   if...
       $       -   ...condition: last two links as a monad - f(pair):
     /         -                   reduce by:
    g          -                     greatest common divisor
      Ḋ        -                   dequeue -> [2..that] (the first pass has pair [0,0] with GCD 0, so can't just decrement as -1 is truthy - but it saves a byte or two elsewhere)
  Ṅ€           -   ...then: print each on its own line
           Ż   - zero range (first pass -> [0]) / prefix with 0 (otherwise)
          ṛ    - get the right argument -> {that}
            ‘  - increment (vectorises)
             ß - call this link again with X set to {that}

Answer 4

APL(Dyalog Unicode), 29 28 bytes ^SBCS

-1 byte by replacing () with an ¨ on ,¨∘⌽⍨∘⍸

Prints the first n pairs.

{⍵↑⊃,⌿,¨∘⌽⍨∘⍸¨1≠∨∘⌽⍨¨⍳¨⍳⍵+9}

Try it on APLgolf!

Answer 5

Charcoal, 39 bytes

ＮθＷ‹Ｌυθ«→ＦΦ…²ⅈ⊙…²ⅈ¬∨﹪ⅈμ﹪κμ⊞⊞Ｏυκ⁻ⅈκ»Ｉ…υθ

Try it online! Link is to verbose version of code. Takes n as input and outputs the first n elements. Explanation:

Ｎθ

Input n.

Ｗ‹Ｌυθ«

Repeat until n elements have been found.

→

Increment i+j.

ＦΦ…²ⅈ⊙…²ⅈ¬∨﹪ⅈμ﹪κμ

Loop through all values of i from 2 to i+j exclusive, for each value looping again though the same range, checking to see whether both i and i+j are divisible by the same nontrivial factor.

⊞⊞Ｏυκ⁻ⅈκ

For those that have a common factor, push i and i+j-i=j to the list of found elements.

»Ｉ…υθ

Output the first n elements.