Progetto Eulero
Si tratta di un contest di tipo matematico/informatico/enigmistico/a-tempo-perso, a cui si accede sul sito https://projecteuler.net
awk -v max=1000 'BEGIN{for(n=1;n<max;n++){if ((n%3)*(n%5)==0) sum+=n}print sum;}'
awk -v max=4000000 'BEGIN{a=1;b=1;while(b<max){r=b;b+=a;a=r;print a;if(a%2==0)sum+=a;}printf "total=%d",sum;}'
awk -v m=600851475143 'BEGIN{ a[0]=2; n=1; for(i=3;m>2;i++){ for(j=0;j<n;j++){ if(i%a[j]==0){ break; } } if(j==n){a[n]=i;n++; while(m%i==0){ printf "%d/%d=",m,i; m/=i; printf "%d\n",m; } } } }'
4 – Largest palindrome product
awk 'BEGIN{for(i=100;i<=999;i++)for(j=i+1;j<=999;j++) printf "%d %d %d\n",i,j,i*j;}'|\ awk '{k=$3; m=0;do{ N=k; k=int(N/10);a[m]=N-(k*10);m++;}while(k>0); if (m==5) if (a[0]==a[4] && a[1]==a[3]) {printf "%d %d %d\n",$1,$2,$3; p=($3>p)?$3:p;} if (m==6) if (a[0]==a[5] && a[1]==a[4] && a[2]==a[3]) {printf "%d %d %d\n",$1,$2,$3; p=($3>p)?$3:p;} }END{printf "\nThe largest palindrome is %d\n",p;}'
5 – Smallest multiple
1 * 2^4 * 3^2 * 5*7 * 11 * 13 * 17 *19 = 232792560
6 – Sum square difference
These two identity are founded easily solving a linear system of equations:
$S_1(N)=1 + 2 + 3 + … + N =\dfrac{N (N + 1)}{2}$
$S_2(N)=1 + 2^2 + 3^2 + … + N^2 =\dfrac{N (N + 1) (2N + 1)}{6}$
Then
$S_1^2(N)-S_2(N)=\dfrac{N (N^2 – 1) (3N + 2)}{12}$
awk -v m=10001 'BEGIN{ a[0]=2; n=1; for(i=3;;i++){ for(j=0;j<n;j++){ if(i%a[j]==0){ break; } } if(j==n){a[n]=i;n++;printf "%d %d\n",n,i; if(n==m)break;} }}'
8 – Largest product in a series
X=7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
awk -v x=$X 'BEGIN{ m=0; for(i=1;i<=length(x)-12;i++){ y=substr(x,i,13); p=1; for(j=1;j<=13;j++){p*=substr(y,j,1);} if(p>m)m=p; printf "%s %d\n",y,p; } printf "%d\n",m; }'
9 – Special Pythagorean triplet
awk 'BEGIN{for(a=1;a<=999;a++)for(b=a;b<=999;b++){ c=1000-a-b; if(c>0 && (a*a+b*b==c*c)) printf "%d %d %d -> %d+%d=%d -> %d\n",a,b,c,a*a,b*b,a*a+b*b,a*b*c;} }'
awk -v m=2000000 'BEGIN{ a[0]=2; n=1; s=a[0]; for(i=3;i<m;i++){ for(j=0;j<n;j++){ if(i%a[j]==0){ break; } } if(j==n){a[n]=i;s+=i;n++;printf "%d %d\n",n,i; } } printf "%d\n",s; }'
11 – Largest product in a grid
awk -v v=20 'BEGIN{i=0;j=0;}{a[i][j]=$1;j=j+1;if(j>v-1){j=0;i=i+1}}END{ max=0; for(i=0;i<v;i++){for(j=0;j<v-4+1;j++){n=a[i][j]*a[i][j+1]*a[i][j+2]*a[i][j+3];if(n>m)m=n;}} for(j=0;j<v;j++){for(i=0;i<v-4+1;i++){n=a[i][j]*a[i+1][j]*a[i+2][j]*a[i+3][j];if(n>m)m=n;}} for(i=0;i<v-4+1;i++){for(j=0;j<v-4+1;j++){n=a[i][j]*a[i+1][j+1]*a[i+2][j+2]*a[i+3][j+3];if(n>m)m=n;}} for(i=3;i<v;i++){for(j=3;j<v;j++){n=a[i][j]*a[i+1][j-1]*a[i+2][j-2]*a[i+3][j-3];if(n>m)m=n;}} printf "%d\n",m; }' list.txt
12 – Highly divisible triangular number
awk -v lim=500 'function D(x){ if(a[x]==0) { n=0; for(i=1;i<=x;i++)if(x%i==0)n++; a[x]=n; } return a[x]; }BEGIN{ for(k=0;;k++){d=(k%2==0)?(D(k/2)*D(k+1)):(D((k+1)/2)*D(k));if(d>lim)break;}j=(k+1)*k/2;printf "%d %d\n",j,d;}'
awk '{len=length($0);r=0; for(i=0;i<len;i++) { a[i]+=substr($0,len-i,1)+r;r=0; if(a[i]>=10){ a[i]-=10; r=1; } } if(n<len) n=len; for(;i<n;i++){ a[i]+=r;r=0; if(a[i]>=10){ a[i]-=10; r=1; } } if(r>0){a[n]+=r;n++;} for(i=n-1;i>=0;i--) printf "%d",a[i]; printf "\n";}' LargeSum.txt
awk -v lim=1000000 'BEGIN{ max=1;maxlen=1; for(i=2;i<lim;i++){ n=i;len=1; while(n!=1){n=(n%2==0)?n/2:3*n+1;len++;} if (len>maxlen){maxlen=len;max=i;} } printf "%d %d\n",max,maxlen;}'
awk -v n=837799 'BEGIN{printf "%d",n;while(n!=1){n=(n%2==0)?n/2:3*n+1;printf "->%d",n;}}'
awk 'BEGIN{ P[0]=2;P[1]=3;P[2]=5;P[3]=7;P[4]=11;P[5]=13;P[6]=17;P[7]=19;P[8]=23;P[9]=29;P[10]=31;P[11]=37; for(i=0;i<20;i++)A[i]=40-i; for(i=0;i<20;i++) for(k=0;k<12;k++) while(A[i]%P[k]==0){ A[i]/=P[k]; E[k]++; } for(i=0;i<20;i++)A[i]=i+1; for(i=0;i<20;i++) for(k=0;k<12;k++) while(A[i]%P[k]==0){ A[i]/=P[k]; F[k]++; } for(i=0;i<12;i++) X[i]=E[i]-F[i]; p=1; for(i=0;i<12;i++) if(X[i]>0)p*=P[i]^X[i]; printf "%d\n",p; }'
awk -v f=1000 'BEGIN{ a[0]=2; n=1;e=1; do{ for(i=0;i<n;i++){ R=(i>0)?r[i-1]:0; r[i]=(a[i]<5)?0:1; a[i]=R+((a[i]<5)?(2*a[i]):(2*(a[i]-5))); } if(r[n-1]>0){a[n]=r[n-1];n++} e++; }while(e<f); for(i=n-1;i>=0;i--) {printf "%d",a[i];s+=a[i];} printf " -> %d\n",s; }'
21124
awk 'BEGIN{ t[0][0]=75; t[1][0]=95;t[1][1]=64; t[2][0]=17;t[2][1]=47;t[2][2]=82; t[3][0]=18;t[3][1]=35;t[3][2]=87;t[3][3]=10; t[4][0]=20;t[4][1]=4;t[4][2]=82;t[4][3]=47;t[4][4]=65; t[5][0]=19;t[5][1]=1;t[5][2]=23;t[5][3]=75;t[5][4]=3;t[5][5]=34; t[6][0]=88;t[6][1]=2;t[6][2]=77;t[6][3]=73;t[6][4]=7;t[6][5]=63;t[6][6]=67; t[7][0]=99;t[7][1]=65;t[7][2]=4;t[7][3]=28;t[7][4]=6;t[7][5]=16;t[7][6]=70;t[7][7]=92; t[8][0]=41;t[8][1]=41;t[8][2]=26;t[8][3]=56;t[8][4]=83;t[8][5]=40;t[8][6]=80;t[8][7]=70;t[8][8]=33; t[9][0]=41;t[9][1]=48;t[9][2]=72;t[9][3]=33;t[9][4]=47;t[9][5]=32;t[9][6]=37;t[9][7]=16;t[9][8]=94;t[9][9]=29; t[10][0]=53;t[10][1]=71;t[10][2]=44;t[10][3]=65;t[10][4]=25;t[10][5]=43;t[10][6]=91;t[10][7]=52;t[10][8]=97;t[10][9]=51;t[10][10]=14; t[11][0]=70;t[11][1]=11;t[11][2]=33;t[11][3]=28;t[11][4]=77;t[11][5]=73;t[11][6]=17;t[11][7]=78;t[11][8]=39;t[11][9]=68;t[11][10]=17;t[11][11]=57; t[12][0]=91;t[12][1]=71;t[12][2]=52;t[12][3]=38;t[12][4]=17;t[12][5]=14;t[12][6]=91;t[12][7]=43;t[12][8]=58;t[12][9]=50;t[12][10]=27;t[12][11]=29;t[12][12]=48; t[13][0]=63;t[13][1]=66;t[13][2]=4;t[13][3]=68;t[13][4]=89;t[13][5]=53;t[13][6]=67;t[13][7]=30;t[13][8]=73;t[13][9]=16;t[13][10]=69;t[13][11]=87;t[13][12]=40;t[13][13]=31; t[14][0]=4;t[14][1]=62;t[14][2]=98;t[14][3]=27;t[14][4]=23;t[14][5]=9;t[14][6]=70;t[14][7]=98;t[14][8]=73;t[14][9]=93;t[14][10]=38;t[14][11]=53;t[14][12]=60;t[14][13]=4;t[14][14]=23; m=0; for(a=0;a<=16383;a++){ f=1; x=0;y=0;s=t[y][x]; while(y<15) {y++;x+=(and(a,f)==0)?0:1;s+=t[y][x];f*=2;} m=(s>m)?s:m; } printf "%d\n",m; }'
awk -v n=1100 'BEGIN{ for(i=1;i<=n;i++) a[i]=i; do{ flag=0; for(i=1;i<=n;i++){ if(a[i]%5==0){ for(j=1;j<=n;j++){ if(a[j]%2==0){ flag=1; a[i]/=5; a[j]/=2; f++; break; } } } } }while(flag==1); p[1]=1;lp=1; for(i=1;i<=n;i++){ if(a[i]>1){ for(j=1;j<=lp;j++){ p[j]*=a[i]; } for(j=1;j<=lp;j++){ if(p[j]>=10){ z=int(p[j]/10); p[j]-=(z*10); p[j+1]+=z; if(z>0 && j==lp) lp++; } } } } printf "%d!=",n; for(i=lp;i>0;i--){s+=p[i];printf "%d",p[i];} printf "x10^%d->%d\n",f,s; }'
awk -v max=10000 ' function SumDiv(loc_num) { loc_c=(loc_num>1)?1:0; loc_r=int(sqrt(loc_num))+1; for(loc_j=2;loc_j<loc_r;loc_j++){ if (loc_num%loc_j==0){ loc_q=(loc_num/loc_j); if (loc_j>loc_q) break; loc_c+=(loc_j<loc_q)?loc_j+loc_q:loc_j; } } return loc_c; } BEGIN{ for(n=1;n<max;n++){ a=SumDiv(n); b=SumDiv(a); if(n==b && a!=b){s+=n;printf "%d\n",n;} } printf "Total=%d\n",s; }'
awk '{AZ="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; n=split($0,a,","); asort(a); for(k=1;k<=n;k++){ l=length(a[k]); s=0; for(i=1;i<=l;i++){c=substr(a[k],i,1);ix=index(AZ,c);s=s+ix;}t+=(s*k);} printf "Total score = %d\n",t; }' p022_names.txt
awk -v max=28123 ' function SumDiv(loc_num) { loc_c=(loc_num>1)?1:0; loc_r=int(sqrt(loc_num))+1; for(loc_j=2;loc_j<loc_r;loc_j++){ if (loc_num%loc_j==0){ loc_q=(loc_num/loc_j); if (loc_j>loc_q) break; loc_c+=(loc_j<loc_q)?loc_j+loc_q:loc_j; } } return loc_c; } BEGIN{ printf "Ready... "; for(n=1;n<=max;n++){ a=SumDiv(n); if(a>n){list[n]=1;ab++;} } printf "Go!\n"; for(n=1;n<=max;n++){ for(k=1;k<=n;k++){ if(list[k]==1){ h=n-k; if(h>0 && list[h]==1){s+=n; ns++;break;} } } } printf "Abundant numbers = %d\n",ab; printf "Numbers sum of two Abundants = %d\n",ns; printf "Sum of Numbers sum of two Abundants = %d\n",s; }' echo "28123*(28123+1)/2-391285755"|bc
24 – Lexicographic permutations
awk -v c=1000000 -v n=10 'BEGIN{ c=c-1;f=1; for(i=0;i<n;i++){a[i]=i;f*=(i+1);} r=c; while(f>1){ f/=n; q=int(r/f); r=r%f; n--; printf "%d",a[q]; for(i=q;i<n;i++)a[i]=a[i+1];a[i]=0; } printf "%d\n",a[0]; }'
25 – 1000-digit Fibonacci number
awk 'BEGIN{ a[0]=1;na=1; b[0]=1;nb=1; z=(na>nb)?na:nb; k=2; while(z<=1000){ z=(na>nb)?na:nb; r=0; for(i=0;i<z;i++){ c=a[i]+b[i]+r; r=0; if(c>=10){r=1;c-=10;} a[i]=c; } na=z; if(r!=0){a[z]+=r;na=z+1;} k++; printf "n. %d ",k; for(i=na-1;i>=0;i--) printf "%d",a[i]; printf " -> %d\n",na; z=(na>nb)?na:nb; r=0; for(i=0;i<z;i++){ c=a[i]+b[i]+r; r=0; if(c>=10){r=1;c-=10;} b[i]=c; } nb=z; if(r!=0){b[z]+=r;nb=z+1;} k++; printf "n. %d ",k; for(i=nb-1;i>=0;i--) printf "%d",b[i]; printf " -> %d\n",nb; } }'
awk -v m=10000 'BEGIN{ maxp=0; maxd=0; for(d=1;d<=m;d++){ n=1; printf "%d/%d=",n,d; a=int(n/d); INT=a; i=0; while(1==1){ r=n%d;if(r==0) break; n=r*10; a=int(n/d); new=0; for(j=0;j<i;j++) if (R[j]==r){new=1;break;} if(new==1) break; f[i]=a; R[i]=r; i++; } printf "%d,",INT; for(k=0;k<j;k++) printf "%d",f[k]; if (new==1){ printf "("; for(k=j;k<i;k++) printf "%d",f[k]; printf ")\n"; if(maxp<(i-j)){ maxp=(i-j);maxd=d; } } else { for(k=j;k<i;k++) printf "%d",f[k]; printf "\n"; } } printf "Max Div=%d\n",maxd; }'
awk -v n=1 -v d=983 'BEGIN{ printf "%d/%d=",n,d; a=int(n/d); INT=a; i=0; while(1==1){ r=n%d;if(r==0) break; n=r*10; a=int(n/d); new=0; for(j=0;j<i;j++) if (R[j]==r){new=1;break;} if(new==1) break; f[i]=a; R[i]=r; i++; } printf "%d,",INT; for(k=0;k<j;k++) printf "%d",f[k]; if (new==1){ printf "("; for(k=j;k<i;k++) printf "%d",f[k]; printf ")\n"; if(maxp<(i-j)){ maxp=(i-j);maxd=d; } } else { for(k=j;k<i;k++) printf "%d",f[k]; printf "\n"; } }'
28 – Number spiral diagonals
Sum of Spiral=(4 n^3+3 n^2 + 8 n – 9)/6
awk -v r=1001 'BEGIN{ n=1;s=n; for(p=2;;p+=2){ for(i=0;i<4;i++){ n+=p; s+=n; } if (n>=r*r) break; } printf "%d\n",s; }'
awk 'BEGIN{for(i=2;i<9999999;i++) {p=0;for(j=1;j<=length(i);j++){p+=substr(i,j,1)^5;}if(i==p)printf "%d %d\n", i,p;}}'
awk ' function IsPandigital(locS) { if(length(locS)!=9) return 0; for(locI=1;locI<10;locI++){ if(match(locS,locI)==0) return 0; } return 1; } BEGIN{ n=0; for(c=1000;c<=9999;c++){ for(a=1;a<99;a++){ if(c%a==0){ b=c/a; s=sprintf("%d%d%d", a,b,c); if(IsPandigital(s)==1){ for(k=0;k<n;k++){ if(p[k]==c) break; } if(k==n){ sum+=c; p[n]=c; n++; printf "%dx%d=%d\n",a,b,c; } } } } } printf "sum=%d\n",sum; }'
awk 'BEGIN{ f[0]=1 for(i=1;i<10;i++){ f[i]=f[i-1]*i; } for(i=3;i<=100000;i++){ len=length(i); s=0; #printf "%d ",i; for(j=1;j<=len;j++) { c=substr(i,j,1); s+=f[c]; #printf "%d!=%d ",c,f[c]; } if(s==i)printf " %d\n",s; } }'
awk -v n=1000000 ' function Rotate(locN){ locL=length(locN); locE=1; locB=0; for(locI=locL;locI>1;locI--){ locM=substr(locN,locI,1); locE*=10; locB+=(locM*locE); } locB+=substr(locN,locI,1); return locB; } function InizializePrimeArray(locN) { p[0]=2;np=1; for(locI=3;locI<locN;locI+=2){ locP=1; for(locJ=0;locJ<locI && p[locJ]*p[locJ]<locI;locJ++){ if(locI%p[locJ]==0){ locP=0; break; } } if(locP==1){ p[np]=locI; np++; } } } function ValidNum(locN){ if (locN==2||locN==5) return 0; locL=length(locN); for(locI=1;locI<=locL;locI++){ if(substr(locN,locI,1)!="1"&&substr(locN,locI,1)!="3"&&substr(locN,locI,1)!="7"&&substr(locN,locI,1)!="9"){ return 1; } } return 0; } function IsPrime(locN) { if(locN<=1) return 0 locP=1; for(locJ=0;locJ<np;locJ++)if(locN!=p[locJ] && locN%p[locJ]==0){ locP=0;break; } return locP; } BEGIN{ InizializePrimeArray(int(sqrt(n))); for(i=2;i<n;i++){ if(ValidNum(i)==0){ g=i; if(IsPrime(g)==1){ waste=0; h=g; do{ h=Rotate(h); if(IsPrime(h)==0){waste=1;} }while(h!=g); if(waste==0){printf "%d\n",g;count++;} } } } printf "Count=%d\n",count; }'
awk ' function IsPandigital(locS) { if(length(locS)!=9) return 0; for(locI=1;locI<10;locI++){ if(match(locS,locI)==0) return 0; } return 1; } BEGIN{ for(n=2;n<=9;n++){ L=int(9/n); min=10^(L-1);max=10^(L); for(i=min;i<max;i++){ s=""; for(j=1;j<=n;j++){ m=j*i; s=sprintf("%s%d",s,m); } if(IsPandigital(s)==1) printf "1..%d x %i -> %s\n",n,i,s; } } }'
cat p042_words.txt| tr -d \"| tr -s \, \\n | \ awk 'BEGIN{k=0;a="ABCDEFGHIJKLMNOPQRSTUVWXYZ";} {n=0;for(i=1;i<=length($1);i++) n+=index(a,substr($1,i,1));t=0;for(i=1;i<25;i++){t+=i;if(n == t) {k++;printf "%s %d\n",$1,n;}}} END{print k;}'
46 – Goldbach’s other conjecture
awk -v n=10000 ' function InizializePrimeArray(locN) { p[0]=2;np=1; for(locI=3;locI<locN;locI+=2){ locP=1; for(locJ=0;locJ<locI && p[locJ]*p[locJ]<locI;locJ++){ if(locI%p[locJ]==0){ locP=0; break; } } if(locP==1){ p[np]=locI; np++; } } } function IsPrime(locN) { if(locN<=1) return 0 locP=1; for(locJ=0;locJ<np;locJ++)if(locN!=p[locJ] && locN%p[locJ]==0){ locP=0;break; } return locP; } BEGIN{ printf "Init...\n"; InizializePrimeArray(n); printf "Begin\n"; for(i=3;i<=n;i+=2) { if(IsPrime(i)==0){ conjecture=0; for(j=1;p[j]<i;j++){ q=(i-p[j])/2; sq=int(sqrt(q)); if(p[j]+2*sq*sq==i){ printf "%d=%d+2x%d^2\n",i,p[j],sq; conjecture=1; break; } } if(conjecture==0) { printf "%d false\n",i; break; } } } }'
awk -v n=100 ' function frac(loc_a,loc_b,loc_c){ loc_a=loc_a*loc_c+loc_b; b=loc_a; } function inv(loc_b,loc_c){ b=loc_c; c=loc_b; } BEGIN{ for(m=1;m<=n;m++){ v[0]=2; p=1; for(i=1;i<m;i++){ v[i]=(i%3==2)?2*p++:1; } b=1;c=v[m-1]; for(i=m-2;i>=1;i--){ a=v[i]; frac(a,b,c); inv(b,c); } a=v[0]; frac(a,b,c); printf "%.0f/%.0f=%f\n",b,c,b/c; } }'