A385974 a(n) = the number of reduced positive proper fractions p/q with phi(q) <= n.

1, 7, 7, 23, 23, 47, 47, 87, 87, 107, 107, 179, 179, 179, 179, 275, 275, 347, 347, 447, 447, 491, 491, 731, 731, 731, 731, 787, 787, 847, 847, 1071, 1071, 1071, 1071, 1359, 1359, 1359, 1359, 1719, 1719, 1887, 1887, 2019, 2019, 2111, 2111, 2639, 2639, 2639, 2639, 2743, 2743, 2851, 2851

Offset: 1

Author

Hal M. Switkay, Jul 13 2025

Keywords

• nonn

Comments

This sequence groups the reduced positive proper fractions p/q in a manner analogous to the Farey sequence (A005728, which adds the endpoints 0/1 and 1/1). However, instead of limiting the size of the denominator (q <= n as is done in the Farey sequence), we limit phi(q) = A000010(q), where phi is the Euler totient function. The computation requires A014197(r) = the number of natural numbers q such that phi(q) = r.

When k > 0, a(2k+1) = a(2k), because there are no natural numbers whose Euler totient equals 2k+1.

Examples

			a(4) enumerates the positive proper fractions whose denominator has Euler totient <= 4. The eligible denominators are 2; 3, 4, 6; 5, 8, 10, 12. The numerators are relatively prime to the denominators. Grouping the fractions by the order of the denominators above, we get: 1/2; 1/3, 2/3, 1/4, 3/4, 1/6, 5/6; 1/5, 2/5, 3/5, 4/5, 1/8, 3/8, 5/8, 7/8, 1/10, 3/10, 7/10, 9/10, 1/12, 5/12, 7/12, 11/12. Thus a(4) = 23.
		

Links

• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Crossrefs

Cf. A000010, A005728, A014197.

Programs

PARI

a(n) = sum(i=1, n, i*invphiNum(i)) - 1; \\ Michel Marcus, Jul 14 2025; using Max Alekseyev's invphi.gp

Formula

a(n) = -1 + Sum_{i=1..n} i*A014197(i).