A385378 The maximum possible number of distinct factors in the factorization of n into prime powers (A246655).

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, 2, 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, 3, 2, 3, 1, 2, 2, 3, 1, 3, 1, 2, 2, 2, 2, 3, 1, 3, 2, 2, 1, 3, 2, 2, 2

Offset: 1

Author

Amiram Eldar, Jun 27 2025

Keywords

• nonn
• easy

Comments

Differs from A376885 and A384422 at n = 32, 64, 96, 128, 160, 192, ... .

Differs from A086435 at n = 36, 100, 144, 180, 196, 225, ... .

Differs from A375272 at n = 128, 384, 640, 896, 1024, 1152, ... .

a(n) depends only on the prime signature of n (A118914).

The indices of records in this sequence are the partial products of the sequence of powers of primes (A000961), i.e., the terms in A024923.

The least index n such that a(n) = k, for k = 0, 1, 2, ..., is A024923(k+1).

Examples

			      n | a(n) | factorization
  ------+------+--------------------------------
      2 |  1   | 2
      6 |  2   | 2 * 3
     24 |  3   | 2 * 3 * 2^2
    120 |  4   | 2 * 3 * 2^2 * 5
    840 |  5   | 2 * 3 * 2^2 * 5 * 7
   6720 |  6   | 2 * 3 * 2^2 * 5 * 7 * 2^3
  60480 |  7   | 2 * 3 * 2^2 * 5 * 7 * 2^3 * 3^2
		

Links

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

Crossrefs

Cf. A000430, A000961, A001221, A003056, A004709, A024923, A077761, A086435, A118914, A246655, A254578, A375272, A376885, A384422, A385379.

Programs

Mathematica

f[p_, e_] := Floor[(Sqrt[8*e + 1] - 1)/2]; a[1] = 0; a[n_] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100]

PARI

a(n) = vecsum(apply(x -> (sqrtint(8*x+1)-1)\2 , factor(n)[, 2]));

Formula

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

a(n) >= A001221(n), with equality if and only if n is cubefree (A004709).

a(n) >= 1 for n >= 2, with equality if and only if n is a prime or a square of a prime (A000430).

Sum_{k=1..n} a(k) ~ n * (log(log(n)) + B + C), where B is Mertens's constant (A077761), C = Sum_{k>=2} P(k*(k+1)/2) = 0.19285739770001405035..., and P is the prime zeta function.