cp's OEIS Frontend

A100613 Number of elements in the set {(x,y): 1 <= x,y <= n, gcd(x,y) > 1}.

%I A100613 #25 Mar 29 2024 09:14:23
%S A100613 0,1,2,5,6,13,14,21,26,37,38,53,54,69,82,97,98,121,122,145,162,185,
%T A100613 186,217,226,253,270,301,302,345,346,377,402,437,458,505,506,545,574,
%U A100613 621,622,681,682,729,770,817,818,881,894,953,990,1045,1046,1117,1146,1209
%N A100613 Number of elements in the set {(x,y): 1 <= x,y <= n, gcd(x,y) > 1}.
%H A100613 Reinhard Zumkeller, <a href="/A100613/b100613.txt">Table of n, a(n) for n = 1..1000</a>
%F A100613 a(n) = A000290(n) - A018805(n) = A185670(n) + A063985(n). - _Reinhard Zumkeller_, Jan 21 2013
%F A100613 a(n) = Sum_{k = 2..n} A242114(n,k). - _Reinhard Zumkeller_, May 04 2014
%F A100613 a(n) ~ kn^2, where k = 1 - 6/Pi^2 = 0.39207... (A229099). - _Charles R Greathouse IV_, Mar 29 2024
%t A100613 f[n_] := Table[ #^2 &[m], {m, 1, n + 1}] - FoldList[Plus, 1, 2 Array[EulerPhi, n, 2]] (* _Gregg K. Whisler_, Jun 25 2008 *)
%o A100613 (Haskell)
%o A100613 a100613 n = length [()| x <- [1..n], y <- [1..n], gcd x y > 1]
%o A100613 -- _Reinhard Zumkeller_, Jan 21 2013
%o A100613 (PARI) a(n) = sum(i=1, n, sum(j=1, n, gcd(i,j)>1)); \\ _Michel Marcus_, Jan 30 2017
%o A100613 (Python)
%o A100613 from functools import lru_cache
%o A100613 @lru_cache(maxsize=None)
%o A100613 def A100613(n): # based on second formula in A018805
%o A100613     if n == 0:
%o A100613         return 0
%o A100613     c, j = 1, 2
%o A100613     k1 = n//j
%o A100613     while k1 > 1:
%o A100613         j2 = n//k1 + 1
%o A100613         c += (j2-j)*(k1**2-A100613(k1))
%o A100613         j, k1 = j2, n//j2
%o A100613     return n+c-j # _Chai Wah Wu_, Mar 24 2021
%Y A100613 Cf. A018805, A000290, A185670, A063985, A242114, A229099.
%K A100613 nonn
%O A100613 1,3
%A A100613 Douglas Stones (dssto1(AT)student.monash.edu.au), Dec 02 2004