[seqfan] Re: Subsets with prime sums

[Alois Heinz]

It is a nice problem.  Here are more terms of the sequence:

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

Maple program:

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..10);


Alois

zak seidov schrieb:
> I didn't mention that 
> all subsets are of length n,
> of course.
>
> Sorry,
> Zak
>
> %N A1
>   
>> For each n, take n subsets of set 1..n^2. 
>> Then select subsets with prime sums. 
>> The sequence gives the 
>> numbers of such subsets for n=2,3,4,5,6.
>>     
>
> --- On Sat, 10/24/09, zak seidov <zakseidov at yahoo.com> wrote:
>
>   
>> From: zak seidov <zakseidov at yahoo.com>
>> Subject: [seqfan]  Subsets with prime sums
>> To: "seqfaneu" <seqfan at seqfan.eu>
>> Date: Saturday, October 24, 2009, 11:31 AM
>> Dear seqfans,
>>
>> Pending your 
>> comments/editings/approvals/rejections/more_terms...
>>
>> Thanks, Zak
>>
>> %S A1 
>> 4,26,444,11998,382716
>>
>> N A1
>> For each n, take n subsets of set 1..n^2. 
>> Then select subsets with prime sums. 
>> The sequence gives the 
>> numbers of such subsets for n=2,3,4,5,6.
>>   
>> %e A1
>> n=2; a(2)=4 because there are four subsets of set {1,2,3,4}
>> with prime sums:
>> {1,2}=>3
>> {1,4}=>5
>> {2,3}=>5
>> {3,4}=>7
>>
>> n=3; a(3)=26 because there are 26 subsets of set
>> {1,2,3,4,5,6,7,8,9} 
>> {1,2,4},{1,2,8},{1,3,7},{1,3,9},{1,4,6},{1,4,8},{1,5,7},{1,7,9},{2,3,6},{2,3,8},{2,4,5},{2,4,7},{2,5,6},{2,6,9},{2,7,8},{2,8,9},{3,4,6},{3,5,9},{3,6,8},{3,7,9},{4,5,8},{4,6,7},{4,6,9},{4,7,8},{5,6,8},{6,8,9}
>> with corresponding prime sums:
>> {7,11,11,13,11,13,13,17,11,13,11,13,13,17,17,19,13,17,17,19,17,17,19,19,19,23}.
>>
>>