|
|
A185670
|
|
Number of pairs (x,y) with 1 <= x < y <= n with at least one common factor.
|
|
4
|
|
|
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, 1006, 1040
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,6
|
|
COMMENTS
|
a(p) = a(p-1) when p is prime.
The successive differences a(n)-a(n-1) are given by A016035(n)
|
|
LINKS
|
|
|
FORMULA
|
a(n) = n*(n-1)/2 + 1 - Sum_{i=1..n} phi(i).
|
|
EXAMPLE
|
For n=9, the a(9)=9 pairs are {(2,4),(2,6),(2,8),(3,6),(3,9),(4,6),(4,8),(6,8),(6,9)}.
|
|
MAPLE
|
|
|
MATHEMATICA
|
|
|
PROG
|
(Haskell)
a185670 n = length [(x, y) | x <- [1..n-1], y <- [x+1..n], gcd x y > 1]
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
if n == 0:
return 0
c, j = 2, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*(k1*(k1-1)+1-2*A185670(k1))
j, k1 = j2, n//j2
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|