cp's OEIS Frontend

A057567 Number of partitions of n where the product of parts divides n.

%I A057567 #45 Jul 02 2025 16:02:00
%S A057567 1,2,2,4,2,5,2,7,4,5,2,11,2,5,5,12,2,11,2,11,5,5,2,21,4,5,7,11,2,15,2,
%T A057567 19,5,5,5,26,2,5,5,21,2,15,2,11,11,5,2,38,4,11,5,11,2,21,5,21,5,5,2,
%U A057567 36,2,5,11,30,5,15,2,11,5,15,2,52,2,5,11,11,5,15,2,38,12,5,2,36,5,5,5,21
%N A057567 Number of partitions of n where the product of parts divides n.
%C A057567 a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24=2^3*3 and 375=3*5^3 both have prime signature (3,1). - _Christian G. Bower_, Jun 03 2005
%H A057567 Antti Karttunen, <a href="/A057567/b057567.txt">Table of n, a(n) for n = 1..10000</a>
%H A057567 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A057567 a(n) = Sum_{d|n} A001055(d). - _Vladeta Jovovic_, Nov 19 2000
%F A057567 a(A025487(n)) = A108464(n).
%F A057567 a(p^k) = A000070(k).
%F A057567 a(A002110(n)) = A000110(n+1).
%F A057567 Dirichlet g.f.: zeta(s) * Product_{k>=2} 1/(1 - 1/k^s). - _Ilya Gutkovskiy_, Nov 03 2020
%e A057567 From _Gus Wiseman_, Jul 04 2019: (Start)
%e A057567 The a(1) = 1 through a(9) = 5 partitions are the following. The Heinz numbers of these partitions are given by A326155.
%e A057567   (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
%e A057567        (11)  (111)  (22)    (11111)  (321)     (1111111)  (4211)
%e A057567                     (211)            (3111)               (22211)
%e A057567                     (1111)           (21111)              (41111)
%e A057567                                      (111111)             (221111)
%e A057567                                                           (2111111)
%e A057567                                                           (11111111)
%e A057567 (End)
%t A057567 Table[Function[m, Count[Map[Times @@ # &, IntegerPartitions[m]], P_ /; Divisible[m, P]] - Boole[n == 1]]@ Apply[Times, #] &@ MapIndexed[Prime[First@ #2]^#1 &, Sort[FactorInteger[n][[All, -1]], Greater]], {n, 88}] (* _Michael De Vlieger_, Aug 16 2017 *)
%o A057567 (PARI)
%o A057567 fcnt(n, m) = {local(s); s=0; if(n == 1, s=1, fordiv(n, d, if(d > 1 & d <= m, s=s+fcnt(n/d, d)))); s}
%o A057567 A001055(n) = fcnt(n, n) \\ This function from _Michael B. Porter_, Oct 29 2009
%o A057567 A057567(n) = sumdiv(n, d, A001055(d)); \\ After Jovovic's formula. _Antti Karttunen_, May 25 2017
%o A057567 (Python)
%o A057567 from sympy import divisors, isprime
%o A057567 def T(n, m):
%o A057567     if isprime(n): return 1 if n <= m else 0
%o A057567     A = (d for d in divisors(n) if 1 < d < n and d <= m)
%o A057567     s = sum(T(n // d, d) for d in A)
%o A057567     return s + 1 if n <= m else s
%o A057567 def a001055(n): return T(n, n)
%o A057567 def a(n): return sum(a001055(d) for d in divisors(n))
%o A057567 print([a(n) for n in range(1, 51)]) # _Indranil Ghosh_, Aug 19 2017
%Y A057567 Cf. A000070, A000110, A001055 (Mobius transform), A002110, A025487, A057568, A108464, A113309, A131802.
%Y A057567 Any prime numbered column of array A108461.
%Y A057567 Cf. A028422, A096276, A114324, A318950, A319000, A319005, A326152, A326155.
%K A057567 nonn
%O A057567 1,2
%A A057567 _Leroy Quet_, Oct 04 2000
%E A057567 More terms from _James Sellers_, Oct 09 2000
%E A057567 More terms from _Vladeta Jovovic_, Nov 19 2000