A244974 Sum of numbers m <= n whose set of prime divisors is a subset of the set of prime divisors of n.

1, 3, 4, 7, 6, 16, 8, 15, 13, 30, 12, 45, 14, 36, 33, 31, 18, 79, 20, 66, 41, 64, 24, 103, 31, 70, 40, 80, 30, 235, 32, 63, 84, 114, 73, 198, 38, 120, 92, 163, 42, 310, 44, 140, 130, 132, 48, 246, 57, 213, 108, 154, 54, 300, 97, 217, 116, 150, 60, 600, 62, 156, 180, 127, 109, 540, 68, 246

Offset

1,2

Comments

a(n) = A000203(n) when n is prime or a perfect prime power (A000961). This is because all products of the prime divisor p in such numbers produce divisors.

a(n) > A000203(n) when n is composite and not a perfect prime power.

Links

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

Formula

a(n) = Sum_{k=1..n} k*( floor(n^k/k)-floor((n^k - 1)/k) ). - Anthony Browne, May 25 2016

a(n) = Sum_{j=1..n} Sum_{i=j..gcd(n^j,j)} i. - Wesley Ivan Hurt, Apr 05 2021

Example

For n = 4, A162306(4) = {1, 2, 4} and a(4) = 7.
For n = 5, A162306(5) = {1, 5} and a(5) = 6.
For n = 6, A162306(6) = {1, 2, 3, 4, 6} and a(6) = 16.

Mathematica

Table[Total@ Union[{1}, Function[d, Select[Range@ n, Union[d, First /@ FactorInteger@ #] == d &]][First /@ FactorInteger@ n]], {n, 68}] (* or *)
Table[Sum[k (Floor[n^k/k] - Floor[(n^k - 1)/k]), {k, n}], {n, 68}] (* Michael De Vlieger, May 26 2016 *)

Prog

(PARI) a(n) = {summ = 0; spn = factor(n)[, 1]~; for (m=1, n, spm = factor(m)[, 1]~; if (setintersect(spm, spn) == spm, summ += m); ); summ; } \\ Michel Marcus, Jul 17 2014

Crossrefs

a(n) = sum of terms of n-th row of triangle A162306(n,k).

Cf. A010846, A000005, A243822.

Sequence in context: A241448 A323243 A346193 * A077580 A069213 A130700

Adjacent sequences: A244971 A244972 A244973 * A244975 A244976 A244977

Keyword

nonn

Author

Michael De Vlieger, Jul 08 2014

Status

approved