[代數] 若k能表示為特定質因數分解式, 求k個數
數學版版友們好,
小弟因研究所需, 被要求證明graph上的vertices/edges數目,
但這個證明會需要用到另外某個性質, 即這次分享的題目.
數日來百思不得其解, 放上來和版友們討論,
還請提供小弟一些想法.
***
題目如下:
給定一正整數n, 及一不小於p的質數集合 S={2, 3, 5, ..., p}
設一正整數 k = 2^x * 3^y * ... * p^z,
且 k <= n
試求所有可能k的個數.
***
個人分析過, 如果是 x + y + ... + z = k <= n
那就是基本的重複組合題目. 所以此路線不通
如果是要求寬鬆一點的解,
是可以用 x + y + ... + z <= sqrt(k)來近似,
當|S| = 1時就是exact solution,
不過這個近似方法會隨著集合S變大, 而漸漸失真
另外, 這題也無法使用倍數的排容原理
i.e., (<n 二的倍數個數)+(<n 三的倍數個數)+...-(二和三的公倍數)-...
因為倍數不一定符合 k = 2^x * 3^y * ... * p^z 這個表示式
以上, 感謝版友們的撥冗指教.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.184.117
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1422692673.A.940.html
※ 編輯: SkyFluid (140.113.225.149), 02/01/2015 00:45:20
→
02/01 00:45, , 1F
02/01 00:45, 1F
※ 編輯: SkyFluid (140.113.225.149), 02/01/2015 00:57:25
推
02/01 01:49, , 2F
02/01 01:49, 2F
→
02/01 03:26, , 3F
02/01 03:26, 3F
謝謝fenzhang版友的回應,
我和一位數學系的友人討論, 發現要找到解法滿簡單的
(其實只要把介於p到n的質數列出, 然後用n減去所有這些數字的倍數即可)
但要把這個值用以n, p組成的多項式表示, 好像就沒有那麼容易了.
※ 編輯: SkyFluid (140.113.225.149), 02/01/2015 03:29:39