Autore: franzpizzo

Progetto Eulero

Si tratta di un contest di tipo matematico/informatico/enigmistico/a-tempo-perso, a cui si accede sul sito https://projecteuler.net

1 – Multiples of 3 and 5

awk -v max=1000 'BEGIN{for(n=1;n<max;n++){if ((n%3)*(n%5)==0) sum+=n}print sum;}'

2 – Even Fibonacci numbers

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;}'

3 – Largest prime factor

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}$

7 – 10001st prime

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;}
}'

10 – Summation of primes

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;}'

13 – Large sum

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

14 – Longest Collatz sequence

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;}}'

15 – Lattice paths

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;
}'

16 – Power digit sum

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;
}'

17 – Number letter counts

21124

18 – Maximum path sum I

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;
}'

19 – Counting Sundays

20 – Factorial digit sum

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;
}'

21 – Amicable numbers

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;
}'

22 – Names scores

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

23 – Non-abundant sums

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;

  }
}'

26 – Reciprocal cycles

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;
}'

30 – Digit fifth powers

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;}}'

32 – Pandigital products

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;
}'

34 – Digit factorials

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;
}
}'

35 – Circular primes

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;
}'

38 – Pandigital multiples

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;
		}
	}
}'

42 – Coded triangle numbers

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;
      }
    }
  }
}'

65 – Convergents of e

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;
  }
}'