Euler Projesi 231. Soru

Binom Katsayıların Asal Çarpanlara Ayrılması

Binom katsayısı ¹⁰C₃ = 120.
120 = 2³ × 3 × 5 = 2 × 2 × 2 × 3 × 5 ve 2 + 2 + 2 + 3 + 5 = 14.
Böylece ¹⁰C₃ binom katsayısının asal çarpanlara ayırmasındaki terimler toplamı 14.

  ^20000000C_15000000 binom katsayısının asal çarpanlara ayırmasındaki terimler toplamı kaçtır?

Cevap: 7526965179680

Python:

import math

nmax = 20000000

primes = nmax*[True]

primes[0:2] = [False,False]

for x in range(2, int(math.sqrt(len(primes)) + 1)):
    if primes[x]:
        for y in range(2 * x, len(primes), x):
            primes[y] = False

p = [x for x in range(len(primes)) if primes[x]]

s = 0

n = 20000000
m = 15000000

def x(n, p):
    c = 0
    while n:
        n //= p
        c += n
    return c

s = 0

for i in p:
    s += i * (x(n, i) - x(m, i) - x(n - m, i))

print(s)

C++:

#include <cstdlib>
#include <iostream>

using namespace std;

bool* primes;

long long int* div_cnt;

void sieve(){
     primes[0] = false;
     primes[1] = false;
     int i;
     for (i=2;i<20000001;i++){
         primes[i]=true;
     }
     for (i=2;i<4475;i++){
         if (primes[i]){
            int j = i*i;
            while (j<20000001){
                  primes[j] = false;
                  j += i;
            }
         }
     }
}

void factor_p(int i){
     while ((i & 1) == 0 ){
           div_cnt[2]++;
           i >>= 1;
     }
     int j = 3;
     while ( !primes[i] & (i>1)){
           while (i % j == 0){
                 div_cnt[j] ++;
                 i = i/j;
           }
           j +=2;
           while (!primes[j]){
               j +=2;   
           }           
     }
     if (i>1){
        div_cnt[i]++;
     }
}

void factor_m(int i){
     while ((i & 1) == 0 ){
           div_cnt[2]--;
           i >>= 1;
     }
     int j = 3;
     while ( !primes[i] & (i>1)){
           while (i % j == 0){
                 div_cnt[j] --;
                 i = i/j;
           }
           j +=2; 
           while (!primes[j]){
               j +=2;   
           }          
     }
     if (i>1){
        div_cnt[i]--;
     }     
}

int main(int argc, char* argv[])
{
    primes = (bool*) malloc (sizeof(bool)*20000001);
    sieve();
    std::cout << "sieve done " << std::endl;
    
    div_cnt = (long long int*)malloc (sizeof(long long int)*20000001);
    
    int i;
 for (i=0;i<20000001;i++){
  div_cnt[i] = 0;
 }
    for (i=15000001;i<20000001;i++){
        factor_p(i);
        if (i%1000==0){std::cout << "factor_p i=" << i << std::endl;}
    }
    for (i=2;i<5000001;i++){
        factor_m(i);
        if (i%1000==0){std::cout << "factor_m i=" << i << std::endl;}
    }
    
    long long int sum = 0;
    long long ii;
    for (ii=0;ii<20000001;ii++){
        sum +=ii*div_cnt[ii];
        
    }
    
    std::cout << "sum = " << sum << std::endl;
    
    free(primes);
    system("PAUSE");
    return EXIT_SUCCESS;
}

Java:

        public static int[] primes = new int[1280000];
 
 public static int amount = 0;
 
 public static long getPrimeAmount(long p, long n) {
  long a = 0;
  long m = p;
  
  while (m <= n) {
   a += n / m;
   m *= p;
  }

  return a;
 }
 
 public static void factor(int n, int k) {
  
  long sum = 0;
  
  for (int i=0; i<amount; i++) {
   if (primes[i] > n) {
    break;
   }
   
   long a_n = getPrimeAmount(primes[i], n);
   long k_n = getPrimeAmount(primes[i], k);
   long ak_n = getPrimeAmount(primes[i], n-k);
   
   long t = a_n - k_n - ak_n;
   
   sum += t*primes[i];
  }
  
  System.out.println(sum);
 }

Maple:

with(numtheory):test:=proc(n)
> local t,k,som,i;
> t:=ifactors(n)[2];
> k:=nops(t);
> som:=0;
> for i from 1 to k do
>   som:=som+t[i][1]*t[i][2];
> od;
> som
> end:


> res:=proc(a,b)
> local som,i;
> som:=0;
> q:=0;
> for i from b+1 to a do
> som:=som+test(i);
> od;
> for i from 2 to a-b do
> som:=som-test(i);
> od;
> som
> end:


> t:=time():res(2*10^7,15*10^6);time()-t;

Haskell:

import qualified FactorSieve 

m = 20 * 10^6
n = 15 * 10^6

array  = FactorSieve.sieve m
factor = FactorSieve.factor array

prop_example = factor 360 == [(2,3),(3,2),(5,1)]

sumTerms = sum . map (uncurry (*)) . factor

answer = sum (map sumTerms [n + 1 .. m]) - sum (map sumTerms [1..m-n])

main = print answer

Delphi:

procedure TForm1.Button5Click(Sender: TObject);
const n=200000000;k=150000000;n_k=n-k;
var  i,h,t:integer;sum:int64;
start,stop,freq:int64;
begin
queryperformancecounter(start);
queryperformancefrequency(freq);

primesieve.init_sieve(n);
sum:=0;

i:=primesieve.nextprime(1);
while i<=n do
begin
t:=0;
h:=n;
while h>=i do begin h:=h div i;inc(t,h) end;
h:=k;
while h>=i do begin h:=h div i;dec(t,h) end;
h:=n_k;
while h>=i do begin h:=h div i;dec(t,h) end;
inc(sum,t*i);

i:=primesieve.nextprime;
end;
memo1.lines.add(inttostr(sum));
queryperformancecounter(stop);
memo1.lines.add(floattostr((stop-start)/freq*1000));
end;