Choose 25 different positive integers no higher than fifty, such that none is a multiple of any of the others. What's the lowest total possible, and what's the set? (Note one such set would be 26 through 50 inclusive; however that set totals 950.)

(In reply to smallish by Jer)

The following program runs through all possibilities in under a millisecond:

int count=0, best=1000;
long long mask[51];
int bits(long long X) {
  int c;
  for(c=0; X; c++) X&=(X-1);
  return c;
}
void rec(long long S, int c, int n) {
  int i,d,s;
  long long T;
  for(i=n;i<=50;i++) if((S>>i)&1) {
    T=S&mask[i]; d=c-bits(T);
    if(d>=25) rec(S&~T,d,i+1);
    S&=~(1LL<<i); c--;
    if(c<25) return;
  };
  count++;
  for(s=0,i=1;i<=50;i++) if((S>>i)&1) s+=i;
  if(s<=best) {
    best=s;
    printf("sum=%i: S=",best);
    for(i=1;i<=60;i++) if((S>>i)&1) printf("%i,",i);
    printf("\n");
  }
}
int main() {
  int i,j;
  for(i=1;i<=50;i++) for(j=2*i;j<=50;j+=i) mask[i]|=(1LL<<j);  
  rec((1LL<<51)-2,50,1);
  printf("%i solutions\n",count);
}

Output:
sum=711: S=8,12,14,17,18,19,20,21,22,23,25,26,27,29,30,31,33,35,37,39,41,43,45,47,49,
1632 solutions

Edited on February 12, 2009, 12:36 pm

Posted by Eigenray on 2009-02-12 12:19:46