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

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

Offset: 1

Author

Olivier Gérard, Feb 09 2011

Keywords

• nonn
• easy
• nice

Examples

			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)}.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
• Oliver Knill, Some experiments in number theory, arXiv preprint arXiv:1606.05971 [math.NT], 2016.

Crossrefs

Cf. A016035, A063985, A100613.

Programs

Haskell

a185670 n = length [(x,y) | x <- [1..n-1], y <- [x+1..n], gcd x y > 1]
-- Reinhard Zumkeller, Mar 02 2012

Maple

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

Mathematica

1 + Accumulate[ Table[n - EulerPhi[n] - 1, {n, 1, 75}]] (* Jean-François Alcover, Jan 04 2013 *)

PARI

a185670(n) = sum(i=2, n, sum(j=2, i-1, gcd(i,j)>1)) \\ Hugo Pfoertner, Sep 04 2024

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A185670(n): # based on second formula in A018805
    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
    return (c-j)//2 # Chai Wah Wu, Mar 24 2021

Formula

a(p) = a(p-1) when p is prime.

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

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

a(n) = A100613(n) - A063985(n). - Reinhard Zumkeller, Jan 21 2013

Extensions

Definition clarified by Reinhard Zumkeller, Mar 02 2012