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,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Wikipedia, Partition (number theory)

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)

Maple

b:= proc(n, i, r) option remember; `if`(i*(i+1)/2<n, 0,
      (t-> `if`(i<n, b(n-i, min(i-1, n-i), t), 0)
      +`if`(i=n, t, 0)+b(n, i-1, r))(igcd(i, r)))
    end:
a:= n-> 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 *)

Crossrefs

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

Sequence in context: A155722 A049045 A153766 * A093013 A272999 A278490

Adjacent sequences: A319298 A319299 A319300 * A319302 A319303 A319304

Keyword

nonn

Author

Gus Wiseman, Sep 16 2018

Status

approved