Pairs with common factors
Generate the sequence where each term n is the count 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 term of the sequence.
- Find and display the one thousandth.
- Stretch
- Find and display the ten thousandth.
- See also
Raku
<lang perl6>use Prime::Factor; use Lingua::EN::Numbers;
my \𝜑 = 0, |(1..*).hyper.map: -> \t { t × [×] t.&prime-factors.unique.map: { 1 - 1/$_ } }
my @pairs-with-common-factors = (1..*).map: -> \n { n × (n - 1) / 2 + 1 - sum (1..n).map: { 𝜑[$_] } }
say "Number of pairs with common factors - first one hundred terms:\n"
~ @pairs-with-common-factors[^100].batch(10)».&comma».fmt("%6s").join("\n") ~ "\n";
for ^5 { say (my $i = 10 ** $_).&ordinal.tc.fmt("%15s term: ") ~ @pairs-with-common-factors[$i - 1].&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
Wren
Surprisingly quick for Wren with even the first million terms found in less than 11 seconds. Stretch goal may need extending. <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