A131233 a(n) = number of positive integers <= n which don't 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,2

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

Links

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

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

Example

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.

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 *)

Crossrefs

Cf. A131232.

Sequence in context: A162683 A073137 A345965 * A136623 A031218 A357004

Adjacent sequences: A131230 A131231 A131232 * A131234 A131235 A131236

Keyword

nonn

Author

Leroy Quet, Jun 20 2007

Extensions

More terms from Joshua Zucker, Jul 18 2007

Status

approved