cp's OEIS Frontend

A185670 Number of pairs (x,y) with 1 <= x < y <= n with at least one common factor.

%I A185670 #56 Sep 04 2024 08:46:43
%S A185670 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,
%T A185670 114,122,137,137,158,158,173,185,202,212,235,235,254,268,291,291,320,
%U A185670 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
%N A185670 Number of pairs (x,y) with 1 <= x < y <= n with at least one common factor.
%H A185670 Reinhard Zumkeller, <a href="/A185670/b185670.txt">Table of n, a(n) for n = 1..1000</a>
%H A185670 Oliver Knill, <a href="https://arxiv.org/abs/1606.05971">Some experiments in number theory</a>, arXiv preprint arXiv:1606.05971 [math.NT], 2016.
%F A185670 a(p) = a(p-1) when p is prime.
%F A185670 a(n)-a(n-1) = A016035(n).
%F A185670 a(n) = n*(n-1)/2 + 1 - Sum_{i=1..n} phi(i).
%F A185670 a(n) = A100613(n) - A063985(n). - _Reinhard Zumkeller_, Jan 21 2013
%e A185670 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)}.
%p A185670 with(numtheory): A185670:=n->n*(n-1)/2 + 1 - add( phi(i), i=1..n): seq(A185670(n), n=1..100); # _Wesley Ivan Hurt_, Jan 30 2017
%t A185670 1 + Accumulate[ Table[n - EulerPhi[n] - 1, {n, 1, 75}]] (* _Jean-François Alcover_, Jan 04 2013 *)
%o A185670 (Haskell)
%o A185670 a185670 n = length [(x,y) | x <- [1..n-1], y <- [x+1..n], gcd x y > 1]
%o A185670 -- _Reinhard Zumkeller_, Mar 02 2012
%o A185670 (Python)
%o A185670 from functools import lru_cache
%o A185670 @lru_cache(maxsize=None)
%o A185670 def A185670(n): # based on second formula in A018805
%o A185670     if n == 0:
%o A185670         return 0
%o A185670     c, j = 2, 2
%o A185670     k1 = n//j
%o A185670     while k1 > 1:
%o A185670         j2 = n//k1 + 1
%o A185670         c += (j2-j)*(k1*(k1-1)+1-2*A185670(k1))
%o A185670         j, k1 = j2, n//j2
%o A185670     return (c-j)//2 # _Chai Wah Wu_, Mar 24 2021
%o A185670 (PARI) a185670(n) = sum(i=2, n, sum(j=2, i-1, gcd(i,j)>1)) \\ _Hugo Pfoertner_, Sep 04 2024
%Y A185670 Cf. A016035, A063985, A100613.
%K A185670 nonn,easy,nice
%O A185670 1,6
%A A185670 _Olivier Gérard_, Feb 09 2011
%E A185670 Definition clarified by _Reinhard Zumkeller_, Mar 02 2012