
EXAMPLE

When n=2, a(2) = 4 because there are 4 subsets of the set {1,2,3,4} with prime sums: {1,2}=>3, {1,4}=>5, {2,3}=>5, {3,4}=>7.
When n=3, a(3) = 26 because there are 26 subsets of the set {1,2,3,4,5,6,7,8,9} with prime sums: {1,2,4}=>7, {1,2,8}=>11, {1,3,7}=>11, {1,3,9}=>13, {1,4,6}=>11, {1,4,8}=>13, {1,5,7}=>13, {1,7,9}=>17, {2,3,6}=>11, {2,3,8}=>13, {2,4,5}=>11, {2,4,7}=>13, {2,5,6}=>13, {2,6,9}=>17, {2,7,8}=>17, {2,8,9}=>19, {3,4,6}=>13, {3,5,9}=>17, {3,6,8}=>17, {3,7,9}=>19, {4,5,8}=>17, {4,6,7}=>17, {4,6,9}=>19, {4,7,8}=>19, {5,6,8}=>19, {6,8,9}=>23.


MAPLE

g:= proc(n, i, t) option remember;
if n<0 or t<0 then 0
elif n=0 then `if`(t=0, 1, 0)
elif i<1 or i<t or (i+(1t)/2)*t<n then 0
else g(n, i1, t) + g(ni, i1, t1)
fi
end;
a:= proc(n) option remember;
add(`if`(isprime(k), g(k, min(k, n^2), n), 0), k=2..n^2*(n^2+1)/2)
end:
seq(a(n), n=2..13);


MATHEMATICA

g[n_, i_, t_] := g[n, i, t] = Which[n<0  t<0, 0, n == 0, If[t == 0, 1, 0], i<1  i<t  (i+(1t)/2)*t < n, 0, True, g[n, i1, t] + g[ni, i1, t1]]; a[n_] := a[n] = Sum[If[PrimeQ[k], g[k, Min[k, n^2], n], 0], {k, 2, n^2*(n^2 + 1)/2}]; Table[Print[a[n]]; a[n], {n, 2, 13}] (* JeanFrançois Alcover, Oct 24 2016, after Alois P. Heinz *)
