A167147 a(n) = Number of subsets with n members of the set {1..n^2} such that the sum of the members is prime.

4, 26, 444, 11998, 382716, 15844060, 766387489, 42716991304, 2704983373484, 193042233338665, 15032959574223321, 1289808484211222447, 120472472277271660102, 12036408131864572935262, 1297010265532587186011353, 151499235341042432049982767, 18434494194245279115211501310, 2430305919107872967957571237320, 334200348422242729412526022526012

Offset

2,1

Comments

The sequence was conceived by Zak Seidov.

Further terms were calculated by Alois P. Heinz.

Links

Alois P. Heinz, Table of n, a(n) for n = 2..29

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+(1-t)/2)*t<n then 0
    else g(n, i-1, t) + g(n-i, i-1, t-1)
      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);
# Coded by Alois P. Heinz

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+(1-t)/2)*t < n, 0, True, g[n, i-1, t] + g[n-i, i-1, t-1]]; 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}] (* Jean-François Alcover, Oct 24 2016, after Alois P. Heinz *)

Crossrefs

Sequence in context: A317668 A328419 A194926 * A322395 A326264 A132488

Adjacent sequences: A167144 A167145 A167146 * A167148 A167149 A167150

Keyword

nonn

Author

Christopher Hunt Gribble, Oct 28 2009

Status

approved