Co-primality and the number pi

Jelly, 12 8 bytes

RÆṪSḤ’÷²

Try it online!

The following binary code works with this version of the Jelly interpreter.

0000000: 52 91 b0 53 aa b7 9a 8a  R..S....

Idea

Clearly, the number of pairs (j, k) such that j ≤ k and j and k are co-prime equals the number of pairs (k, j) that satisfy the same conditions. Also, if j = k, j = 1 = k.

Thus, to count the number of co-prime pairs with coordinates between 1 and n, it suffices to calculate the amount m of pairs (j, k) such that j ≤ k, then compute 2m - 1.

Finally, since Euler's totient function φ(k) yields the number integers between between 1 and k that are co-prime to k, we can calculate m as φ(1) + … + φ(n).

Code

RÆṪSḤ’÷²    Input: n

R           Yield [1, ..., n].
 ÆṪ         Apply Euler's totient function to each k in [1, ..., n].
   S        Compute the sum of all results.
    Ḥ       Multiply the result by 2.
     ’      Subtract 1.
      ÷²    Divide the result by n².

Mathematica 43 42 bytes

I found Lattice points visible from the origin, from which the picture below is taken, to be helpful in reframing the problem through the following questions regarding a given square region of the unit lattice:

• What fraction of the unit-lattice points have co-prime coordinates?
• What fraction of unit-lattice points can be seen from the origin?

---

N@Mean[Mean/@Boole@Array[CoprimeQ,{#,#}]]&

---

Examples

Trailing zeros are omitted.

N@Mean[Mean/@Boole@Array[CoprimeQ,{#,#}]]&/@Range@10

{1., 0.75, 0.777778, 0.6875, 0.76, 0.638889, 0.714286, 0.671875, 0.679012, 0.63}

---

Timing

The timing, in seconds, precedes the answer.

N@Mean[Mean/@Boole@Array[CoprimeQ,{#,#}]]&[1000]// AbsoluteTiming

{0.605571, 0.608383}

Pyth - 13 11 bytes

.OqR1iM^SQ2

Test Suite.