Hohe Fakultät nicht möglich?

[negaH]

Wollten wir nun die Exponenten schon gekürzt für 10! / (6! - 4!) errechnen also direkt auf 2^2 * 3^2 * 5^1 * 7^1 kommen dann geht das so

Delphi-Quellcode:

  function FindEP(K,L,N,P: Cardinal): Cardinal;
  // extract exponents to base P, where P is prime
  var
    E: Cardinal;
  begin
    E := 0;
    while K >= P do
    begin
      N := N div P;
      L := L div P;
      K := K div P;
      Inc(E, N - L - K);
    end;
    while L >= P do
    begin
      N := N div P;
      L := L div P;
      Inc(E, N - L);
    end;
    while N >= P do
    begin
      N := N div P;
      Inc(E, N);
    end;
    Result := E;
  end;

P ist unsere Primzahlbasis,
N dann 10
L dann 6
K dann 4


nun rufen wir für die Primzahlen 3,5,7 obige Funktion auf und bekommen

3^2 * 5^1 * 7^1 * 2^((N - L - K) - (BitCount(N) - BitCount(L) - BitCount(K)) <- ergibt 2^2

Man kann also mit 32 Bit Operationen sehr effizient und auf direktem Wege die Potenzschreibweise des Binomials ausrechnen und erreicht somit den mathematisch kürzesten Weg um das Binomial auszurechnen. Es gibt kein mir bekanntes Verfahren das effizienter und schneller zu berechnen wäre. Besoinderst wenn es sich um sehr große Binomiale, Fakultäten, das Produkt oder die Permutation handelt.

Übrigens mit obiger Funktion kann man auch zb. die Frage beantworten wieviele 0 Stellen am Ende der Fakultät,Binomial,Produkt,Permutation zu einer Basis diese haben.
Möchte man zb. wissen wie oft 10! durch zb. 2 oder 5 oder 10 (2*5) teilbar ohne Rest ist so kann man obige Funktion benutzen.

Man kann damit zb. die Potenzschreibweise von bis zu 4294967295! ausrechnen dazu benötigen wir nur die Primzahlen bis 4294967295.

Gruß Hagen