Mathematica求冪並找到一個指定的係數

Question

我有下面的代碼，它確實做了我想要它做的事情，除了它是非常慢的。我不會那麼困擾，只是當我「手動」處理代碼時，即我將它分解成幾部分並單獨執行時，它幾乎是瞬間的。

這裏是我的代碼：

Coefficient[Product[Sum[x^(j*Prime[i]), {j, 0, Floor[q/Prime[i]]}], 
         {i, 1, PrimePi[q]}], x, q] 

圖片添加爲清楚：

我認爲這是試圖優化的總和，但我不知道。有沒有辦法阻止它？另外，由於我所有的係數都是正的，而且我只想要第x個第一個，有沒有辦法讓Mathematica丟棄所有大於那個的指數，而不是所有與那些乘法的乘法？

Answer 1

我可能會誤解你想要的，但係數將取決於q，我假設你希望它對特定的q進行評估。由於我懷疑（像你一樣）時間是爲了優化產品和總和，我重寫了它。你有這樣的事情：

With[{q = 80}, Coefficient[\!\(
\*UnderoverscriptBox[\(\[Product]\), \(i = 1\), \(PrimePi[q]\)]\((
\*UnderoverscriptBox[\(\[Sum]\), \(j = 0\), \(\[LeftFloor] 
\*FractionBox[\(q\), \(Prime[i]\)]\[RightFloor]\)] 
\*SuperscriptBox[\(x\), \(j*Prime[i]\)])\)\), x, q]] // Timing 
(* 
-> {8.36181, 10003} 
*) 

我與純粹的結構性操作改寫爲

With[{q = 80}, 
Coefficient[Times @@ 
Table[Plus @@ Table[x^(j*Prime[i]), {j, 0, Floor[q/Prime[i]]}], 
     {i, 1, PrimePi[q]}], x, q]] // Timing 
(* 
-> {8.36357, 10003} 
*) 

（這只是建立了術語列表，然後將它們相乘，所以沒有進行象徵性的分析）。

剛剛建立多項式是瞬時的，但它有幾千個術語，所以可能發生的事情是Coefficient花費了很多時間來確保它具有正確的係數。其實你可以通過多項式來解決這個問題。因此：

With[{q = 80}, Coefficient[Expand[\!\(
\*UnderoverscriptBox[\(\[Product]\), \(i = 1\), \(PrimePi[q]\)]\((
\*UnderoverscriptBox[\(\[Sum]\), \(j = 0\), \(\[LeftFloor] 
\*FractionBox[\(q\), \(Prime[i]\)]\[RightFloor]\)] 
\*SuperscriptBox[\(x\), \(j*Prime[i]\)])\)\)], x, q]] // Timing 
(* 
-> {0.240862, 10003} 
*) 

它也適用於我的方法。

所以總結一下，只需在表達式前面，並在取係數之前，粘貼Expand。

Answer 2

我認爲原始代碼很慢的原因是因爲Coefficient即使對於非常大的表達式也可以工作 - 即使天真地展開也不會適合內存。

這裏的原多項式：

poly[q_, x_] := Product[Sum[ x^(j*Prime[i]), 
          {j, 0, Floor[q/Prime[i]]}], {i, 1, PrimePi[q]}] 

查看如何不太大q，擴大多項式佔用了大量的內存和相當緩慢變爲：

In[2]:= Through[{LeafCount, ByteCount}[poly[300, x]]] // Timing 
     Through[{LeafCount, ByteCount}[Expand@poly[300, x]]] // Timing 
Out[2]= { 0.01, { 1859, 55864}} 
Out[3]= {25.27, {77368, 3175840}} 

現在讓我們來定義係數以3種不同的方式和時間他們

coeff[q_] := Module[{x}, Coefficient[poly[q, x], x, q]] 
exCoeff[q_] := Module[{x}, Coefficient[Expand@poly[q, x], x, q]] 
serCoeff[q_] := Module[{x}, SeriesCoefficient[poly[q, x], {x, 0, q}]] 

In[7]:= Table[ coeff[q],{q,1,30}]//Timing 
     Table[ exCoeff[q],{q,1,30}]//Timing 
     Table[serCoeff[q],{q,1,30}]//Timing 
Out[7]= {0.37,{0,1,1,1,2,2,3,3,4,5,6,7,9,10,12,14,17,19,23,26,30,35,40,46,52,60,67,77,87,98}} 
Out[8]= {0.12,{0,1,1,1,2,2,3,3,4,5,6,7,9,10,12,14,17,19,23,26,30,35,40,46,52,60,67,77,87,98}} 
Out[9]= {0.06,{0,1,1,1,2,2,3,3,4,5,6,7,9,10,12,14,17,19,23,26,30,35,40,46,52,60,67,77,87,98}} 

In[10]:= coeff[100]//Timing 
      exCoeff[100]//Timing 
     serCoeff[100]//Timing 
Out[10]= {56.28,40899} 
Out[11]= { 0.84,40899} 
Out[12]= { 0.06,40899} 

所以SeriesCoefficient絕對是最好的選擇。當然，除非你是 好一點，在組合數學比我，你知道下列素分區式 （oeis）

In[13]:= CoefficientList[Series[1/Product[1-x^Prime[i],{i,1,30}],{x,0,30}],x] 
Out[13]= {1,0,1,1,1,2,2,3,3,4,5,6,7,9,10,12,14,17,19,23,26,30,35,40,46,52,60,67,77,87,98} 

In[14]:= f[n_]:=Length@IntegerPartitions[n,All,Prime@Range@PrimePi@n]; Array[f,30] 
Out[14]= {0,1,1,1,2,2,3,3,4,5,6,7,9,10,12,14,17,19,23,26,30,35,40,46,52,60,67,77,87,98}