login
Number of partitions of n into 3 parts which have common divisors.
15

%I #20 Aug 24 2020 22:31:08

%S 0,0,0,0,0,0,1,0,1,1,2,0,4,0,4,3,5,0,9,0,9,5,10,0,16,2,14,7,17,0,27,0,

%T 21,11,24,6,36,0,30,15,37,0,51,0,41,25,44,0,64,4,58,25,57,0,81,12,69,

%U 31,70,0,108,0,80,43,85,16,123,0,97,45,120,0,144,0,114,69,121,14,171,0

%N Number of partitions of n into 3 parts which have common divisors.

%C a(p) = 0 if p is a prime. Can anyone suggest a formula?

%C See example for a method to find a(n). - _David A. Corneth_, Aug 24 2020

%H David A. Corneth, <a href="/A082024/b082024.txt">Table of n, a(n) for n = 0..9999</a> (first 5001 terms from Alois P. Heinz)

%e a(14) = 4 and the partitions are (10,2,2), (8,4,2),(6,6,2) and (6,4,4).

%e a(13) = 0 as for all r + s + t = 13,r > 0, s > 0,t> 0 gcd(r,s,t) = 1.

%e From _David A. Corneth_, Aug 24 2020: (Start)

%e a(100) = 233. The squarefree part of 100 is 10. The divisors of 10 are 1, 2, 5 and 10.

%e These are the possible squarefree divisors of parts. As parts must not be coprime, we exclude 1, leaving 2, 5 and 10. We then compute 100/k for each of these numbers.

%e This gives 50, 20 and 10 respectively. Now a(100) is found by adding -(round(50^2/12)*(-1)^omega(2) + round(20^2/12)*(-1)^omega(5) + round(10^2/12)*(-1)^omega(10)) = -(-208 - 33 + 8) = 233 where omega(m) is the number of distinct divisors of m (Cf. A001221) and round(m^2/12) is the number of partitions of m into 3 parts (Cf. A069905) (End)

%t a[n_] := Length[Select[Flatten[Table[{a, b, n-a-b}, {a, 1, Floor[n/3]}, {b, a, Floor[(n-a)/2]}], 1], GCD@@#1>1&]]

%o (PARI) a(n) = if(n==0, return(0)); cn = factorback(factor(n)[, 1]); d = divisors(cn); -sum(i = 2, #d, round((n/d[i])^2/12) * (-1)^omega(d[i])) \\ _David A. Corneth_, Aug 24 2020

%Y Cf. A001221, A069905, A082023, A284825.

%K nonn,easy

%O 0,11

%A _Amarnath Murthy_, Apr 07 2003

%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 20 2003 and _Dean Hickerson_, Apr 22 2003