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

1, 2, 3, 4, 5, 5, 7, 8, 9, 9, 11, 10, 13, 13, 14, 16, 17, 15, 19, 18, 20, 21, 23, 20, 25, 25, 27, 26, 29, 22, 31, 32, 32, 33, 34, 30, 37, 37, 38, 36, 41, 32, 43, 42, 42, 45, 47, 40, 49, 45, 50, 50, 53, 45, 54, 52, 56, 57, 59, 44, 61, 61, 60, 64, 64, 52, 67, 66, 68, 58, 71, 60, 73

Offset: 1

Author

Leroy Quet, Jun 20 2007

Keywords

• nonn

Comments

Equivalently, a(n) is the number of integers m, 1 <= m <= n such that gcd(m,n) is 1 or a prime or a prime power, i.e. gcd(m,n) = p^k for some prime p and some k >= 0. Cf. A117494. - Geoffrey Critzer, Feb 22 2015

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 20 positive integers only 10 and 20 are divisible by both 2 and 5. There are 18 other positive integers <= 20, so a(20)=18.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A010055, A013661, A131232, A116512, A117494, A154945.

Programs

Maple

with(numtheory):
a:= n-> add(`if`(nops(factorset(igcd(n,k)))<2, 1, 0), k=1..n):
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 22 2015

Mathematica

nn = 73; f[list_, i_] := list[[i]]; a =Table[If[Length[FactorInteger[n]] == 1, 1, 0], {n, 1, nn}]; b =Table[EulerPhi[n], {n, 1, nn}]; Table[
DirichletConvolve[f[a, n], f[b, n], n, m], {m, 1, nn}] (* Geoffrey Critzer, Feb 22 2015 *)
a[n_] := Module[{p = FactorInteger[n][[;; , 1]]}, n * Times @@ (1-1/p) * (1 + Total[1/(p-1)])]; a[1] = 1; 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)));} \\ Amiram Eldar, Jun 21 2025

Formula

Dirichlet g.f.: A(s)*zeta(s-1)/zeta(s) where A(s) = Sum_{n>=1} A010055(n)/n^s - Geoffrey Critzer, Feb 22 2015

From Amiram Eldar, Jun 21 2025: (Start)

a(n) = A116512(n) + A000010(n).

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = (1 + Sum_{p prime} (1/(p^2-1))) / zeta(2) = (1 + A154945)/A013661 = 0.94331640941093700227... . (End)

Extensions

More terms from Joshua Zucker, Jul 18 2007