A282446 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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