cp's OEIS Frontend

A319301 Sum of GCDs of strict integer partitions of n.

%I A319301 #19 May 20 2021 04:08:35
%S A319301 1,2,4,5,7,10,11,14,18,21,22,33,30,39,49,54,54,78,72,100,110,121,126,
%T A319301 181,174,207,238,284,284,389,370,466,512,582,647,806,796,954,1066,
%U A319301 1265,1300,1616,1652,1979,2192,2452,2636,3202,3336,3892,4237,4843,5172,6090
%N A319301 Sum of GCDs of strict integer partitions of n.
%H A319301 Alois P. Heinz, <a href="/A319301/b319301.txt">Table of n, a(n) for n = 1..1000</a>
%H A319301 Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>
%F A319301 From _Richard L. Ollerton_, May 06 2021: (Start)
%F A319301 a(n) = Sum_{d|n} A000010(n/d)*A000009(d).
%F A319301 a(n) = Sum_{k=1..n} A000009(gcd(n,k)).
%F A319301 a(n) = Sum_{k=1..n} A000009(n/gcd(n,k))*A000010(gcd(n,k))/A000010(n/gcd(n,k)). (End)
%p A319301 b:= proc(n, i, r) option remember; `if`(i*(i+1)/2<n, 0,
%p A319301       (t-> `if`(i<n, b(n-i, min(i-1, n-i), t), 0)
%p A319301       +`if`(i=n, t, 0)+b(n, i-1, r))(igcd(i, r)))
%p A319301     end:
%p A319301 a:= n-> b(n$2, 0):
%p A319301 seq(a(n), n=1..61);  # _Alois P. Heinz_, Mar 17 2019
%t A319301 Table[Sum[GCD@@ptn,{ptn,Select[IntegerPartitions[n],UnsameQ@@#&]}],{n,30}]
%t A319301 (* Second program: *)
%t A319301 b[n_, i_, r_] := b[n, i, r] = If[i(i+1)/2 < n, 0,
%t A319301      With[{t = GCD[i, r]}, If[i < n, b[n - i, Min[i - 1, n - i], t], 0] +
%t A319301      If[i == n, t, 0] + b[n, i - 1, r]]];
%t A319301 a[n_] := b[n, n, 0];
%t A319301 Array[a, 61] (* _Jean-François Alcover_, May 20 2021, after _Alois P. Heinz_ *)
%Y A319301 Cf. A000009, A000010, A078374, A078392, A289508, A289509, A303138, A306956, A319300.
%K A319301 nonn
%O A319301 1,2
%A A319301 _Gus Wiseman_, Sep 16 2018