A383156 The sum of the maximum exponents in the prime factorizations of the divisors of n.

0, 1, 1, 3, 1, 3, 1, 6, 3, 3, 1, 7, 1, 3, 3, 10, 1, 7, 1, 7, 3, 3, 1, 13, 3, 3, 6, 7, 1, 7, 1, 15, 3, 3, 3, 13, 1, 3, 3, 13, 1, 7, 1, 7, 7, 3, 1, 21, 3, 7, 3, 7, 1, 13, 3, 13, 3, 3, 1, 15, 1, 3, 7, 21, 3, 7, 1, 7, 3, 7, 1, 22, 1, 3, 7, 7, 3, 7, 1, 21, 10, 3, 1

Offset

1,4

Comments

Inverse Möbius transform of A051903.

a(n) depends only on the prime signature of n (A118914).

Links

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

Amiram Eldar, Plot of Sum_{k=1..n} a(k)/(c_1*n*log(n) + c_2*n) - 1 for n = 10^(1..10).

Formula

a(n) = Sum_{d|n} A051903(d).

a(n) = A000005(n) * A383157(n)/A383158(n).

a(p^e) = e*(e+1)/2 for prime p and e >= 0. In particular, a(p) = 1 for prime p.

a(n) = 2^omega(n) - 1 = A309307(n) if n is squarefree (A005117).

a(n) = tau(n, 2) - 1 + Sum_{k=2..A051903(n)} k * (tau(n, k+1) - tau(n, k)), where tau(n, k) is the number of k-free divisors of n (k-free numbers are numbers that are not divisible by a k-th power other than 1). For a given k >= 2, tau(n, k) is a multiplicative function with tau(p^e, k) = min(e+1, k). E.g., tau(n, 2) = A034444(n), tau(n, 3) = A073184(n), and tau(n, 4) = A252505(n).

Sum_{k=1..n} a(k) ~ c_1 * n * log(n) + c_2 * n, where c_1 is Niven's constant (A033150), c_2 = -1 + (2*gamma - 1)*c_1 - 2*zeta'(2)/zeta(2)^2 - Sum_{k>=3} (k-1) * (k*zeta'(k)/zeta(k)^2 - (k-1)*zeta'(k-1)/zeta(k-1)^2) = -2.37613633493572231366..., and gamma is Euler's constant (A001620).

Example

4 has 3 divisors: 1, 2 = 2^1 and 4 = 2^2. The maximum exponents in their prime factorizations are 0, 1 and 2, respectively. Therefore, a(4) = 0 + 1 + 2 = 3.
12 has 6 divisors: 1, 2 = 2^1, 3 = 3^1, 4 = 2^2, 6 = 2 * 3 and 12 = 2^2 * 3. The maximum exponents in their prime factorizations are 0, 1, 1, 2, 1 and 2, respectively. Therefore, a(12) = 0 + 1 + 1 + 2 + 1 + 2 = 7.

Mathematica

emax[n_] := If[n == 1, 0, Max[FactorInteger[n][[;; , 2]]]]; a[n_] := DivisorSum[n, emax[#] &]; Array[a, 100]
(* second program: *)
a[n_] := If[n == 1, 0, Module[{e = FactorInteger[n][[;; , 2]], emax, v}, emax = Max[e]; v = Table[Times @@ (Min[# + 1, k + 1] & /@ e), {k, 1, emax}]; v[[1]] + Sum[k*(v[[k]] - v[[k - 1]]), {k, 2, emax}] - 1]]; Array[a, 100]

Prog

(PARI) emax(n) = if(n == 1, 0, vecmax(factor(n)[, 2]));
a(n) = sumdiv(n, d, emax(d));
(PARI) a(n) = if(n == 1, 0, my(e = factor(n)[, 2], emax = vecmax(e), v); v = vector(emax, k, vecprod(apply(x ->min(x+1 , k+1), e))); v[1] + sum(k = 2, emax, k * (v[k]-v[k-1])) - 1);

Crossrefs

Cf. A000005, A001221, A005117, A034444, A051903, A073184, A118914, A252505, A309307, A383157, A383158, A383159.

Cf. A001620, A013661, A033150, A306016.

Sequence in context: A367628 A126212 A357858 * A066637 A317144 A050336

Adjacent sequences: A383153 A383154 A383155 * A383157 A383158 A383159

Keyword

nonn,easy

Author

Amiram Eldar, Apr 18 2025

Status

approved