A005361 Product of exponents of prime factorization of n.

1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 4, 1, 2, 1, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 1, 1, 5, 1, 1, 1, 4, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 4, 2, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 2, 1, 1, 2, 6, 1, 1, 1, 2, 1, 1, 1, 6, 1, 1, 2, 2, 1, 1

Offset: 1

Author

Jeffrey Shallit and Olivier Gérard

Keywords

• nonn
• easy
• nice
• mult

Comments

a(n) depends only on prime signature of n (cf. A025487, A052306). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3,1).

There was a comment here that said "a(n) is the number of nilpotents elements in the ring Z/nZ", but this is false, see A003557.

a(n) is the number of square-full divisors of n. a(n) is also the number of divisors d of n such that d and n have the same prime factors, i.e., A007947(d) = A007947(n). - Laszlo Toth, May 22 2009

Number of divisors u of n such that u|(u^n/n). Row lengths in triangle of A284318. - Juri-Stepan Gerasimov, Apr 05 2017

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from T. D. Noe)
• Imanuel Chen and Michael Z. Spivey, Integral Generalized Binomial Coefficients of Multiplicative Functions, Preprint 2015; Summer Research Paper 238, Univ. Puget Sound.
• P. Erdős and T. Motzkin, Problem 5735, Amer. Math. Monthly, 78 (1971), 680-681. (Incorrect solution!)
• Vaclav Kotesovec, Graph - the asymptotic ratio (100000 terms)
• J. Knopfmacher, A prime-divisor function, Proc. Amer. Math. Soc., 40 (1973), 373-377.
• MathStackExchange, Dirichlet series for zeta(s)*zeta(2*s)*zeta(3*s)*zeta(6*s)^(-1).
• H. N. Shapiro, Problem 5735, Amer. Math. Monthly, 97 (1990), 937.
• D. Suryanarayana and R. Sitaramachandra Rao, The number of square-full divisors of an integer, Proc. Amer. Math. Soc., Vol. 34, No. 1 (1972), pp. 79-80.
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

Cf. A000005, A002110, A005117 (indices of ones), A028234, A052306, A067029, A072411, A082695, A284318.

Cf. A360969, A360970, A361132.

Cf. A340065 (Dgf at s=2).

Programs

Haskell

a005361 = product . a124010_row -- Reinhard Zumkeller, Jan 09 2012

Maple

A005361 := proc(n)
    local a, p ;
    a := 1 ;
    for p in ifactors(n)[2] do
       a := a*op(2, p) ;
    end do:
    a ;
end proc:
seq(A005361(n),n=1..30) ; # R. J. Mathar, Nov 20 2012
# second Maple program:
a:= n-> mul(i[2], i=ifactors(n)[2]):
seq(a(n), n=1..80);  # Alois P. Heinz, Feb 18 2020

Mathematica

Prepend[ Array[ Times @@ Last[ Transpose[ FactorInteger[ # ] ] ]&, 100, 2 ], 1 ]
Array[Times@@Transpose[FactorInteger[#]][[2]]&,80] (* Harvey P. Dale, Aug 15 2012 *)

PARI

for(n=1,100, f=factor(n); print1(prod(i=1,omega(f), f[i,2]),",")) \\ edited by M. F. Hasler, Feb 18 2020

PARI

a(n)=factorback(factor(n)[,2]) \\ Charles R Greathouse IV, Nov 07 2014

PARI

for(n=1, 100, print1(direuler(p=2, n, (1 - X + X^2)/(1 - X)^2)[n], ", ")) \\ Vaclav Kotesovec, Jun 14 2020

Python

from math import prod
from sympy import factorint
def a(n): return prod(factorint(n).values())
print([a(n) for n in range(1, 91)]) # Michael S. Branicky, Jul 04 2022

Scheme

(define (A005361 n) (if (= 1 n) 1 (* (A067029 n) (A005361 (A028234 n))))) ;; Antti Karttunen, Mar 06 2017

Formula

n = Product (p_j^k_j) -> a(n) = Product (k_j).

Dirichlet g.f.: zeta(s)*zeta(2s)*zeta(3s)/zeta(6s).

Multiplicative with a(p^e) = e. - David W. Wilson, Aug 01 2001

a(n) = Sum_{d dividing n} floor(rad(d)/rad(n)) where rad(n) is A007947. - Enrique Pérez Herrero, Nov 06 2009

For n > 1: a(n) = Product_{k=1..A001221(n)} A124010(n,k). - Reinhard Zumkeller, Aug 27 2011

a(n) = tau(n/rad(n)), where tau is A000005 and rad is A007947. - Anthony Browne, May 11 2016

a(n) = Sum_{k=1..n}(floor(cos^2(Pi*k^n/n))*floor(cos^2(Pi*n/k))). - Anthony Browne, May 11 2016

From Antti Karttunen, Mar 06 2017: (Start)

For all n >= 1, a(prime^n) = n, a(A002110(n)) = a(A005117(n)) = 1. [From Crossrefs section.]

a(1) = 1; for n > 1, a(n) = A067029(n) * a(A028234(n)).

(End)

Let (b(n)) be multiplicative with b(p^e) = -1 + ( (floor((e-1)/3)+floor(e/3)) mod 4 ) for p prime and e > 0, then b(n) is the Dirichlet inverse of (a(n)). - Werner Schulte, Feb 23 2018

Sum_{i=1..k} a(i) ~ (zeta(2)*zeta(3)/zeta(6)) * k (Suryanarayana and Sitaramachandra Rao, 1972). - Amiram Eldar, Apr 13 2020

More precise asymptotics: Sum_{k=1..n} a(k) ~ 315*zeta(3)*n / (2*Pi^4) + zeta(1/2)*zeta(3/2)*sqrt(n) / zeta(3) + 6*zeta(1/3)*zeta(2/3)*n^(1/3) / Pi^2 [Knopfmacher, 1973]. - Vaclav Kotesovec, Jun 13 2020