找到最小的N使得N！可以被一個素數整除

是否有一個有效的算法來計算最小的整數N，使得N！可以被p^k整除，其中p是一個相對小的素數，k是一個非常大的整數。換句話說，找到最小的N使得N！可以被一個素數整除

factorial(N) mod p^k == 0

如果給定的n和p，我想求P多少次劃分成N個！我會使用衆所周知的公式

k = Sum(floor(N/p^i) for i=1,2,...

我已經做了蠻力搜索k值很小，但隨着k的增加，這種方法很快就會崩潰，而且似乎沒有一種模式可以推斷出較大的值。由五元美鈔和哈馬提出

編輯的2011年6月13日

使用的建議，我用了一個半二進制搜索來解決這個問題，但以這樣的方式不太他們建議。使用上面第二個公式的截斷版本，我計算了N的上界作爲k和p的乘積（僅使用第一項）。我用1作爲下界。使用經典的二分搜索算法，我計算了這兩個值之間的中點，並計算了第二個公式中將使用此中點值作爲N的k值，這次是使用所有項。

如果計算的k太小，我調整了下限並重復。太大了，我首先測試看中間點1計算的k是否小於所需的k。如果是這樣，中點返回爲最接近的N.否則，我調整了高點並重復。

如果計算出的k相等，我測試了中點-1的值是否等於中點的值。如果是這樣，我將高點調整爲中點並重復。如果中點-1小於期望的k，則中點返回爲期望的答案。

即使k值非常大（10位或更多位），該方法也可以運行O（n log（n））速度。

來源

2011-06-13 sizzzzlerz

即使尼莫的答案不是很清楚，我相信它比二分查找更好。畢竟，它是O（1）！或者，更確切地說，因爲你必須處理數字，所以它是O（log k）。這個問題是可以直接解決的，所以不需要做一些迭代計算。 – Fezvez 2011-06-13 17:51:42

最好將自己的問題回答回答，而不是對問題的編輯。 – ThomasMcLeod 2011-06-13 18:53:10

「10位或更多位」不是「非常大」:-)。我編輯了我的答案來添加一個Perl實現。即使對於數十位數字的k，似乎也能正常工作，但我不知道答案是否正確。如果你能找到一個能夠給出錯誤答案的案例，我希望看到它。 – Nemo 2011-06-13 23:47:03

使用您提到的公式，給定固定值p和N = 1,2...的k值的順序是非遞減的。這意味着您可以使用二進制搜索的變體找到N給定所需的k。

以N = 1開頭，並計算出k。
Double N直到k大於或等於您想要的k以獲得上限。
在剩餘的時間間隔進行二進制搜索以找到您的k。

來源

2011-06-13 01:34:11 hammar

爲什麼不嘗試使用您提到的第二個公式進行二分法搜索？

您只需要考慮N的值，其中p除以N，因爲如果它不是，那麼N！和（N-1）！除以p的相同冪，所以N不能是最小的一個。

來源

2011-06-13 01:41:53

好吧，這很有趣。

定義F（1）=（P^I - 1）/（P - 1）的一類有趣的「鹼」的，其中的位置i的值是這樣的F（1）

寫ķ。

你可以從最重要的數字到最不重要的數字。所以首先找到最大的j，使得f（j）< = k。然後計算k/f（j）的商和餘數。將商存儲爲q_j，將餘數存儲爲r。現在計算r/f（j-1）的商和餘數。將商存儲爲q_ {j-1}，餘數再次存儲爲r。現在計算r/f（j-2）的商和餘數。等等。

這產生序列q_j，q_ {j-1}，q_ {j-2}，...，q_1。（注意，序列在1結束，而不是0）。然後計算q_j * p^j + q_ {j-1} * p ^（j-1）+ ... q_1 * p。那就是你的N =

例如：k = 9，p = 3所以f（i）=（3^i-1）/2f(1)=1,f（2）= 4，f 3）= 13。因此，當f（j）< = 9時，最大的j是i = 2，f（2）= 4。取商數和9/4的餘數。這是一個2的商（這是我們2的位置）和餘數1.

對於1的剩餘部分，找出1/f（1）的商和餘數。商數是1，餘數是零，所以我們完成了。

所以Q_2 = 2，Q_1 = 1 2 * 3^2 + 1 * 3^1 = 21，這是一個正確的N.

我對爲什麼這個紙上作品的解釋，但我我不確定如何在文本中進行交流......請注意，f（i）回答了「p（p^i）中有多少p因子！」。一旦你找到最大的i，j，使得j * f（i）小於k，並且意識到你真的在做的是找到最小的j * p^i小於N，剩下的那種掉出洗。例如，在我們的p = 3的例子中，我們得到了4 p由1-9的乘積貢獻，另外4貢獻了10-18的乘積，還有一個貢獻了21。前兩個是p^2; f（2）= 4告訴我們，p^2的每個倍數對產品貢獻4個p。

[更新]

代碼總是有助於澄清。將以下perl腳本保存爲foo.pl並將其作爲foo.pl <p> <k>運行。請注意，**是Perl的指數運算符，bdiv計算BigInts（無限精度整數）的商和餘數，use bigint告訴Perl在任何地方都使用BigInts。

#!/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;

來源

2011-06-13 02:00:25 Nemo

這感覺就像p-adic規範會幫助解釋的東西 – 2011-06-13 04:09:47

-2

考慮

I =（P ^ñ）！

並忽略除p之外的主要因素。結果看起來像

我= P ^Ñ * P ^n-1個 * P ^的n-2 * ... * P * 1
我= P ^{N +（N-1）+ （n-2）+ ...2 + 1}
我= P ^{（N + N）/ 2}

因此，我們試圖找到最小的n，即

（N + N）/ 2> = K

其中如果記得二次方程右給我們

N = p ^ñ，其中n> = （sqrt（1 + 8k）-1）/ 2

（P.S.有誰知道如何顯示在降價的激進符號）

編輯：

這是不對的。讓我看看我是否可以挽救它...

來源

2011-06-13 16:08:05 Beta

找到最小的N使得N！可以被一個素數整除

回答

相關問題