A169594 Number of divisors of n, counting divisor multiplicity in n.

1, 2, 2, 4, 2, 4, 2, 6, 4, 4, 2, 7, 2, 4, 4, 9, 2, 7, 2, 7, 4, 4, 2, 10, 4, 4, 6, 7, 2, 8, 2, 11, 4, 4, 4, 12, 2, 4, 4, 10, 2, 8, 2, 7, 7, 4, 2, 14, 4, 7, 4, 7, 2, 10, 4, 10, 4, 4, 2, 13, 2, 4, 7, 15, 4, 8, 2, 7, 4, 8, 2, 16, 2, 4, 7, 7, 4, 8, 2, 14, 9, 4, 2, 13, 4, 4, 4, 10, 2, 13, 4, 7, 4, 4, 4, 17, 2, 7

Offset: 1

Author

Joseph L. Pe, Dec 02 2009

Keywords

• nonn
• easy

Comments

The multiplicity of a divisor d > 1 in n is defined as the largest power i for which d^i divides n; and for d = 1 it is defined as 1.

a(n) is also the sum of the multiplicities of the divisors of n.

In other words, a(n) = 1 + sum of the highest exponents e_i for which each number k_i in range 2 .. n divide n, as {k_i}^{e_i} | n. For nondivisors of n this exponent e_i is 0, for n itself it is 1. - Antti Karttunen, May 20 2017

From Gus Wiseman, Mar 25 2021: (Start)

Also the number of strict chains of divisors ending with n and having constant (equal) first quotients. The case starting with 1 is A089723. For example, the a(1) = 1 through a(12) = 7 chains are:

1 2 3 4 5 6 7 8 9 10 11 12

1|2 1|3 1|4 1|5 1|6 1|7 1|8 1|9 1|10 1|11 1|12

2|4 2|6 2|8 3|9 2|10 2|12

1|2|4 3|6 4|8 1|3|9 5|10 3|12

2|4|8 4|12

1|2|4|8 6|12

3|6|12

(End)

a(n) depends only on the prime signature of n. - David A. Corneth, Mar 28 2021

Examples

			The divisors of 8 are 1, 2, 4, 8 of multiplicity 1, 3, 1, 1, respectively. So a(8) = 1 + 3 + 1 + 1 = 6.
		

Links

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

Crossrefs

Cf. A168512.

Row sums of A286561, A286563 and A286564.

A001055 counts factorizations (strict: A045778, ordered: A074206).

A057567 counts chains of divisors with weakly increasing first quotients.

A067824 counts strict chains of divisors ending with n.

A253249 counts strict chains of divisors.

A334997 counts chains of divisors of n by length.

A342086 counts chains of divisors with strictly increasing first quotients.

A342496 counts partitions with equal first quotients (strict: A342515, ranking: A342522, ordered: A342495).

A342530 counts chains of divisors with distinct first quotients.

Cf. A003238, A003242, A069916, A122651, A309891, A318991, A318992, A325545.

Programs

Maple

a := n -> ifelse(n < 2, 1, 1 + add(padic:-ordp(n, k), k = 2..n)):
seq(a(n), n = 1..98);  # Peter Luschny, Apr 10 2025

Mathematica

divmult[d_, n_] := Module[{output, i}, If[d == 1, output = 1, If[d == n, output = 1, i = 0; While[Mod[n, d^(i + 1)] == 0, i = i + 1]; output = i]]; output]; dmt0[n_] := Module[{divs, l}, divs = Divisors[n]; l = Length[divs]; Sum[divmult[divs[[i]], n], {i, 1, l}]]; Table[dmt0[i], {i, 1, 40}]
Table[1 + DivisorSum[n, IntegerExponent[n, #] &, # > 1 &], {n, 98}] (* Michael De Vlieger, May 20 2017 *)

PARI

A286561(n,k) = { my(i=1); if(1==k, 1, while(!(n%(k^i)), i = i+1); (i-1)); };
A169594(n) = sumdiv(n,d,A286561(n,d)); \\ Antti Karttunen, May 20 2017

PARI

a(n) = { if(n == 1, return(1)); my(f = factor(n), u = vecmax(f[, 2]), cf = f, res = numdiv(f) - u + 1); for(i = 2, u, cf[, 2] = f[, 2]\i; res+=numdiv(factorback(cf)) ); res } \\ David A. Corneth, Mar 29 2021

Python

def a286561(n, k):
    i=1
    if k==1: return 1
    while n%(k**i)==0:
        i+=1
    return i-1
def a(n): return sum([a286561(n, d) for d in divisors(n)]) # Indranil Ghosh, May 20 2017

Scheme

(define (A169594 n) (add (lambda (k) (A286561bi n k)) 1 n))
;; Implements sum_{i=lowlim..uplim} intfun(i)
(define (add intfun lowlim uplim) (let sumloop ((i lowlim) (res 0)) (cond ((> i uplim) res) (else (sumloop (1+ i) (+ res (intfun i)))))))
;; For A286561bi see A286561. - Antti Karttunen, May 20 2017

Formula

From Friedjof Tellkamp, Feb 29 2024: (Start)

a(n) = A309891(n) + 1.

G.f.: x/(1-x) + Sum_{k>=2, j>=1} x^(k^j)/(1-x^(k^j)).

Dirichlet g.f.: zeta(s) * (1 + Sum_{k>=1} (zeta(k*s) - 1)).

Sum_{n>=1} a(n)/n^2 = (7/24) * Pi^2. (End)

Extensions

Extended by Ray Chandler, Dec 08 2009