login
A342586
a(n) is the number of pairs (x,y) with 1 <= x, y <= 10^n and gcd(x,y)=1.
9
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
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
Related counts of k-tuples:
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
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