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,6

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.

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

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

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 *)

Prog

(Haskell)
a185670 n = length [(x, y) | x <- [1..n-1], y <- [x+1..n], gcd x y > 1]
-- Reinhard Zumkeller, Mar 02 2012
(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
(PARI) a185670(n) = sum(i=2, n, sum(j=2, i-1, gcd(i, j)>1)) \\ Hugo Pfoertner, Sep 04 2024

Crossrefs

Cf. A016035, A063985, A100613.

Sequence in context: A198991 A371556 A214990 * A011981 A238131 A212532

Adjacent sequences: A185667 A185668 A185669 * A185671 A185672 A185673

Keyword

nonn,easy,nice

Author

Olivier Gérard, Feb 09 2011

Extensions

Definition clarified by Reinhard Zumkeller, Mar 02 2012

Status

approved