数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
12
返回列表 发新帖
楼主: 杨协成

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

[复制链接]
发表于 2021-7-20 21:19 | 显示全部楼层
本帖最后由 天山草 于 2021-7-20 22:11 编辑

当  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 的筛选区间就缩小了范围,运行时间缩短。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-7-20 21:31 | 显示全部楼层
cgl_74 发表于 2021-7-20 20:11
我的解法,供讨论哈。N值的计算有些烦冗,求解过程先忽略。

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

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

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

点评

n= 268107840 时解的个数为 k=11057,大于 10000。  发表于 2021-7-20 22:22
回复 支持 反对

使用道具 举报

发表于 2021-7-20 22:25 | 显示全部楼层
本帖最后由 天山草 于 2021-7-20 23:14 编辑

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

回复 支持 反对

使用道具 举报

发表于 2021-7-20 22:43 | 显示全部楼层
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}}\]

点评

道理是对,实际上是老虎吃天,没法下手。  发表于 2021-7-20 23:19
回复 支持 反对

使用道具 举报

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


计算问题还是用计算机搞快!
回复 支持 反对

使用道具 举报

发表于 2021-7-20 23:45 | 显示全部楼层
本帖最后由 zytsang 于 2021-7-21 00:03 编辑
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\) 有同样数量的因子。
回复 支持 反对

使用道具 举报

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

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

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

非常感谢各位网友的参与!
回复 支持 反对

使用道具 举报

发表于 2021-7-21 16:13 | 显示全部楼层
关于解的数量的计算,我看了看7楼陆老师的算法,以及zytsang的说明,简单推广一下也推导出解的因子算法。
我整理了一下我的推导过程作为补充。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 1 反对 0

使用道具 举报

发表于 2021-7-22 07:43 | 显示全部楼层

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2021-8-1 16:32 , Processed in 0.062500 second(s), 15 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表