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

1, 3, 11, 43, 159, 647, 2519, 10043, 39895, 159703, 637927, 2551171, 10200039, 40803219, 163198675, 652774767, 2611029851, 10444211447, 41776529287, 167106121619, 668423198491, 2673693100831, 10694768891659, 42779072149475, 171116268699455, 684465093334979, 2737860308070095

Offset

0,2

Links

Chai Wah Wu, Table of n, a(n) for n = 0..45

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.

Formula

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

Example

Only fractions with gcd(numerator, denominator) = 1 are counted. E.g.,
  1/2 counts, but 2/4, 3/6, 4/8 ... do not, because they reduce to 1/2;
  1/1 counts, but 2/2, 3/3, 4/4 ... do not, because they reduce to 1/1.
.
For n=0, the size of the grid is 1 X 1:
.
    | 1
  --+--
  1 | o      Sum:  1
.
For n=1, the size of the grid is 2 X 2:
.
    | 1 2
  --+----
  1 | o o          2
  2 | o .          1
                  --
             Sum:  3
.
For n=2, the size of the grid is 4 X 4:
.
    | 1 2 3 4
  --+--------
  1 | o o o o      4
  2 | o . o .      2
  3 | o o . o      3
  4 | o . o .      2
                  --
             Sum: 11
.
For n=3, the size of the grid is 8 X 8:
.
    | 1 2 3 4 5 6 7 8
  --+----------------
  1 | o o o o o o o o     8
  2 | o . o . o . o .     4
  3 | o o . o o . o o     6
  4 | o . o . o . o .     4
  5 | o o o o . o o o     7
  6 | o . . . o . o .     3
  7 | o o o o o o . o     7
  8 | o . o . o . o .     4
                         --
                    Sum: 43

Prog

(Python)
import math
for n in range (0, 21):
     counter = 0
     for x in range (1, pow(2, n)+1):
        for y in range(1, pow(2, n)+1):
            if math.gcd(y, x) ==  1:
                counter += 1
     print(n, counter)
(PARI) for(n=0, 24, my(j=2^n); print1(2*sum(k=1, j, eulerphi(k))-1, ", ")) \\ Hugo Pfoertner, Mar 17 2021
(Python)
from sympy import sieve
def A342632(n): return 2*sum(t for t in sieve.totientrange(1, 2**n+1)) - 1 # Chai Wah Wu, Mar 23 2021
(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(2**n) for n in range(25)]) # Michael S. Branicky, Mar 23 2021

Crossrefs

a(n) = A018805(2^n).

Cf. A000010, A002088, A059956 (6/Pi^2), A064018, A342586.

Sequence in context: A034477 A140803 A246758 * A084643 A364865 A302705

Adjacent sequences: A342629 A342630 A342631 * A342633 A342634 A342635

Keyword

nonn

Author

Karl-Heinz Hofmann, Mar 17 2021

Extensions

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

Status

approved