Depth-first search
From Polymath Wiki
Jump to navigationJump to search
The C program below executes a depth-first search. It was written quickly without much regard for user-friendliness, so requires some explanation.
Compile the program, say to an executable called 'erdos'. Then execute:
erdos erdos1.log erdos2.log
Choose the names of the log files as you please. Important output (maximum-length sequences) goes to your console and to erdos2.log; some further information about how far it's tracked back, and so on, goes in erdos1.log. I generally follow erdos1.log in a separate console window while the program is running.
You will want to modify some bits and pieces in the code. Set C_min and C_max to the minimum and maximum values allowed for the partial sums (e.g. -2 and 2). Set 'OPTIMIZE' to 1 if you want to use the [math]\displaystyle{ (p, q) }[/math]-optimization trick: this only works if C_min=-2 and C_max=2 and you haven't got any additional constraints. Set N to the limit of your search. Set N_TO_COUNT to the length you want to count instances of -- e.g. to count the number of 1124-length sequences you find, set it to 1124.
Further down there is an EXCLUDE macro, where you set the constraints. You can see the format from the code that's there. These are conditions for rejection. Note that these should be constraints on the x[i] for i<=n: don't put something like x[n]==x[2*n] here or it won't work.
Further down still, the declaration of init_x is set to the initial value for the search.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#ifndef _WIN32
# include <stdbool.h>
#else
# define bool char
# define true 1
# define false 0
#endif
#define OPTIMIZE 0
#define N 1200 // limit of search
#define C_min -2 // limit on sums
#define C_max 2 // limit on sums
#define N_TO_COUNT 1124
static unsigned int s[N+1][N+1];
static unsigned int l[N+1];
static void print_seq(FILE *fp, char *seq, unsigned int n) {
unsigned int j;
fprintf(fp, "\n ");
for (j = 1; j<=n; j++) {
fprintf(fp, "%s", (seq[j] == 1) ? "+" : "-");
if (j%60==0) fprintf(fp, "\n ");
}
fprintf(fp, "\n");
}
static bool check(char *seq, unsigned int n) {
bool ok = true;
unsigned int d = 1;
while ((d <= n) && ok) {
unsigned int i = d;
char tot = 0;
while ((i <= n) && ok) {
tot += seq[i];
if ((tot<C_min) || (tot>C_max)) ok = false;
i += d;
}
d++;
}
return ok;
}
#define EXCLUDE \
((n%3==0) && (x[n]==x[n/3])) || \
((n%5==0) && (x[n]==-x[n/5]))// || \
// ((n%7==0) && (x[n]==x[n/7]))// || \
// ((n%11==0) && (x[n]==x[n/11])) || \
// ((n%13==0) && (x[n]==-x[n/13]))
int main(int argc, char *argv[]) {
FILE *fp, *fp1;
struct tm *local;
time_t tt;
bool is_prime[N+1];
char t[N+1][N+1];
char x[N+1];
char x_ref[N+1];
unsigned int n, max_n, min_back, max_fwd;
unsigned long kk;
#if OPTIMIZE
bool tracking = false; // whether I'm tracking from a prime to check for symmetry
unsigned int tracking_p = 0; // base prime for tracking
char tracking_sign = 0;
#endif
bool hope;
const char init_x[689] = {
0, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, +1, -1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, +1, -1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, -1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, +1, -1, +1, +1, +1, -1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, +1, -1, +1, -1, +1, -1, +1, +1, -1, -1, -1, +1, -1, +1, +1, -1, -1, +1, +1, -1, +1, -1, +1, +1, -1, +1, -1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, +1, -1, -1, -1, +1, +1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, -1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, +1, -1, +1, -1, -1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, +1, +1, -1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, -1, +1, +1, +1, -1, +1, -1, -1, -1, +1, +1, -1, +1, -1, -1, +1, -1, +1, +1, +1, +1, -1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, +1, +1, -1, -1, -1, -1, +1, +1, -1, +1, +1, -1, -1, -1, +1, +1, +1, -1, -1, +1, -1, -1, +1, +1, +1, -1, -1, -1, +1, +1, -1, +1, +1, +1, -1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, +1, -1, -1, -1, -1, +1, +1, +1, -1, -1, +1, +1, -1, +1, -1, +1, +1, -1, -1, -1, +1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, +1, +1, -1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, +1, -1, -1, -1, +1, -1, -1, +1, -1, +1, +1, +1, -1, -1, +1, -1, +1, -1, +1, +1, -1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, +1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, -1, +1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, +1, +1, -1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, -1, -1, -1, +1, +1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, -1, +1, +1, +1, -1, -1, -1, -1, +1, -1, +1, +1, -1, -1, +1, +1, +1, +1, -1, +1, -1, -1, +1, -1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, +1, -1, +1, -1, +1, -1, -1, -1, +1, +1, +1, +1, -1, +1, -1, -1, -1, +1, +1, -1, +1, -1, -1, +1, +1, +1, -1, -1, -1, +1, -1, +1, +1, -1, +1, +1, -1, -1, +1, -1, -1, +1, +1, -1, -1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, +1, -1, +1, +1, +1, -1, -1, -1, -1, +1, +1, +1, -1, +1, -1, +1, +1
};
const unsigned int init_x_max = 688;
{ // initialize divisors table (s), lengths vector (l) and is_prime vector
unsigned int n, d;
for (n = 0; n <= N; n++) {
unsigned int d_count = 0;
for (d = 1; d <= N; d++) {
if ((n%d) == 0) {
s[n][d_count] = d;
d_count++;
}
}
l[n] = d_count;
is_prime[n] = (d_count == 2);
}
}
{ // initialize coordinates vector (x)
unsigned int i;
for (i = 0; i <= init_x_max; i++) x[i] = init_x[i];
for (i = init_x_max+1; i <= N; i++) x[i] = 1;
}
{ // set x_ref = x
unsigned int i;
for (i = 0; i <= N; i++) x_ref[i] = x[i];
}
{ // initialize totals table (t)
unsigned int n, d;
for (n = 0; n <= N; n++) {
for (d = 0; d <= N; d++) t[n][d] = 0;
}
t[1][1] = x[1];
}
fp = fopen(argv[1], "w");
fp1 = fopen(argv[2], "w");
kk = 0;
n = 2;
max_n = 2;
hope = true;
min_back = 2;
max_fwd = 2;
while ((n <= N) && hope) { // require that t[m][d] is correct for all m<n, d|m
bool ok = true;
unsigned int i = 0;
if (n < min_back) { // record new track-back limit
min_back = n;
max_fwd = min_back;
tt = time(NULL);
local = localtime(&tt);
fprintf(fp, "\n************\n%smaximum = %d\n", asctime(local), max_n);
fprintf(fp, "found %lu sequences of length %d\n", kk, N_TO_COUNT);
fprintf(fp, "backtracked to %d ... checking ...\n", n);
}
#if OPTIMIZE
if ((!tracking) && (n > N/3) && is_prime[n] && (x[n]==x_ref[n]) && (t[n-1][1]==0)) {
tracking = true;
tracking_p = n;
tracking_sign = x[n];
}
if (tracking && is_prime[n] && (x[n]==-tracking_sign)) { // track back to tracking_p and reverse value there
while (n > tracking_p) {
x[n] = x_ref[n];
n--;
}
x[n] = -x_ref[n];
tracking = false;
}
#endif
while ((i < l[n]) && ok) {
unsigned int d = s[n][i];
char tot = t[n-d][d] + x[n];
#if OPTIMIZE
if (tracking && (d==1) && (tot==-tracking_sign)) tracking = false;
#endif
if ((tot<C_min) || (tot>C_max) || (EXCLUDE)) ok = false;
else {
t[n][d] = tot;
i++;
}
if (!ok) {
if (x[n] == x_ref[n]) {
x[n] = -x_ref[n];
i = 0;
ok = true;
}
}
}
if (ok) {
if (n > max_fwd) { // set and record new max_fwd
max_fwd = n;
fprintf(fp, "%d ... ", n);
fflush(fp);
}
if (n==N_TO_COUNT) kk++;
if (n > max_n) { // update maximum and print sequence
max_n = n;
min_back = n;
fprintf(fp1, "length: %d\n", n);
fprintf(fp1, "x: ");
print_seq(fp1, x, n);
fprintf(stdout, "length: %d\n", n);
fprintf(stdout, "x: ");
print_seq(stdout, x, n);
fprintf(stdout, "verify: %s\n", check(x, n) ? "pass" : "fail");
}
n++;
}
else { // track back
while ((n > 0) && (x[n] == -x_ref[n])) {
x[n] = x_ref[n];
n--;
}
x[n] = -x_ref[n];
#if OPTIMIZE
if (n<=tracking_p) tracking = false;
#endif
if (n == 1) hope = false;
}
}
fprintf(fp, "END\n");
if (hope) { // reached N successfully: print final sequence
fprintf(fp, "N = %d\n", N);
fprintf(fp, "x: ");
print_seq(fp, x, N);
fprintf(fp, "check: %s\n", check(x, N) ? "pass" : "fail");
}
else fprintf(fp, "fail\n");
fprintf(fp, "found %lu sequences of length %d\n", kk, N_TO_COUNT);
fclose(fp);
fclose(fp1);
}
