|
|
A361373
|
|
Number of prime powers p^m <= n such that p | n.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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, 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(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)):
|
|
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.
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|