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,6

Comments

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

Links

Antti Karttunen, Table of n, a(n) for n = 1..16384

Index entries for sequences computed from exponents in factorization of n.

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

Example

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

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

Prog

(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

Crossrefs

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

Cf. A001620, A072102.

Sequence in context: A095960 A316314 A183093 * A377071 A029356 A334019

Adjacent sequences: A183093 A183094 A183095 * A183097 A183098 A183099

Keyword

nonn

Author

Jaroslav Krizek, Dec 25 2010

Status

approved