user
Generate the sequence where each term **n** is the count of the pairs **(x,y)** with **1 < x < y <= n**, that have at least one common prime factor.

For instance, when **n** = 9, examine the pairs:

```
   (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9)
   (3,4) (3,5) (3,6) (3,7) (3,8) (3,9)
   (4,5) (4,6) (4,7) (4,8) (4,9)
   (5,6) (5,7) (5,8) (5,9)
   (6,7) (6,8) (6,9)
   (7,8) (7,9)
   (8,9)

```

Find all of the pairs that have at least one common prime factor:

```
   (2,4) (2,6) (2,8) (3,6) (3,9) (4,6) (4,8) (6,8) (6,9)

```

and count them:

```
   a(9) = 9

```

Terms may be found directly using the formula:

```
   a(n) = n × (n-1) / 2 + 1 - 𝚺{i=1..n} 𝚽(i)

```

where 𝚽() is Phi; the Euler totient function.

For the term **a(p)**, if **p** is prime, then **a(p)** is equal to the previous term.

Task

* Find and display the first one hundred terms of the sequence.
* Find and display the one thousandth.

Stretch

* Find and display the ten thousandth, one hundred thousandth, one millionth.

See also

* OEIS:A185670 - Number of pairs (x,y) with 1 <= x < y <= n with at least one common factor * Task: Totient function
assistant
```
use Prime::Factor;
use Lingua::EN::Numbers;

my \𝜑 = 0, |(1..*).hyper.map: -> \t { t × [×] t.&prime-factors.unique.map: { 1 - 1/$_ } }

sub pair-count (\n) {  n × (n - 1) / 2 + 1 - sum 𝜑[1..n] }

say "Number of pairs with common factors - first one hundred terms:\n"
    ~ (1..100).map(&pair-count).batch(10)».&comma».fmt("%6s").join("\n") ~ "\n";

for ^7 { say (my $i = 10 ** $_).&ordinal.tc.fmt("%22s term: ") ~ $i.&pair-count.&comma }

```

Output:

```
Number of pairs with common factors - first one hundred terms:
     0      0      0      1      1      4      4      7      9     14
    14     21     21     28     34     41     41     52     52     63
    71     82     82     97    101    114    122    137    137    158
   158    173    185    202    212    235    235    254    268    291
   291    320    320    343    363    386    386    417    423    452
   470    497    497    532    546    577    597    626    626    669
   669    700    726    757    773    818    818    853    877    922
   922    969    969  1,006  1,040  1,079  1,095  1,148  1,148  1,195
 1,221  1,262  1,262  1,321  1,341  1,384  1,414  1,461  1,461  1,526
 1,544  1,591  1,623  1,670  1,692  1,755  1,755  1,810  1,848  1,907

                 First term: 0
                 Tenth term: 14
         One hundredth term: 1,907
        One thousandth term: 195,309
        Ten thousandth term: 19,597,515
One hundred thousandth term: 1,960,299,247
         One millionth term: 196,035,947,609
```