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

Author

Michael De Vlieger, Jun 17 2024

Keywords

• nonn
• easy

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.

Examples

			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.
		

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

Crossrefs

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

Programs

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

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

Python

from sympy import integer_log, primefactors
def A361373(n): return sum(integer_log(n,p)[0] for p in primefactors(n)) # Chai Wah Wu, Sep 20 2024

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.