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

1, 63, 6087, 608383, 60794971, 6079301507, 607927104783, 60792712854483, 6079271032731815, 607927102346016827, 60792710185772432731, 6079271018566772422279, 607927101854119608051819, 60792710185405797839054887, 6079271018540289787820715707, 607927101854027018957417670303

Offset

0,2

References

Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54. (See link below.)

Links

Table of n, a(n) for n=0..15.

Joachim von zur Gathen and Jürgen Gerhard, Extract from "3.4. (Non-)Uniqueness of the gcd" chapter, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54.

Hugo Pfoertner, Illustration of a(2)=6087.

Formula

Lim_{n->infinity} a(n)/10^(2*n) = 6/Pi^2 = 1/zeta(2).

Prog

(Python)
import math
for n in range (0, 10):
     counter = 0
     for x in range (1, pow(10, n)+1):
        for y in range(1, pow(10, n)+1):
            if math.gcd(y, x) ==  1:
                counter += 1
     print(n, counter)
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def A018805(n):
  if n == 1: return 1
  return n*n - sum(A018805(n//j) for j in range(2, n//2+1)) - (n+1)//2
print([A018805(10**n) for n in range(8)]) # Michael S. Branicky, Mar 18 2021
(PARI) a342586(n)=my(s, m=10^n); forfactored(k=1, m, s+=eulerphi(k)); s*2-1 \\ Bruce Garner, Mar 29 2021
(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

Crossrefs

a(n) = 2*A064018(n) - 1. - Hugo Pfoertner, Mar 16 2021

a(n) = A018805(10^n). - Michel Marcus, Mar 16 2021

Cf. A000010, A059956 (6/Pi^2), A342632, A342841, A343193, A343282.

Related counts of k-tuples:

pairs: A018805, A342632, A342586;

triples: A071778, A342935, A342841;

quadruples: A082540, A343527, A343193;

5-tuples: A343282;

6-tuples: A343978, A344038. - N. J. A. Sloane, Jun 13 2021

Sequence in context: A238994 A364745 A069407 * A046190 A296782 A292782

Adjacent sequences: A342583 A342584 A342585 * A342587 A342588 A342589

Keyword

nonn

Author

Karl-Heinz Hofmann, Mar 16 2021

Extensions

a(10) from Michael S. Branicky, Mar 18 2021

More terms using A064018 from Hugo Pfoertner, Mar 18 2021

Edited by N. J. A. Sloane, Jun 13 2021

Status

approved