A376885 The number of factors of n of the form p^(k!) counted with multiplicity, where p is a prime and k >= 1, when the factorization is uniquely done using the factorial-base representation of the exponents in the prime factorization of n.

0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 3, 1, 3, 2, 2, 2, 2, 1, 2, 2, 3, 1, 3, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 3, 2, 3, 2, 2, 1, 3, 1, 2, 2, 1, 2, 3, 1, 2, 2, 3, 1, 3, 1, 2, 2, 2, 2, 3, 1, 3, 2, 2, 1, 3, 2, 2, 2, 3, 1, 3, 2, 2, 2, 2, 2, 4, 1, 2, 2, 2, 1, 3, 1, 3, 3

Offset: 1

Author

Amiram Eldar, Oct 08 2024

Keywords

• nonn
• easy
• base

Comments

Let n = Product p^e be the canonical prime factorization of n. The factorization of n that is based on the factorial-base representation of the exponents is done by factoring each prime power p^e into prime powers, p^e = Product_{k} (p^(k!))^d_k where e = Sum_{k>=1} d_k * k! is the factorial-base representation of e. So, the factors in this factorization are prime powers with exponents that are factorial numbers. Each factor in the factorization, p^(k!), can have a multiplicity d in the range [1, k], so this factorization of n is a product of numbers of the form (p^(k!))^d.

The number of factors counted with multiplicity (the sum of the multiplicities d in (p^(k!))^d) is given by this sequence (analogous to A001222 for the canonical prime factorization).

The number of distinct factors p^(k!) of n is A376886(n) (analogous to A001221).

The number of divisors of n that can be constructed from partial sets of these factors (with multiplicities that are not larger than those in n) is A376887(n) (analogous to A000005), and their sum is A376888(n) (analogous to A000203).

Examples

			For n = 8 = 2^3, the representation of 3 in factorial base is 11, i.e., 3 = 1! + 2!, so 8 = (2^(1!))^1 * (2^(2!))^1 and a(8) = 1 + 1 = 2.
For n = 16 = 2^4, the representation of 4 in factorial base is 20, i.e., 4 = 2 * 2!, so 16 = (2^(2!))^2 and a(16) = 2.
		

Links

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

Crossrefs

Cf. A000142, A007623, A034968, A077761.

Cf. A000005, A000203, A001221, A001222, A376886, A376887, A376888.

Similar sequences: A064547, A318464.

Programs

Mathematica

fdigsum[n_] := Module[{k = n, m = 2, r, s = 0}, While[{k, r} = QuotientRemainder[k, m]; k != 0 || r != 0, s += r; m++]; s]; f[p_, e_] := fdigsum[e]; a[1] = 0; a[n_] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100]

PARI

fdigsum(n) = {my(k = n, m = 2, r, s = 0); while([k, r] = divrem(k, m); k != 0 || r != 0, s += r; m++); s;}
a(n) = {my(e = factor(n)[, 2]); sum(i = 1, #e, fdigsum(e[i]));}

Formula

Additive with a(p^e) = A034968(e).

Sum_{k=1..n} a(k) ~ n * (log(log(n)) + B + C), where B is Mertens's constant (A077761) and C = Sum_{p prime} f(1/p) = 0.18682321026088865388..., where f(x) = -x + (1-x) * Sum_{k>=1} A034968(k)* x^k.