A361373 Number of prime powers p^m <= n such that p | n.

0, 1, 1, 2, 1, 3, 1, 3, 2, 4, 1, 5, 1, 4, 3, 4, 1, 6, 1, 5, 3, 5, 1, 6, 2, 5, 3, 5, 1, 9, 1, 5, 4, 6, 3, 8, 1, 6, 4, 7, 1, 9, 1, 6, 5, 6, 1, 8, 2, 7, 4, 6, 1, 8, 3, 7, 4, 6, 1, 10, 1, 6, 5, 6, 3, 10, 1, 7, 4, 10, 1, 9, 1, 7, 5, 7, 3, 10, 1, 8, 4, 7, 1, 12, 3, 7

Offset

1,4

Comments

Let p be prime. The term "prime power" p^m, m > 0, used here is that of A246655 = A000040 U A246547, the union of primes and perfect prime powers. Essentially, 1 is not considered a prime power.

Links

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Michael De Vlieger, Diagram illustrating a(1440) = 20. Terms are arranged according to prime decomposition and sorted vertically. This sequence counts primes (red) and perfect prime powers (gold).

Formula

a(n) = Sum_{p | n} floor(log n / log p).

a(n) = number of prime powers in row n of A162306.

a(n) < A000005(n), since A000005 counts 1.

a(n) < A010846(n), since A010846 counts 1.

Let tau = A000005, rad = A007947, rcf = A010846, and lpf = A020639.

a(p) = tau(p) - 1 = rcf(p) - 1 = 1 since S = row p of both A027750 and A162306 = {1, p} contains the prime power p.

a(p^m) = tau(p^m) - 1 = rcf(p^m) = 1 = m since S = row p^m of both A027750 and A162306 = {1, p, p^2, ..., p^m} contains the prime powers {p, p^2, ..., p^m}.

a(k) = tau(k) - 1 = 3 for squarefree composite k = p*q, p < q < p^2 in A138109 since S = row k of A162306 = {1, p, q, p^2, p*q} contains 3 prime powers {p, q, p^2}.

a(k) < tau(k) for k in A138511 and k in A126706 since m = lpf(k)^(-1 + floor(log k / log lpf(k))) is such that m < k but m does not divide k.

Example

Let S = {k <= n : rad(k) | n} = row n of A162306
a(1) = 0 since S = {1} has 0 prime powers.
a(2) = 1 since S = {1, [2]} has 1 prime power.
a(4) = 2 since S = {1, [2, 4]} has 2 prime powers.
a(6) = 3 since S = {1, [2, 3, 4], 6} has 3 prime powers.
a(10) = 4 since S = {1, [2, 4, 5, 8], 10} has 4 prime powers.
a(12) = 5 since S = {1, [2, 3, 4], 6, [8, 9], 12} has 5 prime powers, etc.

Maple

a := n -> add(ilog[p](n), p in NumberTheory:-PrimeFactors(n)):
seq(a(n), n = 1..92); # Peter Luschny, Jun 20 2024

Mathematica

{0}~Join~Table[Total@ Map[Floor@ Log[#, n] &, FactorInteger[n][[All, 1]]], {n, 2, 120}]

Prog

(PARI) a(n) = if (n==1, 0, my(f=factor(n)[, 1]); sum(k=1, #f, logint(n, f[k]))); \\ Michel Marcus, Jun 20 2024

Crossrefs

Cf. A000005, A000040, A007947, A010846, A020639, A126706, A138109, A138511, A162306, A246655, A246547.

Sequence in context: A038569 A308686 A020650 * A124224 A290089 A323902

Adjacent sequences: A361370 A361371 A361372 * A361374 A361375 A361376

Keyword

nonn,easy

Author

Michael De Vlieger, Jun 17 2024

Status

approved