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

%I #25 Apr 05 2021 20:39:17

%S 1,3,4,7,6,16,8,15,13,30,12,45,14,36,33,31,18,79,20,66,41,64,24,103,

%T 31,70,40,80,30,235,32,63,84,114,73,198,38,120,92,163,42,310,44,140,

%U 130,132,48,246,57,213,108,154,54,300,97,217,116,150,60,600,62,156,180,127,109,540,68,246

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

%C 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.

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

%H Michael De Vlieger, <a href="/A244974/b244974.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = Sum_{k=1..n} k*( floor(n^k/k)-floor((n^k - 1)/k) ). - _Anthony Browne_, May 25 2016

%F a(n) = Sum_{j=1..n} Sum_{i=j..gcd(n^j,j)} i. - _Wesley Ivan Hurt_, Apr 05 2021

%e For n = 4, A162306(4) = {1, 2, 4} and a(4) = 7.

%e For n = 5, A162306(5) = {1, 5} and a(5) = 6.

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

%t Table[Total@ Union[{1}, Function[d, Select[Range@ n, Union[d, First /@ FactorInteger@ #] == d &]][First /@ FactorInteger@ n]], {n, 68}] (* or *)

%t Table[Sum[k (Floor[n^k/k] - Floor[(n^k - 1)/k]), {k, n}], {n, 68}] (* _Michael De Vlieger_, May 26 2016 *)

%o (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

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

%Y Cf. A010846, A000005, A243822.

%K nonn

%O 1,2

%A _Michael De Vlieger_, Jul 08 2014