Algorithme pour trouver le plus petit n tel que n! est divisible par une première élevée à une puissance

Pourquoi n'essayez-vous pas la recherche binaire de la réponse à l'aide de la deuxième formule que vous avez mentionnée?

Vous devez seulement envisager des valeurs pour N, pour lesquons que P divise N, car si cela ne le fait pas, alors n! et (n-1)! sont divisés par la même puissance de p, donc n ne peut pas être le plus petit.

OK c'est une sorte de plaisir.

Définir f (i) = (p ^ i-1) / (p - 1) p>

écrire k dans une sorte de "base" drôle où La valeur de la position I est celle-ci f (i). p>

Vous faites cela du chiffre le plus significatif au chiffre moins important. Donc, d'abord, trouvez le plus grand j tel que f (j)

Ceci génère une séquence q_j, q_ {j-1}, q_ {j-2}, ..., q_1. (Notez que la séquence se termine à 1, pas 0.) puis calculez q_j * p ^ j + q_ {j-1} * p ^ (j-1) + ... q_1 * p. C'est votre n. P>

Exemple: K = 9, P = 3. SO F (I) = (3 ^ I - 1) / 2. F (1) = 1, F (2) = 4 , f (3) = 13. Le plus grand j avec f (j)

Pour ce reste de 1, trouvez le quotient et le reste de 1 / F (1). Quotient est 1, le reste est zéro, donc nous sommes terminés. P>

donc q_2 = 2, q_1 = 1. 2 * 3 ^ 2 + 1 * 3 ^ 1 = 21, qui est la bonne N.

J'ai une explication sur papier pour la raison pour laquelle cela fonctionne, mais je ne suis pas sûr de savoir comment le communiquer dans le texte ... Notez que f (i) répond à la question "Combien de facteurs de p sont là dans (P ^ I)! ". Une fois que vous avez trouvé le plus grand i, j tel que J * F (I) est inférieur à K et réalisez ce que vous faites vraiment, c'est de trouver le plus grand j * p ^ i moins de N, le reste de la sorte de chute du lavage . Dans notre exemple p = 3, par exemple, nous obtenons 4 p versées par le produit de 1 à 9, 4 plus contribué par le produit de 10-18, et une autre contribution de 21. Ces deux premiers sont des multiples de p ^ 2; f (2) = 4 nous dit que chaque multiple de P ^ 2 contribue 4 autres p ^ 2 sur le produit. p>

[Mise à jour] p>

code aide toujours à clarifier. Enregistrez le script Perl suivant comme foo.pl code> et exécutez-le comme foo.pl

code>. Notez que ** code> est l'opérateur d'exponenciation de Perl, BDIV code> calcule un quotient et le reste pour les Bigints (entiers de précision illimités) et Utiliser Bigint code> dit à Perl Utiliser des grossications partout. P>

#!/usr/bin/env perl

use warnings;
use strict;
use bigint;

@ARGV == 2
    or die "Usage: $0 <p> <k>\n";

my ($p, $k) = map { Math::BigInt->new($_) } @ARGV;

sub f {
    my $i = shift;
    return ($p ** $i - 1) / ($p - 1);
}

my $j = 0;
while (f($j) <= $k) {
    $j++;
}
$j--;

my $N = 0;

my $r = $k;
while ($r > 0) {
    my $val = f($j);
    my ($q, $new_r) = $r->bdiv($val);
    $N += $q * ($p ** $j);
    $r = $new_r;
    $j--;
}

print "Result: $N\n";

exit 0;

considérer

i = (p ^{n )!}

et ignorer les facteurs premiers autres que p. Le résultat ressemble à

i = p ^{n * P n-1 * p n-2 ..... * p * 1
I = p n + (n-1) + (n-2) + ... 2 + 1
I = p (n 2 + n) / 2}

Nous essayons donc de trouver le plus petit n tel que

(n ^{2 + n) / 2> = k}

Que si je me souviens que le droit d'équation quadratique nous donne

n = p ^{n , où n> = (sqrt (1 + 8k) -1) / 2 de
de
de
(P.S. Est-ce que quelqu'un sait-il comment montrer le symbole radical de Markdown?)}

EDIT:

C'est faux. Permettez-moi de voir si je peux la récupérer ...