Pairs with common factors

Pairs with common factors is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

Factor

Works with: Factor version 0.99 2022-04-03

<lang factor>USING: formatting grouping io kernel math math.functions math.primes.factors prettyprint ranges sequences tools.memory.private ;

totient-sum ( n -- sum )

   [1..b] [ totient ] map-sum ;

a ( n -- a(n) )

   dup [ 1 - * 2 / ] keep totient-sum - ;

"Number of pairs with common factors - first 100 terms:" print 100 [1..b] [ a commas ] map 10 group simple-table. nl

7 <iota> [ dup 10^ a commas "Term #1e%d: %s\n" printf ] each</lang>

Output:

Number of pairs with common factors - first 100 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

Term #1e0: 0
Term #1e1: 14
Term #1e2: 1,907
Term #1e3: 195,309
Term #1e4: 19,597,515
Term #1e5: 1,960,299,247
Term #1e6: 196,035,947,609

Raku

<lang perl6>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 }</lang>

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

Wren

Library: Wren-math

Library: Wren-fmt

<lang ecmascript>import "./math" for Int import "./fmt" for Fmt

var totient = Fn.new { |n|

   var tot = n
   var i = 2
   while (i*i <= n) {
       if (n%i == 0) {
           while(n%i == 0) n = (n/i).floor
           tot = tot - (tot/i).floor
       }
       if (i == 2) i = 1
       i = i + 2
   }
   if (n > 1) tot = tot - (tot/n).floor
   return tot

}

var max = 1e6 var a = List.filled(max, 0) var sumPhi = 0 for (n in 1..max) {

   sumPhi = sumPhi + totient.call(n)
   if (Int.isPrime(n)) {
       a[n-1] = a[n-2]
   } else {
       a[n-1] = n * (n - 1) / 2 + 1 - sumPhi
   }

}

System.print("Number of pairs with common factors - first one hundred terms:") Fmt.tprint("$,5d ", a[0..99], 10) System.print() var limits = [1, 10, 1e2, 1e3, 1e4, 1e5, 1e6] for (limit in limits) {

   Fmt.print("The $,r term: $,d", limit, a[limit-1])

}</lang>

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  

The 1st term: 0
The 10th term: 14
The 100th term: 1,907
The 1,000th term: 195,309
The 10,000th term: 19,597,515
The 100,000th term: 1,960,299,247
The 1,000,000th term: 196,035,947,609