Euler Projesi 239. Soru

Yirmi İki Aptalca Asal Sayı

1'den 100'e kadar numaralandırılmış bir dizi disk bir sıra halinde rastgele sıralanıyor.

Tam olarak 22 asal sayılı diskin doğal konumlarından başka yerde bulunacak şekilde kısmi bir bozulmayla sıralanması olasılığı nedir? (Asal sayılı olmayan disklerin herhangi bir kısmı kendi doğal konumlarında veya konumlarının dışında bulunabilir.)

Cevabınızı 0, abcdefghijkl şeklinde 12 ondalık basamağa kadar yuvarlayarak verin.
Cevap: 0.001887854841

C++:

public class Euler239 {
    public static void main(String[] args) {
        double[][] dp = new double[102][102];
        // dp[n][m] has the following meaning:
        // we need to put n+m items in a permutation
        // each of n items has one place on which it can't be put
        // m items can be put anywhere
        for (int n = 0; n <= 100; ++n) {
            for (int m = 0; m <= 100; ++m) {
                if (n == 0)
                    dp[n][m] = 1;
                else {
                    dp[n][m] = dp[n-1][m]*m/(n+m);
                    if (n > 1)
                        dp[n][m] += dp[n-2][m+1]*(n-1)/(n+m);
                }
            }
        }
        double res = 0;
        Sieve sieve = new Sieve(101);
        for (int i = 1; i <= 100; ++i) if (sieve.isPrime(i)) {
            for (int j = i+1; j <= 100; ++j) if (sieve.isPrime(j)) {
                for (int k = j+1; k <= 100; ++k) if (sieve.isPrime(k)) {
                    res += dp[22][75]/(100*99*98);
                }
            }
        }
        System.out.println(res);
    }
}

Maple:

d:=n->(-1)**n*sum((-1)**k*binomial(n,k)*k!,k=0..n); # permutation with no fixed point
phi:=proc(k,n) option remember;if k=n then d(k) elif k=1 then n-1 else phi(k,n-1)+k*phi(k-1,n-1) fi end: #injection from [1,k] to [1,n]
evalf(binomial(25,3)*phi(22,97)*75!/100!,20);

Mathematica:

h[n_,0]=n!;
h[n_,1]=(n-1)(n-1)!;
h[n_,p_]:=h[n-1,p-1](n-p)+Sum[h[n-p+i,i](p-1)!/i!(n-p+1),{i,0,p-2}]
Table[h[75+i,i]=h[75+i,i];,{i,0,22}];
SetAccuracy[(h[97,22]Binomial[25,3])/100!,13]

Python:

import math

#using third-party memorize technology(thanx to x10)

class memoize(object):
    def __init__(self,fun):
 self.memory={}
 self.fun=fun
    def __call__(self,*args):
 if args in self.memory: return self.memory[args]
 r=self.fun(*args)
 self.memory[args]=r
 return r
 

def isprime(x) :  
  if x <= 1 :
    return False
  if x < 4 :
    return True
  if x % 2 == 0 :
    return False
  if x < 9 :
    return True
  if x % 3 == 0 :
    return False
  
  r = int(math.sqrt(x))
  f = 5
  while f <= r :
    if x % f == 0 :
      return False
    if x % (f+2) == 0 :
      return False
    f += 6
  return True 


@memoize
def calc(p, n, hit) :
  if p <= 0 :
    if hit == 0 :
      return 1.0
    else :
      return 0.0

  # disk in empty place
  pr = (n - p) / n * calc(p-1, n-1, hit) 

  # disk in allowed position
  if p > 1 :   
    pr += (p - 1) / n * calc(p-2, n-1, hit)
  
  # disk in its native position
  if hit > 0 :   
    pr += 1 / n * calc(p-1, n-1, hit - 1)  

  return pr


pr = [x for x in range(100+1) if isprime(x)]
pc = len(pr)

print calc(pc, float(100), pc - 22)

C#:

// compute C(multiple,k)
static long Binomial(long n, long k)
 {
 checked
  {
  if (k > n)
   return 0;
  if (k > n / 2)
   k = n - k; // faster
  long accum = 1;
  for (long i = 1; i <= k; i++)
   accum = accum * (n - k + i) / i;
  return accum;
  }
 }
static public void Run(bool sample)
 {
 checked
  {
  double p = 0;
  for (int j = 1; j <= 22; ++j)
   {
   double d = (double)Binomial(22, j);
   for (int k = 1; k <= j; ++k)
    d /= 98 - k;
   if ((j & 1) == 0) p -= d; else p += d;
   }
  Console.WriteLine("{0}=0.001887854841", Binomial(25, 3) * (1 - p) / (100 * 99 * 98));
  }

Haskell:

numWays n 0 = factorial n
numWays n 1 = (n-1) * factorial (n-1)
numWays n d = ((d-1) * numWays (n-1) (d-2)) + ((n-d) * numWays (n-1) (d-1))

p239 = (fromIntegral (25 `choose` 22) * (numWays 97 22)) / (factorial 100)