|
%I #51 Mar 09 2022 00:21:07
%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.
%C a(p) = a(p-1) when p is prime.
%C The successive differences a(n)-a(n-1) are given by A016035(n)
%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(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
%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
|
