A131232 a(n) is the number of positive integers < n that do not have 2 or more distinct prime divisors in common with n.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 12, 13, 14, 15, 16, 15, 18, 18, 20, 21, 22, 20, 24, 25, 26, 26, 28, 22, 30, 31, 32, 33, 34, 30, 36, 37, 38, 36, 40, 32, 42, 42, 42, 45, 46, 40, 48, 45, 50, 50, 52, 45, 54, 52, 56, 57, 58, 44, 60, 61, 60, 63, 64, 52, 66, 66, 68, 58, 70, 60, 72

Offset: 1

Author

Leroy Quet, Jun 20 2007

Keywords

• nonn

Examples

			The distinct primes which divide 20 are 2 and 5. So a(20) is the number of positive integers < 20 which are not divisible by at least 2 distinct primes dividing 20; i.e. are not divisible by both 2 and 5. Among the first 19 positive integers only 10 is divisible by both 2 and 5. There are 18 other positive integers <= 19, so a(20) = 18.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A010055, A131233.

Programs

Mathematica

a[n_] := Module[{p = FactorInteger[n][[;; , 1]]}, n * Times @@ (1-1/p) * (1 + Total[1/(p-1)]) - Boole[Length[p] == 1]]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jun 21 2025 *)

PARI

a(n) = {my(p = factor(n)[,1]); n * vecprod(apply(x -> 1-1/x, p)) * (1 + vecsum(apply(x -> 1/(x-1), p))) - (#p < 2);} \\ Amiram Eldar, Jun 21 2025

Formula

a(n) = A131233(n) - A010055(n). - Amiram Eldar, Jun 21 2025

Extensions

More terms from Joshua Zucker, Jul 18 2007