A282446 Call d a recursive divisor of n iff the p-adic valuation of d is a recursive divisor of the p-adic valuation of n for any prime p dividing d; a(n) gives the number of recursive divisors of n.

1, 2, 2, 3, 2, 4, 2, 3, 3, 4, 2, 6, 2, 4, 4, 4, 2, 6, 2, 6, 4, 4, 2, 6, 3, 4, 3, 6, 2, 8, 2, 3, 4, 4, 4, 9, 2, 4, 4, 6, 2, 8, 2, 6, 6, 4, 2, 8, 3, 6, 4, 6, 2, 6, 4, 6, 4, 4, 2, 12, 2, 4, 6, 5, 4, 8, 2, 6, 4, 8, 2, 9, 2, 4, 6, 6, 4, 8, 2, 8, 4, 4, 2, 12, 4, 4

Offset

1,2

Comments

More informally, the prime tower factorization of a recursive divisor of n can be obtained by removing branches from the prime tower factorization of n (the prime tower factorization of a number is defined in A182318).

A recursive divisor of n is also a divisor of n, hence a(n)<=A000005(n) for any n, with equality iff n is cubefree (i.e. n belongs to A004709).

A recursive divisor of n is also a (1+e)-divisor of n, hence a(n)<=A049599(n) for any n, with equality iff the p-adic valuation of n is cubefree for any prime p dividing n.

This sequence first differs from A049599 at n=256: a(256)=4 whereas A049599(256)=5; note that 256=2^(2^3), and 2^3 is not cubefree.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Formula

Multiplicative, with a(p^k)=1+a(k) for any prime p and k>0.

a(A014221(n))=n+1 for any n>=0.

Example

The recursive divisors of 40 are: 1, 2, 5, 8, 10 and 40, hence a(40)=6.

Mathematica

a[1] = 1; a[n_] := a[n] = Times @@ (1 + a/@ (Last /@ FactorInteger[n])); Array[a, 100] (* Amiram Eldar, Apr 12 2020 *)

Prog

(PARI) a(n) = my (f=factor(n)); return (prod(i=1, #f~, 1+a(f[i, 2])))

Crossrefs

Cf. A000005, A004709, A049599, A014221, A182318.

Sequence in context: A073184 A377519 A073182 * A049599 A353898 A366901

Adjacent sequences: A282443 A282444 A282445 * A282447 A282448 A282449

Keyword

nonn,mult

Author

Rémy Sigrist, Feb 15 2017

Status

approved