Euler Projesi 203. Soru

Binom katsayıları ⁿC_k üçgensel formda (Pascal üçgeni) aşağıdaki şekilde düzenlenebilir:

							1
						1		1
					1		2		1
				1		3		3		1
			1		4		6		4		1
		1		5		10		10		5		1
	1		6		15		20		15		6		1
1		7		21		35		35		21		7		1

.........

İlk 8 sırada görüldüğü üzere 12 farklı sayı bulunmaktadır: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 ve 35.

Bir n pozitif tamsayısı herhangi bir asal sayının karesi ile tam bölünmüyorsa bu n sayısına kare-serbest sayı denir. Pascal üçgeninin ilk 8 sırasında yer alan farklı 12 sayıdan, 4 ve 20 hariç, 10 tanesi kare-serbest sayılardır ve bu kare-serbest sayıların toplamı 105 dir.

Pascal üçgeninin ilk 51 sırasında yer alan farklı kare-serbest sayıların toplamı kaçtır?

Cevap: 34029210557338

 Maple:

with(numtheory):

s:={1}:
for i to 50 do
 for j to i-1 do
  k:=binomial(i,j):
  if(mobius(k)<>0) then
    s:=s union {k}:
  end if:
 end do:
end do:

add(s[i],i=1..nops(s));

C/C++:

struct SPrimes
{
   enum{N=50};
   int* ap;
   unsigned int ixCurrent;
   unsigned int ixMax;
   SPrimes(unsigned int max=N)
   {
      if (max < 1000) max=1000;
      ap = new int[(ixMax=max)+1];
      ap[ixCurrent=0] = 2;
      ap[++ixCurrent] = 3;
      int ix = 5;
      int ani = 0;
      while (1)
      {
         if (isPrime(ix))
         {
            ap[++ixCurrent] = ix;
            if (ixCurrent >= ixMax)
               break;
         }
         ix += 2 + 2*(ani++ & 1);
      }
      printf(" found %d primes until ix=%d\n", ixCurrent, ix);
   }
   ~SPrimes()
   {
      delete [] ap;
   }
   int isPrime(unsigned __int64 number)
   {
      int ix = 0;
      int sqr = sqrt((__int64)number)+1;
      int divisor = ap[ix++];
      __int64 n = number;
    while (divisor < sqr) {
     if (0 == (n % divisor)) {
      return 0;
     }
         divisor = ap[ix++];
    }
      return 1;
   }
   int isSquareFree(__int64 num)
   {
      int ix = 0;
      while (ix < ixCurrent)
      {
         int divisor = ap[ix++];
         divisor *= divisor;
         if ((num%divisor) == 0)
            return 1;
      }
      return 0;
   }
};
__int64 n[1400]={1};
__int64* p[52]={&n[0]};
std::set<__int64> objNumbers;
SPrimes objPrimes;
int main(int argc, char**argv)
{
   int ix = 1;
   int ipx = 1;
   int nx = 1;
   __int64* px;
   __int64* ppx = p[0];
   objNumbers.insert(1);
   while (ix < 51)
   {
      px = &n[nx];
      p[ix] = px;
      int ixx = 0;
      px[ixx++] = 1;
      while (ixx < ix)
      {
         __int64 n = ppx[ixx-1]+ppx[ixx];
         px[ixx++] = n;
         if (!objPrimes.isSquareFree(n))
            objNumbers.insert(n);
      }
      px[ixx++] = 1;
      ppx = px;
      nx += ixx;
      ++ix;
   }
   std::set<__int64>::iterator itx = objNumbers.begin();
   unsigned __int64 sum = 0;
   while (itx != objNumbers.end())
   {
      __int64 n = (*itx);
      sum += n;
      ++itx;
   }
   printf("sum=%I64u\n", sum);
   return 0;
}

Java:

public Problem_203()
{
    long[][] arr = new long[51][51];
    long sum = 0;
    for ( int a = 0; a < arr.length; ++a )
        for ( int b = 0; b < arr[a].length; ++b )
            arr[a][b] = b == 0 ? 1 : 0;
    for ( int a = 1; a < arr.length; ++a )
        for ( int b = 1; b <= a; ++b )
            arr[a][b] = arr[a - 1][b - 1] + arr[a - 1][b];
    for ( int a = 0; a < arr.length; ++a )
        for ( int b = 0; b < arr[a].length; ++b )
        {
            for ( int c = 0; c <= a; ++c )
                for ( int d = 0; d <= (c == a ? b - 1 : c); ++d )
                    arr[a][b] = arr[a][b] == arr[c][d] ? 0 : arr[a][b];
            for ( long c = 2; c * c <= arr[a][b]; ++c )
                arr[a][b] = arr[a][b] % (c * c) == 0 ? 0 : arr[a][b];
            sum += arr[a][b];
        }
    System.out.print(sum + "\n");
}