/******************************************************************************
Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.
*******************************************************************************/
#include <stdio.h>
#include <time.h>
// 5 16 23 43 76 127 210 (minimum size needed for solutions in 3-tuples through 9-tuples)
#define size 256 // number of evens/odds to search, size N allows for numbers from 1 to 2N
// 256 is maximum without extending the _bits arrays
int is_prime[1024];
// unsigned long should be 64-bit, use uint64_t if necessary
unsigned long all_bits[size][4];
unsigned long and_bits[10][4];
int group[10];
int best_count=9; // set to minimum length of desired solutions
int solutions;
void find_best(int pos); // recursive search
int popcount(unsigned long x); // unused bit-summation function (implemented in-line)
int main()
{
int i,j,e,o;
unsigned long b;
time_t t1,t2;
is_prime[0]=is_prime[1]=0;
for(i=2;i<1024;i++)is_prime[i]=1;
for(i=2;i<1024;i++){
if(is_prime[i]==1){
for(j=i*i;j<1024;j+=i)is_prime[j]=0;
}
}
for(i=0,o=1;i<size;i++,o+=2){
for(j=0;j<4;j++)all_bits[i][j]=0;
for(j=0,e=2,b=1;j<size;j++,e+=2,b<<=1){
if(b==0)b=1;
if(is_prime[o+e]==1){
all_bits[i][j/64]|=b;
}
}
}
t1=time(NULL);
// beginning of search, restrict the range of the loop variable for partial search
// run i=5;i<6 with size 210 for quick output of least-max 9-tuple solutions
for(i=0;i<size;i++){
group[0]=i;
for(j=0;j<4;j++)
and_bits[0][j]=all_bits[i][j];
find_best(1);
}
t2=time(NULL);
printf("%d %ld %ld",solutions,clock(),t2-t1);
return 0;
}
void find_best(int pos){
int i,j,n;
unsigned long bit, mask=15;
for(i=group[pos-1]+1;i<size;i++){
group[pos] = i;
for(j=n=0;j<4;j++){
and_bits[pos][j] = and_bits[pos-1][j] & all_bits[i][j];
// n+=popcount(and_bits[pos][j]); (for loop replaces function call)
for(bit=and_bits[pos][j];bit;n++)bit&=bit-1;
}
if(n>pos){
if(pos<9)find_best(pos+1);
if(pos+1>=best_count){
if(pos+1==best_count)solutions++;
else solutions=1;
best_count=pos+1;
printf("%d: ",best_count);
for(j=0;j<=pos;j++)printf("%d ",2*group[j]+1);
printf("| ");
for(j=0,bit=1;j<size;j++,bit<<=1){
if(bit==0)bit=1;
if((and_bits[pos][j/64] & bit)==bit)printf("%d ",j+j+2);
}
printf(" (%d) %ld\n",solutions,clock());
}
}
}
}
int popcount(unsigned long x){
int count;
for(count=0;x;count++)
x&=x-1;
return count;
}
