[代數] 若k能表示為特定質因數分解式, 求k個數

[SkyFluid (鹹魚飯X的現身)]

數學版版友們好,


小弟因研究所需, 被要求證明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
→ SkyFluid    : 抱歉, 原本問題有錯. 應為相乘非相加.
※ 編輯: SkyFluid (140.113.225.149), 02/01/2015 00:57:25
推 fenzhang    : 你要的是上下界還是近似值還是算出值的演算法?
→ SkyFluid    : 我在找的是上下界, 不過當然這個界限是愈tight愈好
謝謝fenzhang版友的回應,

我和一位數學系的友人討論, 發現要找到解法滿簡單的
(其實只要把介於p到n的質數列出, 然後用n減去所有這些數字的倍數即可)

但要把這個值用以n, p組成的多項式表示, 好像就沒有那麼容易了.
※ 編輯: SkyFluid (140.113.225.149), 02/01/2015 03:29:39