求n值，使\(\frac{1}{a}+\frac{1}{b}=\frac{1}{n}\)的正整数解的个数大于特定值

天山草

当  q=1 时  1/x + 1/y = q/p = 1/p = 1/n 的解的组数如前面陆教授的公式，写成 mathematica 程序是

共有   (Length[Divisors[n^2]]+1)/2  组解。

按这个公式写个小程序：

1. Do[k = (Length[Divisors[n^2]] + 1)/2;
   
2. If[k > 1000, Print["n= ", n, " , k= ", k]; Break[]];
   
3. n++;
   
4. , {n, 1, 99999999999999}]

复制代码

运行结果可答复主帖提出的问题：

n=180180 时解的个数为 k=1013，大于 1000。

n= 268107840  时解的个数为 k=11057，大于 10000。

对于大于 10000 这个解不要直接运行上面的程序，否则时间太长，因为 n = 2^2×3^2×7×11×13×17×19×23 时  k=9113，

n = 2^3×3^2×7×11×13×17×19×23 时  k=12758，因此  n 的筛选区间就缩小了范围，运行时间缩短。

杨协成

cgl_74 发表于 2021-7-20 20:11
我的解法，供讨论哈。N值的计算有些烦冗，求解过程先忽略。

8楼的cgl_74网友对第二问的解答是正确的！使用质因数分解的方法极大地提高了求解效率。

当解的组数大于1000时， \(n=180180\) 是最小的n值。

欢迎继续改进算法，使用更高效的算法求解第三问。

天山草

当 n 的最小值等于多少，解的个数大于 100000 ？ 大于 1000000 ？

zytsang

cgl_74 发表于 2021-7-20 20:11
我的解法，供讨论哈。N值的计算有些烦冗，求解过程先忽略。

8楼使用素因子分解的方法非常巧妙，我借用同样的思路，写个小程序可以把第三问的 \(n\) 值搜索出来：
\[n=9350130049860600
=2^3\cdot
3^3\cdot
5^2\cdot
7^2\cdot
11\cdot
13\cdot
17\cdot
19\cdot
23\cdot
29\cdot
31\cdot
37\]
解的数量为
\[\frac{(2\cdot3+1)^2(2\cdot2+1)^2(2\cdot1+1)^8+1}{2}=4018613\]

站在巨人cgl_74的肩膀上。

---

有些技巧可以减小搜索空间：
（1）素因子分解可写为
\[n=p_1^{a_1}\cdot p_2^{a_2} \cdot p_3^{a_3}\cdots\]
令素因子从小到大排列
\[p_1<p_2<p_3<\cdots\]
对于满足题目要求的最小 \(n\) 值，我们必有
\[a_1\geq a_2\geq a_3\geq \cdots\]

（2）我们最多只需要前14个素因子，因为 \(3^{14}=4782969\) 就已经大于第三问的解的组数要求。所以我们最多只需要尝试搜索素因子的指数 \(\{a_1,a_2, \cdots, a_{14}\}\)，使得
\[\frac{(2a_1+1)(2a_2+1)\cdots(2a_{14}+1)+1}{2}>4000000\]
并且
\[a_1\geq a_2\geq \cdots\geq a_{14}\]
对应的 \(n\) 值则可以计算为
\[n
=2^{a_1}\cdot
3^{a_2}\cdot
5^{a_3}\cdot
7^{a_4}\cdot
11^{a_5}\cdot
13^{a_6}\cdot
17^{a_7}\cdot
19^{a_8}\cdot
23^{a_9}\cdot
29^{a_{10}}\cdot
31^{a_{11}}\cdot
37^{a_{12}}\cdot
41^{a_{13}}\cdot
43^{a_{14}}\]

cgl_74

zytsang 发表于 2021-7-20 22:43
8楼使用素因子分解的方法非常巧妙，我借用同样的思路，写个小程序可以把第三问的 \(n\) 值搜索出来：
\[ ...

牛
计算问题还是用计算机搞快！

zytsang

cgl_74 发表于 2021-7-20 22:57
牛
计算问题还是用计算机搞快！

昨天拿Fortran跑，穷举了n久都没超越 \(1\times10^5\)，全靠大神的思路呢 当然这第三问的 \(4\times10^6\) 应该是特意选的，如果再高个数量级还得另想办法。

---

为了完整性，我补充一点过程。对于正整数 \(n\)，若其素因子分解为
\[n=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}=\prod_{i=1}^k p_i^{a_i}\]
则 \(n\) 的因子数量为
\[d(n)=(a_1+1)(a_2+1)\cdots(a_k+1)=\prod_{i=1}^k (a_i+1)\]
根据7楼陆教授的推导，我们需要求 \(d(n^2)\)。显然
\[n^2=\Big(p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}\Big)^2=\left(\prod_{i=1}^k p_i^{a_i}\right)^2=\prod_{i=1}^k p_i^{2a_i}\]
所以 \(n^2\) 的因子数量为
\[d(n^2)=(2a_1+1)(2a_2+1)\cdots(2a_k+1)=\prod_{i=1}^k (2a_i+1)\]
所以 \(n^2\) 的对应方程的解的数量为
\[\frac{d(n^2)+1}{2}=\frac{(2a_1+1)(2a_2+1)\cdots(2a_k+1)+1}{2}\]
这是8楼的其中一个过程。这一步显著降低了计算复杂度，将 \(n^2\) 的素因子分解降低为 \(n\) 的素因子分解。

---

另外，满足题目要求的最小 \(n\) 值，我们必有
\[a_1\geq a_2\geq a_3\geq \cdots\]
是因为，如果当 \(i<j\) 时存在 \(a_i < a_j \)，那么我们可以调换 \(a_i\) 和 \(a_j\) 的数值，使得 \(n\) 值变小，但是不改变 \(n\) 的因子数量。举个例子，比如 \(n_1=2^2\cdot 3^3=108\)，那么我们可以令 \(n_2=2^3\cdot3^2=72\)，这样有 \(n_2<n_1\) 但是 \(n_1\) 和 \(n_2\) 有同样数量的因子。

杨协成

zytsang 发表于 2021-7-20 22:43
8楼使用素因子分解的方法非常巧妙，我借用同样的思路，写个小程序可以把第三问的 \(n\) 值搜索出来：
\[ ...

14楼的zytsang网友对第三问的解答是正确的！突破性思路由8楼的cgl_74网友提供。

当解的组数大于4000000时， \(n=9350130049860600\) 是最小的n值。

非常感谢各位网友的参与！

cgl_74

关于解的数量的计算，我看了看7楼陆老师的算法，以及zytsang的说明，简单推广一下也推导出解的因子算法。
我整理了一下我的推导过程作为补充。

xfhaoym