cp's OEIS Frontend

A342586 a(n) is the number of pairs (x,y) with 1 <= x, y <= 10^n and gcd(x,y)=1.

%I A342586 #98 Jun 13 2021 13:33:32
%S A342586 1,63,6087,608383,60794971,6079301507,607927104783,60792712854483,
%T A342586 6079271032731815,607927102346016827,60792710185772432731,
%U A342586 6079271018566772422279,607927101854119608051819,60792710185405797839054887,6079271018540289787820715707,607927101854027018957417670303
%N A342586 a(n) is the number of pairs (x,y) with 1 <= x, y <= 10^n and gcd(x,y)=1.
%D A342586 Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54. (See link below.)
%H A342586 Joachim von zur Gathen and Jürgen Gerhard, <a href="/A342586/a342586_1.pdf">Extract from "3.4. (Non-)Uniqueness of the gcd" chapter</a>, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54.
%H A342586 Hugo Pfoertner, <a href="/A342586/a342586.pdf">Illustration of a(2)=6087</a>.
%F A342586 Lim_{n->infinity} a(n)/10^(2*n) = 6/Pi^2 = 1/zeta(2).
%o A342586 (Python)
%o A342586 import math
%o A342586 for n in range (0,10):
%o A342586      counter = 0
%o A342586      for x in range (1, pow(10,n)+1):
%o A342586         for y in range(1, pow(10,n)+1):
%o A342586             if math.gcd(y,x) ==  1:
%o A342586                 counter += 1
%o A342586      print(n, counter)
%o A342586 (Python)
%o A342586 from functools import lru_cache
%o A342586 @lru_cache(maxsize=None)
%o A342586 def A018805(n):
%o A342586   if n == 1: return 1
%o A342586   return n*n - sum(A018805(n//j) for j in range(2, n//2+1)) - (n+1)//2
%o A342586 print([A018805(10**n) for n in range(8)]) # _Michael S. Branicky_, Mar 18 2021
%o A342586 (PARI) a342586(n)=my(s, m=10^n); forfactored(k=1,m,s+=eulerphi(k)); s*2-1 \\ _Bruce Garner_, Mar 29 2021
%o A342586 (PARI) a342586(n)=my(s, m=10^n); forsquarefree(k=1,m,s+=moebius(k)*(m\k[1])^2); s \\ _Bruce Garner_, Mar 29 2021
%Y A342586 a(n) = 2*A064018(n) - 1. - _Hugo Pfoertner_, Mar 16 2021
%Y A342586 a(n) = A018805(10^n). - _Michel Marcus_, Mar 16 2021
%Y A342586 Cf. A000010, A059956 (6/Pi^2), A342632, A342841, A343193, A343282.
%Y A342586 Related counts of k-tuples:
%Y A342586 pairs: A018805, A342632, A342586;
%Y A342586 triples: A071778, A342935, A342841;
%Y A342586 quadruples: A082540, A343527, A343193;
%Y A342586 5-tuples: A343282;
%Y A342586 6-tuples: A343978, A344038. - _N. J. A. Sloane_, Jun 13 2021
%K A342586 nonn
%O A342586 0,2
%A A342586 _Karl-Heinz Hofmann_, Mar 16 2021
%E A342586 a(10) from _Michael S. Branicky_, Mar 18 2021
%E A342586 More terms using A064018 from _Hugo Pfoertner_, Mar 18 2021
%E A342586 Edited by _N. J. A. Sloane_, Jun 13 2021