A183096 a(n) = number of divisors of n that are not perfect powers.

0, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 4, 1, 3, 3, 1, 1, 4, 1, 4, 3, 3, 1, 5, 1, 3, 1, 4, 1, 7, 1, 1, 3, 3, 3, 5, 1, 3, 3, 5, 1, 7, 1, 4, 4, 3, 1, 6, 1, 4, 3, 4, 1, 5, 3, 5, 3, 3, 1, 10, 1, 3, 4, 1, 3, 7, 1, 4, 3, 7, 1, 7, 1, 3, 4, 4, 3, 7, 1, 6, 1, 3, 1, 10, 3, 3, 3, 5, 1, 10, 3, 4, 3, 3, 3, 7, 1, 4, 4, 5

Offset: 1

Author

Jaroslav Krizek, Dec 25 2010

Keywords

• nonn

Comments

Sequence is not the same as A183093: a(72) = 7, A183093(72) = 6.

Examples

			For n = 12, set of such divisors is {2, 3, 6, 12}; a(12) = 4.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384
• Index entries for sequences computed from exponents in factorization of n.

Crossrefs

Cf. A000005, A001597, A091050, A183093, A183095.

Cf. A001620, A072102.

Programs

Mathematica

ppQ[n_] := GCD @@ FactorInteger[n][[;;, 2]] > 1; ppQ[1] = True; a[n_] := DivisorSum[n, 1 &, !ppQ[#] &]; Array[a, 100] (* Amiram Eldar, Jan 30 2025 *)

PARI

A091050(n) = (1+ sumdiv(n, d, ispower(d)>1)); \\ This function from Michel Marcus, Sep 21 2014
A183096(n) = (numdiv(n) - A091050(n)); \\ Antti Karttunen, Nov 23 2017

Formula

a(n) = A000005(n) - A091050(n).

a(1) = 0, a(p) = 1, a(pq) = 3, a(pq...z) = 2^k - 1, a(p^k) = 1, for p, q = primes, k = natural numbers, pq...z = product of k (k > 2) distinct primes p, q, ..., z.

Sum_{k=1..n} a(k) ~ n*(log(n) + 2*gamma - A072102 - 2), where gamma is Euler's constant (A001620). - Amiram Eldar, Jan 29 2025