A319301 Sum of GCDs of strict integer partitions of n.

1, 2, 4, 5, 7, 10, 11, 14, 18, 21, 22, 33, 30, 39, 49, 54, 54, 78, 72, 100, 110, 121, 126, 181, 174, 207, 238, 284, 284, 389, 370, 466, 512, 582, 647, 806, 796, 954, 1066, 1265, 1300, 1616, 1652, 1979, 2192, 2452, 2636, 3202, 3336, 3892, 4237, 4843, 5172, 6090

Offset: 1

Author

Gus Wiseman, Sep 16 2018

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Wikipedia, Partition (number theory)

Crossrefs

Cf. A000009, A000010, A078374, A078392, A289508, A289509, A303138, A306956, A319300.

Programs

Maple

b:= proc(n, i, r) option remember; `if`(i*(i+1)/2 `if`(i b(n$2, 0):
seq(a(n), n=1..61);  # Alois P. Heinz, Mar 17 2019

Mathematica

Table[Sum[GCD@@ptn,{ptn,Select[IntegerPartitions[n],UnsameQ@@#&]}],{n,30}]
(* Second program: *)
b[n_, i_, r_] := b[n, i, r] = If[i(i+1)/2 < n, 0,
     With[{t = GCD[i, r]}, If[i < n, b[n - i, Min[i - 1, n - i], t], 0] +
     If[i == n, t, 0] + b[n, i - 1, r]]];
a[n_] := b[n, n, 0];
Array[a, 61] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

Formula

From Richard L. Ollerton, May 06 2021: (Start)

a(n) = Sum_{d|n} A000010(n/d)*A000009(d).

a(n) = Sum_{k=1..n} A000009(gcd(n,k)).

a(n) = Sum_{k=1..n} A000009(n/gcd(n,k))*A000010(gcd(n,k))/A000010(n/gcd(n,k)). (End)