cp's OEIS Frontend

A342632 Number of ordered pairs (x, y) with gcd(x, y) = 1 and 1 <= {x, y} <= 2^n.

%I A342632 #46 Sep 04 2021 15:50:11
%S A342632 1,3,11,43,159,647,2519,10043,39895,159703,637927,2551171,10200039,
%T A342632 40803219,163198675,652774767,2611029851,10444211447,41776529287,
%U A342632 167106121619,668423198491,2673693100831,10694768891659,42779072149475,171116268699455,684465093334979,2737860308070095
%N A342632 Number of ordered pairs (x, y) with gcd(x, y) = 1 and 1 <= {x, y} <= 2^n.
%H A342632 Chai Wah Wu, <a href="/A342632/b342632.txt">Table of n, a(n) for n = 0..45</a>
%H A342632 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.
%F A342632 Lim_{n->infinity} a(n)/2^(2*n) = 6/Pi^2 = 1/zeta(2).
%e A342632 Only fractions with gcd(numerator, denominator) = 1 are counted. E.g.,
%e A342632   1/2 counts, but 2/4, 3/6, 4/8 ... do not, because they reduce to 1/2;
%e A342632   1/1 counts, but 2/2, 3/3, 4/4 ... do not, because they reduce to 1/1.
%e A342632 .
%e A342632 For n=0, the size of the grid is 1 X 1:
%e A342632 .
%e A342632     | 1
%e A342632   --+--
%e A342632   1 | o      Sum:  1
%e A342632 .
%e A342632 For n=1, the size of the grid is 2 X 2:
%e A342632 .
%e A342632     | 1 2
%e A342632   --+----
%e A342632   1 | o o          2
%e A342632   2 | o .          1
%e A342632                   --
%e A342632              Sum:  3
%e A342632 .
%e A342632 For n=2, the size of the grid is 4 X 4:
%e A342632 .
%e A342632     | 1 2 3 4
%e A342632   --+--------
%e A342632   1 | o o o o      4
%e A342632   2 | o . o .      2
%e A342632   3 | o o . o      3
%e A342632   4 | o . o .      2
%e A342632                   --
%e A342632              Sum: 11
%e A342632 .
%e A342632 For n=3, the size of the grid is 8 X 8:
%e A342632 .
%e A342632     | 1 2 3 4 5 6 7 8
%e A342632   --+----------------
%e A342632   1 | o o o o o o o o     8
%e A342632   2 | o . o . o . o .     4
%e A342632   3 | o o . o o . o o     6
%e A342632   4 | o . o . o . o .     4
%e A342632   5 | o o o o . o o o     7
%e A342632   6 | o . . . o . o .     3
%e A342632   7 | o o o o o o . o     7
%e A342632   8 | o . o . o . o .     4
%e A342632                          --
%e A342632                     Sum: 43
%o A342632 (Python)
%o A342632 import math
%o A342632 for n in range (0, 21):
%o A342632      counter = 0
%o A342632      for x in range (1, pow(2, n)+1):
%o A342632         for y in range(1, pow(2, n)+1):
%o A342632             if math.gcd(y, x) ==  1:
%o A342632                 counter += 1
%o A342632      print(n, counter)
%o A342632 (PARI) for(n=0,24,my(j=2^n);print1(2*sum(k=1,j,eulerphi(k))-1,", ")) \\ _Hugo Pfoertner_, Mar 17 2021
%o A342632 (Python)
%o A342632 from sympy import sieve
%o A342632 def A342632(n): return 2*sum(t for t in sieve.totientrange(1,2**n+1)) - 1 # _Chai Wah Wu_, Mar 23 2021
%o A342632 (Python)
%o A342632 from functools import lru_cache
%o A342632 @lru_cache(maxsize=None)
%o A342632 def A018805(n):
%o A342632   if n == 1: return 1
%o A342632   return n*n - sum(A018805(n//j) for j in range(2, n//2+1)) - (n+1)//2
%o A342632 print([A018805(2**n) for n in range(25)]) # _Michael S. Branicky_, Mar 23 2021
%Y A342632 a(n) = A018805(2^n).
%Y A342632 Cf. A000010, A002088, A059956 (6/Pi^2), A064018, A342586.
%K A342632 nonn
%O A342632 0,2
%A A342632 _Karl-Heinz Hofmann_, Mar 17 2021
%E A342632 Edited by _N. J. A. Sloane_, Jun 13 2021