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

Author

Michael De Vlieger, Jul 08 2014

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

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

Cf. A010846, A000005, A243822.

Programs

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

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

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