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

%I #56 Sep 04 2024 08:46:43

%S 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 114,122,137,137,158,158,173,185,202,212,235,235,254,268,291,291,320,

%U 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 Number of pairs (x,y) with 1 <= x < y <= n with at least one common factor.

%H Reinhard Zumkeller, <a href="/A185670/b185670.txt">Table of n, a(n) for n = 1..1000</a>

%H 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 a(p) = a(p-1) when p is prime.

%F a(n)-a(n-1) = A016035(n).

%F a(n) = n*(n-1)/2 + 1 - Sum_{i=1..n} phi(i).

%F a(n) = A100613(n) - A063985(n). - _Reinhard Zumkeller_, Jan 21 2013

%e 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 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 1 + Accumulate[ Table[n - EulerPhi[n] - 1, {n, 1, 75}]] (* _Jean-François Alcover_, Jan 04 2013 *)

%o (Haskell)

%o a185670 n = length [(x,y) | x <- [1..n-1], y <- [x+1..n], gcd x y > 1]

%o -- _Reinhard Zumkeller_, Mar 02 2012

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A185670(n): # based on second formula in A018805

%o if n == 0:

%o return 0

%o c, j = 2, 2

%o k1 = n//j

%o while k1 > 1:

%o j2 = n//k1 + 1

%o c += (j2-j)*(k1*(k1-1)+1-2*A185670(k1))

%o j, k1 = j2, n//j2

%o return (c-j)//2 # _Chai Wah Wu_, Mar 24 2021

%o (PARI) a185670(n) = sum(i=2, n, sum(j=2, i-1, gcd(i,j)>1)) \\ _Hugo Pfoertner_, Sep 04 2024

%Y Cf. A016035, A063985, A100613.

%K nonn,easy,nice

%O 1,6

%A _Olivier Gérard_, Feb 09 2011

%E Definition clarified by _Reinhard Zumkeller_, Mar 02 2012