login
A342632
Number of ordered pairs (x, y) with gcd(x, y) = 1 and 1 <= {x, y} <= 2^n.
9
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
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).
Sequence in context: A034477 A140803 A246758 * A084643 A364865 A302705
KEYWORD
nonn
AUTHOR
Karl-Heinz Hofmann, Mar 17 2021
EXTENSIONS
Edited by N. J. A. Sloane, Jun 13 2021
STATUS
approved