In the past week, I’ve run an experiment with ChatGPT to answer the question: Is it feasible to use Chatbots to ease and accelerate the writing of computer code to search for answers to very hard combinatorial problems? From my experience so far over five days, I’m inclined to say yes. The problem I decided to work on involves sets S of integers contained in {1,2,3… n} with the property that no three integers x, y, z in S satisfy x < y < z and y-x = z-y, or in other words x , y, z form a three-term arithmetic progression. Sets with this property are variously known as Salem-Spencer sets and non-averaging sets. There is a Wikipedia article on the subject here https://en.wikipedia.org/wiki/Salem%E2%80%93Spencer_set . The collaboration with the chatbot involved writing Python and C code to test sets for being non-averaging and for finding dense non-averaging sets. I wasn’t following any book or article, however I used the Online Encyclopedia of Integer Sequences to verify the results of the computations, in particular sequence A065825 at https://oeis.org/A065825 .
My role was mostly to guide the software development, acting as an architect. ChatGPT has a vast store of knowledge on computer science topics and can be counted upon to produce good but not faultless code. It has happened before that the computer programs written by ChatGPT at my behest have become almost beyond my capacity, and still not satisfactory. The results are modest, but likely more than I could have done on my own in the same timeframe. Maximal-sized sets were found for n up to 122, yielding, for example, a 32-element non-averaging set contained in {1, 2, 3, … 122}.
Currently, the efforts are going into finding dense non-averaging sets with 33 elements. This can be done for n as low as 137 (per OEIS), but our program is nowhere near that result. I’ve been reading a survey paper and a journal article by William Gasarch et al , the paper being entitled “Finding Large 3-free Sets I: The Small n Case” [1] It serves as inspiration and motivation to consider writing more efficient programs. I’m providing the source code of the most current version of the C program, spencer509a.c which to me demonstrates ChatGPT’s expertise with C, data structures and the OpenMP parallel computing platform.
[1] Gasarch, W., Glenn, J., & Kruskal, C. P. (2008). Finding large 3-free sets I: The small n case. Journal of Computer and System Sciences, 74(4), 628-655. https://doi.org/10.1016/j.jcss.2007.06.002
#include <stdio.h>
#include <omp.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h> // Include for uint64_t
#define CHUNK_SIZE 20
#define PROB_BACKTRACK 0.100
// #define PROB_BACKTRACK 0.0074
// #define MAX_NUMBER 148
#define MAX_NUMBER 160
#define MAX_SIZE 33
#define ATTEMPTS 10000
#define BITSET_PARTS 3
static unsigned long long x=1234567890987654321ULL,c=13456123456123456ULL, y=362436362436362436ULL,z=1066149217761810ULL,t;
#define MWC (t=(x<<58)+c, c=(x>>6), x+=t, c+=(x<t), x)
#define XSH ( y^=(y<<13), y^=(y>>17), y^=(y<<43) )
#define CNG ( z=6906969069LL*z+1234567 )
#define KISS (MWC+XSH+CNG)
long int allocations = 0;
long int deallocations = 0;
long int creations = 0;
long int iterations = 0;
int delta = 0;
int globalIdx[192];
int globalBit[192];
int A065825[44] = {0,1, 2, 4, 5, 9, 11, 13, 14, 20, 24, 26, 30, 32, 36, 40, 41, 51, 54, 58, 63, 71, 74, 82, 84, 92, 95, 100, 104, 111, 114, 121, 122, 137, 145, 150, 157, 163, 165, 169, 174, 194, 204, 209};
int idx_array[192];
uint64_t bit_array[192];
// Define BitSet struct
typedef struct {
uint64_t parts[BITSET_PARTS]; // Assuming each part is 64 bits to cover up to 192 elements
} BitSet;
// ... Rest of your code ...
typedef struct Node {
BitSet members; // BitSet representing the members of the Salem-Spencer set
BitSet legal; // BitSet representing which numbers are legal to add
struct Node* parent; // Pointer to the parent node
int set_size; // Number of elements in the set
} Node;
void initialize_globals() {
for (int i = 0; i < 192; i++) {
globalIdx[i] = i / 64;
globalBit[i] = i % 64;
}
}
void set_clear(BitSet *set) {
for (int i = 0; i < sizeof(set->parts) / sizeof(set->parts[0]); i++) {
set->parts[i] = 0; // Set all bits to 0
}
}
/********************************************************************
bool set_contains(const BitSet *set, int element) {
if (element < 1 || element > 192) {
// Element out of bounds
return false;
}
int idx = (element - 1) / 64; // Determine which part of the array to check
int bit = (element - 1) % 64; // Determine which bit within the part to check
return (set->parts[idx] & (1ULL << bit)) != 0; // Check if the bit is set
}
**************************************************************************************/
/***********************************************************
bool set_contains(const BitSet *set, int element) {
if (element < 1 || element > 192) {
return false;
}
int idx = globalIdx[element - 1];
int bit = globalBit[element - 1];
return (set->parts[idx] & (1ULL << bit)) != 0;
}
***********************************************************/
bool set_contains(const BitSet *set, int element) {
if (element < 1 || element > 192) {
return false;
}
element--; // Adjust for 0-based indexing in the array
return (set->parts[idx_array[element]] & bit_array[element]) != 0;
}
void set_add(BitSet *set, int element) {
if (element < 1 || element > 192) {
// Element out of bounds
return;
}
int idx = (element - 1) / 64; // Determine which part of the array to modify
int bit = (element - 1) % 64; // Determine which bit within the part to set
set->parts[idx] |= (1ULL << bit); // Set the bit
}
void set_remove(BitSet *set, int element) {
if (element < 1 || element > 192) {
// Element out of bounds
return;
}
int idx = (element - 1) / 64; // Determine which part of the array to modify
int bit = (element - 1) % 64; // Determine which bit within the part to unset
set->parts[idx] &= ~(1ULL << bit); // Unset the bit
}
void update_legal_bitset(Node* node, int new_member) {
if (new_member < 1 || new_member > 192) {
// New member out of bounds
return;
}
// Iterate over all current members of the set
#pragma omp parallel
{
int thread_id = omp_get_thread_num(); // Get current thread number
int num_threads = omp_get_num_threads(); // Total number of threads
int items_per_thread = 192 / num_threads;
int remainder = 192 % num_threads;
// Distribute remainder among the first 'remainder' threads
int start = thread_id * items_per_thread + (thread_id < remainder ? thread_id : remainder);
int end = start + items_per_thread + (thread_id < remainder);
#pragma omp critical
for (int i = start; i < end; i++) {
// Your logic for each case
// #pragma omp critical
if (!set_contains(&node->members, i)) {
continue;
}
// Check all possible arithmetic progressions involving 'new_member' and 'i'
int ap_member;
// Case 1: new_member is the middle term (i, new_member, ap_member)
ap_member = 2 * new_member - i;
if (ap_member >= 1 && ap_member <= 192) {
set_remove(&node->legal, ap_member);
// set_remove(&node->legal, ap_member);
}
// Case 2: i is the middle term (ap_member, i, new_member)
ap_member = 2 * i - new_member;
if (ap_member >= 1 && ap_member <= 192) {
set_remove(&node->legal, ap_member);
// set_remove(&node->legal, ap_member);
}
// Case 3: new_member and i are ends of the progression (new_member, ap_member, i)
if ((new_member + i) % 2 == 0) {
ap_member = (new_member + i) / 2;
set_remove(&node->legal, ap_member);
// set_remove(&node->legal, ap_member);
}
}
}
/********************************************************************************************
#pragma omp parallel for
for (int i = 1; i <= 192; i++) {
if (!set_contains(&node->members, i)) {
continue;
}
// Check all possible arithmetic progressions involving 'new_member' and 'i'
int ap_member;
// Case 1: new_member is the middle term (i, new_member, ap_member)
ap_member = 2 * new_member - i;
if (ap_member >= 1 && ap_member <= 192) {
#pragma omp critical
set_remove(&node->legal, ap_member);
// set_remove(&node->legal, ap_member);
}
// Case 2: i is the middle term (ap_member, i, new_member)
ap_member = 2 * i - new_member;
if (ap_member >= 1 && ap_member <= 192) {
#pragma omp critical
set_remove(&node->legal, ap_member);
// set_remove(&node->legal, ap_member);
}
// Case 3: new_member and i are ends of the progression (new_member, ap_member, i)
if ((new_member + i) % 2 == 0) {
ap_member = (new_member + i) / 2;
#pragma omp critical
set_remove(&node->legal, ap_member);
// set_remove(&node->legal, ap_member);
}
}
}
******************************************************************************************/
}
void print_hexadecimal(const BitSet *set) {
int hexDigits = BITSET_PARTS * 16; // Each 64-bit part has 16 hex digits
// Iterate through each part from the last to the first
for (int partIdx = BITSET_PARTS - 1; partIdx >= 0; partIdx--) {
uint64_t part = set->parts[partIdx];
// Print each hex digit of the part
for (int hexIdx = 15; hexIdx >= 0; hexIdx--) {
int hexDigit = (part >> (hexIdx * 4)) & 0xF; // Extract 4 bits
printf("%01X", hexDigit);
// Print a space every 4 hex digits for grouping
if (hexIdx % 4 == 0 && !(partIdx == 0 && hexIdx == 0)) {
printf(" ");
}
}
}
printf("\n");
}
Node* create_initial_node() {
Node* node = malloc(sizeof(Node)); // Allocate memory for a new node
allocations++;
creations++;
// printf("just allocated memory for a root\n");
// printf("%ld creations\n", creations);
if (node == NULL) {
// Handle memory allocation failure
fprintf(stderr, "Failed to allocate memory for a new node\n");
return NULL;
}
// Initialize the members BitSet to represent an empty set
set_clear(&node->members);
// Initialize the legal BitSet to represent all numbers as legal
for (int i = 0; i < sizeof(node->legal.parts) / sizeof(node->legal.parts[0]); i++) {
node->legal.parts[i] = ~0ULL; // Set all bits to 1
}
// Initially, the node has no parent and the set is empty
node->parent = NULL;
node->set_size = 0; // Initialize set size to 0
// printf("This is function create_initial_node and I am about to return\n");
return node;
}
void copy_node(Node* dest, Node* src) {
if (dest == NULL || src == NULL) {
return;
}
// Copy members and legal BitSet
for (int i = 0; i < sizeof(src->members.parts) / sizeof(src->members.parts[0]); i++) {
dest->members.parts[i] = src->members.parts[i];
dest->legal.parts[i] = src->legal.parts[i];
}
// Copy set size
dest->set_size = src->set_size;
}
void print_set(Node* node) {
if (node == NULL) {
return;
}
printf("{");
bool first = true;
for (int i = 1; i <= 192; i++) {
if (set_contains(&node->members, i)) {
if (!first) {
printf(", ");
}
printf("%d", i);
first = false;
}
}
printf("}");
}
// Function to free a node
void free_node(Node* node) {
if (node) {
// Print the content in hexadecimal format before freeing
// printf("Freeing node with set: ");
// print_hexadecimal(&node->members);
// printf("\n");
// Free the node and any dynamically allocated resources within
free(node);
deallocations++;
}
}
void shuffle(int *array, int n) {
// Go through the array elements from the end to the beginning
for (int i = n - 1; i > 0; i--) {
// Pick a random index from 0 to i
int j = rand() % (i + 1);
// Swap array[i] with the element at the random index
if(j>0)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
Node* create_child_node(Node* parent) {
Node* child = malloc(sizeof(Node));
creations++;
// printf("%ld creations\n", creations);
allocations++;
// printf("Just allocated memory for a child node\n");
// printf("allocations = %ld deallocations = %ld\n", allocations, deallocations);
if (child == NULL) {
fprintf(stderr, "Failed to allocate memory for child node\n");
return NULL;
}
// Copy the BitSet states from the parent to the child
child->members = parent->members; // You might need to implement a function to copy BitSets
child->legal = parent->legal; // Same as above, implement if needed
// Link the child to its parent
child->parent = parent;
child->set_size = parent->set_size; // The child initially has the same set size as the parent
return child;
}
Node* fill_to_capacity(Node* parent_node, int max_number) {
int numbers[MAX_NUMBER];
// Fill the array with numbers from 1 to max_number
for (int i = 0; i < max_number; i++) {
numbers[i] = i + 1;
}
// Shuffle the numbers array
if (1 )
{
shuffle(numbers, max_number);
// shuffle(numbers, max_number);
// shuffle(numbers, max_number);
}
Node* current_node = parent_node; // Start with the parent node
/*********************************************************************************************************************
// Attempt to add each shuffled number to the set
for (int i = 0; i < max_number; i++) {
int num = numbers[i];
if (set_contains(¤t_node->legal, num) && !set_contains(¤t_node->members, num)) {
**********************************************************************************************************************/
// and now after finding a new number to add to the set, we do a so-called futility check
// current numbers plus newly found in total is: current_node->set_size + 1
// remaining slots to fill with more numbers is:
// MAX_NUMBER - num
// check that:
// A065825(MAX_SIZE - (current_node->set_size + 1)) <= ( MAX_NUMBER - num)
// if so, then proceed as usual or previously
// if not, abandon the job of fill_to_capacity and proceed to quit function
// return value: as if num not added
// Attempt to add each shuffled number to the set
for (int i = 0; i < max_number; i++) {
int num = numbers[i];
if (set_contains(¤t_node->legal, num) && !set_contains(¤t_node->members, num)) {
// Futility check
int currentSize = current_node->set_size + 1;
int correction = 0;
// Assuming 'currentSet' is an array representing the current Salem-Spencer set
// and 'currentSize' is the number of elements currently in the set
for (int j = 1; j <= 192; j++) {
if (set_contains(¤t_node->members, j)) {
if(j>num)
{
correction++;
}
}
}
// Now you can use 'correction' in your condition
/**********************************************************************
if (A065825[MAX_SIZE - currentSize] > (remainingSlots - correction)) {
// Break or other logic
}
*****************************************************************************/
int remainingSlots = MAX_NUMBER - num;
if((double)KISS / (double)18446744073709551615 < 0.5)
{
if(delta<0)
{
delta = delta + 1;
}
}
else
{
if(delta > 10)
{
delta = delta - 1;
}
}
// if (A065825[MAX_SIZE - currentSize] > remainingSlots) {
if (A065825[MAX_SIZE - currentSize] > (delta+remainingSlots - correction)) {
// If futility check fails, abandon this branch
break;
}
// Proceed as usual if futility check passes
// ... rest of your code for adding the number to the set ...
// Create a new child node as a copy of the current node
Node* child_node = create_child_node(current_node);
set_add(&child_node->members, num);
child_node->set_size = current_node->set_size + 1; // Increment set size
update_legal_bitset(child_node, num);
current_node = child_node; // Move to the child node
} // end of if set_contains etc
}
// Return value as if num not added
return current_node;
/**************************************************************************************
}
}
return current_node; // Return the last node created (or the parent node if no additions)
**************************************************************************************************/
}
Node* backtrack_node(Node* node, int chunk_size) {
// Check if the node is NULL or has no parent (root node)
if (node == NULL || node->parent == NULL) {
return node; // Return the current node as no backtracking is possible
}
Node* current = node;
Node* to_free = NULL;
for (int i = 0; i < chunk_size; i++) {
// If the current node has no parent, stop backtracking
if (current->parent == NULL) {
break;
}
// Mark the current node to be freed
to_free = current;
// Move to the parent node
current = current->parent;
// Free the marked node
free_node(to_free);
deallocations++;
}
// Return the node reached after backtracking
// printf("This is backtrack_node about to return...\n");
// printf("allocations = %ld deallocations = %ld\n", allocations, deallocations);
return current;
}
int countSetBits(const BitSet *set) {
int count = 0;
for (int i = 0; i < MAX_NUMBER; i++) {
int idx = i / 64;
int bit = i % 64;
if (set->parts[idx] & (1ULL << bit)) {
count++;
}
}
return count;
}
int main() {
srand(time(NULL));
Node* record_node = create_initial_node();
int record_size = 0;
int chunk_size = CHUNK_SIZE;
double prob_backtrack=PROB_BACKTRACK;
int is_futile;
initialize_globals();
for (int i = 0; i < 192; i++) {
idx_array[i] = i / 64;
bit_array[i] = 1ULL << (i % 64);
}
for (int i = 0; i < ATTEMPTS; i++) {
Node* current_node = create_initial_node(); // Start new attempt
while (iterations<10000000) {
iterations++;
// ... After updating the set with a new member ...
int currentSize = current_node->set_size;
int availableSlots = countSetBits(¤t_node->legal); // Count the available slots within the first MAX_NUMBER bits
// Futility check
if (MAX_SIZE - currentSize > availableSlots) {
// This branch is futile, handle accordingly
is_futile = 1;
}
else
{
is_futile = 0;
}
if(is_futile == 0)
{
current_node = fill_to_capacity(current_node, MAX_NUMBER);
if (current_node->set_size >= 31) {
// Record new record
record_size = current_node->set_size;
// copy_node(record_node, current_node);
// Print the new record set
printf("New record: Size of Salem-Spencer set = %d\n", record_size);
printf("{");
print_set(current_node); // Assuming print_set function correctly prints the set
printf("}\n");
printf("allocations: %ld\n", allocations);
printf("deallocations: %ld\n", deallocations);
printf("delta=%d\n", delta);
fflush(stdout);
if(record_size == MAX_SIZE)
{
printf("Maximum size found, exiting\n");
return 0;
}
break; // Start new attempt
}
if ((double)KISS / (double)18446744073709551615 < prob_backtrack) {
// current_node = backtrack_node(current_node, chunk_size);
}
}
else
{
current_node = backtrack_node(current_node, chunk_size);
// while ((double)KISS / (double)18446744073709551615 < prob_backtrack) {
// current_node = backtrack_node(current_node, chunk_size);
// }
}
// free_node(current_node); // Free tree from this attempt
} // if is_futile == 0
printf("iterations = %ld\n", iterations);
printf("prob = %lf\n", prob_backtrack);
printf("chunk_size = %d\n", chunk_size);
printf("delta = %d\n", delta);
prob_backtrack = prob_backtrack + 0.0001L;
if((double)KISS / (double)18446744073709551615 < 0.5)
{
if(chunk_size<19)
{
chunk_size = chunk_size + 1;
}
}
else
{
if(chunk_size > 8)
{
chunk_size = chunk_size - 1;
}
}
iterations = 0;
}
free_node(record_node); // Free record node
return 0;
}
/****************************************************************************
int main() {
srand(time(NULL));
Node* record_node = create_initial_node();
int record_size = 0;
for (int i = 0; i < ATTEMPTS; i++) {
Node* current_node = create_initial_node(); // Start new attempt
while (true) {
current_node = fill_to_capacity(current_node, MAX_NUMBER);
if (current_node->set_size > record_size) {
// Record new record
record_size = current_node->set_size;
copy_node(record_node, current_node);
print_new_record(record_node);
break; // Start new attempt
}
if ((double)rand() / RAND_MAX < PROB_BACKTRACK) {
current_node = backtrack_node(current_node, CHUNK_SIZE);
}
}
free_node(current_node); // Free tree from this attempt
}
free_node(record_node); // Free record node
return 0;
}
**************************************************************************/
/*****************************************************************************************************************
int main() {
srand(time(NULL));
Node* record_node = create_initial_node(); // Function to create an initial node
Node* root_node;
int record_size = 0;
printf("CHUNK_SIZE = %d\n", CHUNK_SIZE);
printf("PROB_BACKTRACK = %.3f\n", PROB_BACKTRACK);
for (int i = 0; i < ATTEMPTS; i++) { // Start of for loop
Node* current_node = create_initial_node(); // Create a new node for each attempt
root_node = current_node;
current_node = fill_to_capacity(current_node, MAX_NUMBER);
if (current_node->set_size > record_size) { // Start of if block for new record
record_size = current_node->set_size;
copy_node(record_node, current_node); // Function to copy the node's state
printf("New record: Size of Salem-Spencer set = %d\n", record_size);
printf("allocations - deallocations = %ld . set size=%d\n", allocations-deallocations, current_node->set_size);
// Print the new record set
printf("New record: Size of Salem-Spencer set = %d\n", record_size);
printf("{");
print_set(record_node); // Assuming print_set function correctly prints the set
printf("}\n");
printf("allocations: %ld\n", allocations);
printf("deallocations: %ld\n", deallocations);
fflush(stdout);
} // End of if block for new record
if (current_node->set_size <= record_size) { // Start of if block for backtracking
current_node = backtrack_node(current_node, CHUNK_SIZE); // Function to backtrack
while ((double)KISS / (double)18446744073709551615 < PROB_BACKTRACK) { // Start of while loop
current_node = backtrack_node(current_node, CHUNK_SIZE);
} // End of while loop
fill_to_capacity(current_node, MAX_NUMBER);
} // End of if block for backtracking
free_node(root_node); // Function to free the memory of the node
deallocations++;
} // End of for loop
free_node(record_node); // Free the memory of the record node
deallocations++;
return 0;
} // End of main function
*************************************************************************************************/