// gcc -O3 -o gen010 gen010.c #include #include #include #include #include #include int mot[1000000], code[100000], mot2[1000000]; int i, j, s, k, size, x, nb, mnb, pos, lim, w; void date(){ fflush(stdout); system("date \"+\%d/\%m/\%Y \%H/\%M/\%S\""); } int forb(int *m, int i, char *ch){ int a, x, l = i+1; x = strlen(ch); if(l < x) return 0; for(a = 0; a < x && m[l-x+a] == ch[a]-'0'; a++); return a == x; } int req(int *g, int *d, int l){ int x = 0; for(; l--; x++) if(g[l] != d[x]) return 0; return 1; }//*/ int rrep3(int *m, int i){ int x, y, lon = 2, a, l = i+1; if(i && m[i] == m[i-1]) return 1;// forbids aa if(i > 1 && m[i]+m[i-1]+m[i-2] == 1) return 1;// forbids 010 if(forb(m, i, "01201")) return 1; if(forb(m, i, "0210120")) return 1; if(forb(m, i, "0201210120210")) return 1; if(forb(m, i, "0120210121020")) return 1; if(forb(m, i, "01202102012101")) return 1; if(forb(m, i, "10121020120210")) return 1; if(forb(m, i, "120121021202101")) return 1; if(forb(m, i, "201202120121020")) return 1; if(forb(m, i, "012021020121021201")) return 1; if(forb(m, i, "102120121020120210")) return 1; if(forb(m, i, "10121020120212012101")) return 1; if(forb(m, i, "012021020120212012101")) return 1; if(forb(m, i, "202120121012021020120")) return 1; if(l >= w) for(a = 0; a <= l-w ; a++) if(req(m+a, m+l-w, w)) return 1;// checks if w-directed for(; (x = (7*lon)/4) <= i; lon++){ for(y = i-lon; (y >= 0) && (m[y] == m[y+lon]); y--); if(i-y > x) return 1; } return 0; }//*/ int rrep4(int *m, int i){ int x, y, lon = 1; for(; (x = (7*lon)/5) <= i; lon++){ for(y = i-lon; (y >= 0) && (m[y] == m[y+lon]); y--); if(i-y > x) return 1; } return 0; }//*/ int ok(){ if(mnb < nb) {printf("nb=%d ", mnb = nb); date("");} for(*code = x = 0; ;) if(rrep4(code, x)){ ici: while(code[x] == nb-1) if(!x--) return 1; code[x]++; }else{ s = nb-1-code[x];//optimized version //s = code[x];//old version for(k = 0; k < size; k++){ mot2[pos = k+x*size] = mot[k+s*size]; if(x && rrep3(mot2, pos)) return 0; } if(x == lim-1) goto ici; else code[++x] = 0; } } int other(){ if(i < size) return 1; //if(i%size < 489 && mot[i] != mot[i-size]) return 0; for(k = i-i%size; k <= i; k++) if(mot[k] < mot[k-size]) break; else if(mot[k] > mot[k-size]){ i -= i%size+1; return 0; } if(i < 2*size) return 1; for(k = 0; k <= i%size; k++) mot2[size+k] = mot[i-i%size+k]; for(k = 0; k < i/size-1; k++){ for(j = 0; j < size; j++) mot2[j] = mot[k*size+j]; if(rrep3(mot2, size+i%size)) return 0; } return 1; } int A(){ mnb = nb = 0; printf("size=%d w=%d lim=%d ", size, w, lim); date(""); for(*mot = i = 0; ;) if(rrep3(mot, i) || !other()){ here: while(mot[i] == 2) if(!i--) return 1; mot[i]++; }else if((!((i+1)%size)) && ((nb = (i+1)/size) > 1)) if(!ok()) goto here; else if(nb == 4) break; else goto there; else there: mot[++i] = 0; for(x = 0; x < 4; x++, printf("\n")) for(k = 0; k < size; k++) printf("%d", mot[k+x*size]); printf("OK size=%d w=%d lim=%d ", size, w, lim); date(""); return 0; } void usage(){ printf("Usage: ./gen010 size w lim\n"); exit(0); } int main(int ac, char **av){ if(ac != 4) usage(); size = atoi(av[1]); w = atoi(av[2]); lim = atoi(av[3]); for(; A() && size < 2000; size++); } /* execution where line 83 is uncommented to get a long common prefix: this is the morphism in the paper ochem@ochem-2022:~/mots/motif45$ gcc -O3 -o gen010 gen010.c && ./gen010 1557 180 9 size=1557 w=180 lim=9 15/07/2023 22/26/29 nb=2 15/07/2023 22/27/15 nb=3 15/07/2023 22/27/19 nb=4 15/07/2023 22/29/31 012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121012021020121021202101210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201210120212012102012021012102120210201210212012101202102012021201210212021020120210121021201210201202120121012021020121021202101210201202120121021202102012021012102120121012021020120212012102120210201210120212012102012021012102120210201202120121012021020121021202101210201202120121021202102012101202120121020120210121021201210120210201210212021012102012021201210212021020120210121021201210201202120121012021020121021202101210201202120121021202102012101202120121020120210121021201210120210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212012101202102012102120210121020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212021020120212012101202102012102120210121020120212012102120210201210120212012102012021 012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121012021020121021202101210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201210120212012102012021012102120210201210212012101202102012021201210212021020120210121021201210201202120121012021020121021202101210201202120121021202102012021012102120121012021020120212012102120210201210120212012102012021012102120121012021020121021202101210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201210120212012102012021012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021202102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212012101202102012102120210121020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212021020120212012101202102012102120210121020120212012102120210201210120212012102012021 012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121012021020121021202101210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201210120212012102012021012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021202102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212012101202102012102120210121020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212012101202102012102120210121020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212012101202102012021201210212021020120210121021201210201202120121012021020121021202101210201202120121021202102012021012102120121012021020120212012102120210201210120212012102012021012102120210201202120121012021020121021202101210201202120121021202102012101202120121020120210121021202102 012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121012021020121021202101210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201210120212012102012021012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021201210120210201210212021012102012021201210212021020120210121021201210201202120121012021020121021202101210201202120121021202102012101202120121020120210121021202102012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021202102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212012101202102012102120210121020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212012101202102012021201210212021020120210121021201210201202120121012021020121021202101210201202120121021202102012021012102120121012021020120212012102120210201210120212012102012021012102120210201202120121012021020121021202101210201202120121021202102012101202120121020120210121021202102 OK size=1557 w=180 lim=9 16/07/2023 02/39/08 execution where line 83 is commented: this is how a first morphism of length 1557 is found ochem@ochem-2022:~/mots/motif45$ gcc -O3 -o gen010 gen010.c && ./gen010 1557 180 9 size=1557 w=180 lim=9 16/07/2023 16/40/41 nb=2 16/07/2023 16/41/04 nb=3 16/07/2023 16/41/41 nb=4 16/07/2023 16/42/41 012021012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201210120212012102012021012102120210201202120121012021020121021202101210201202120121021202102012021012102120121012021020120212012102120210201210120212012102012021012102120210201210212012101202102012021201210212021020120210121021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012101202120121020120210121021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020120212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201210120212012102012021012102120210201210212012101202102012021201210212021020121012021201210201202101210212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121012021020121021202101210201202120121021202102012101202120121020120210121021202102012102120121012021020120212012102120210201210120212012102 012021012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121020120212012101202102012102120210121020120212012102120210201210120212012102012021012102120210201202120121012021020121021202101210201202120121021202102012021012102120121012021020120212012102120210201210120212012102012021012102120210201210212012101202102012021201210212021020120210121021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012101202120121020120210121021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021202102012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012101202120121020120210121021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020120212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121012021020121021202101210201202120121021202102012101202120121020120210121021202102012102120121012021020120212012102120210201210120212012102 012021012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121012021020121021202101210201202120121021202102012101202120121020120210121021202102012021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021202102012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012101202120121020120210121021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020120212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121012021020121021202101210201202120121021202102012101202120121020120210121021202102012102120121012021020120212012102120210201210120212012102012021012102120121012021020121021202101210201202120121021202102012021012102120121012021020120212012102120210201210120212012102012021012102120210201210212012101202102012021201210212021020120210121021201210201202120121012021020121021202101210201202120121021202102012101202120121020120210121021202102012102120121012021020120212012102120210201210120212012102 012021012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212012101202102012102120210121020120212012102120210201202101210212012101202102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012021012102120121012021020121021202101210201202120121021202102012101202120121020120210121021202102012021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021202102012102120121012021020120212012102120210201202101210212012102012021201210120210201210212021012102012021201210212021020121012021201210201202101210212021020121021201210120210201202120121021202102012101202120121020120210121021201210120210201210212021012102012021201210212021020120210121021201210120210201202120121021202102012101202120121020120210121021202102012102120121012021020120212012102120210201202101210212012101202102012102120210121020120212012102120210201210120212012102012021012102120210201210212012101202102012021201210212021020121012021201210201202101210212012101202102012102120210121020120212012102120210201210120212012102012021012102120210201202120121012021020121021202101210201202120121021202102012021012102120121012021020120212012102120210201210120212012102012021012102120210201210212012101202102012021201210212021020120210121021201210201202120121012021020121021202101210201202120121021202102012101202120121020120210121021202102012102120121012021020120212012102120210201210120212012102 OK size=1557 w=180 lim=9 16/07/2023 16/51/20 */