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

Author

Karl-Heinz Hofmann, Mar 16 2021

Keywords

• nonn

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

• 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.

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

Programs

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

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

Formula

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

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