Project Euler 第245题

8 投票

6 回答

5978 浏览

数据工程师

提问于 2025-04-15 11:39

我现在在研究第245题，但遇到了一些问题。我已经做了一些工作，但感觉没有真正朝解决问题的方向前进。到目前为止，我得到了以下内容：

我们需要找到 n=ab，其中 a 和 b 是正整数。我们可以假设 gcd(a, b) = 1，这样 phi(n) = phi(ab) = phi(a)phi(b) 就成立。

我们要解决的是：

$\frac{n-\phi(n)}{n-1}=\frac1k$

$\frac{n-1}{n-\phi(n)}=k$

因此：

$n\equiv1\ (\text{mod }n-\phi(n))$

在这个时候，我觉得实际看看这些数字的分布会是个好主意。我写了一个暴力破解的程序，用来找到所有小于 10⁴ 的（合成）解：

15, 85, 255, 259, 391, 589, 1111, 3193, 4171, 4369, 12361, 17473, 21845, 25429, 28243, 47989, 52537, 65535, 65641, 68377, 83767, 91759

重要的是，看起来在问题要求的 10¹¹ 限制下，不会有太多。我发现的最有趣/有用的部分是，即使对于较大的 n，k 也相当小。实际上，最大的 k 只有 138。（另外，似乎 k 总是偶数。）

考虑到这一点，我猜测可以考虑每个 k 的值，找出对应的 n 的值。

回到原始方程，可以将其重写为：

$\frac{\phi(n)-1}{n-1}=\frac{k-1}k$

因为我们知道 k：

$k\cdot\phi(n)\equiv k\ (\text{mod }n-1)$

这就是我目前的进展；我仍在追寻一些思路，但我在想我是不是错过了重点！通过暴力破解的方法，我找到了小于 10⁸ 的总和为 5699973227（只有 237 个 n 的解）。

我几乎没有其他想法了；有没有人能给我一些提示？

更新：很多人做了大量工作，我们一起证明了几件事情。以下是一些结论：

n 总是奇数，k 总是偶数。k <= 10^5.5。n 必须是无平方因子的。

我找到了 n=pq（两个质因子）时的所有解，其中 p > q。我利用了对于两个质数，q = k + factor(k² - k + 1) 和 p = k + [k² - k + 1] / factor(k² - k + 1) 的事实。我们还知道对于两个质数，k < q < 2k。

对于有两个或更多质因子的 n，所有的质因子都大于 k。

模运算质数数学问题暴力破解欧拉函数 gcd 合成数数学分布

6 个回答

让我接着 jug 开始的内容，但换个方式来讲。我们的目标还是找到那些有两个不同因子的数字 n=pq。正如你已经提到的，我们要找的数字是这样的：n-phi(n) 能被 n-1 整除。也就是说，如果 n=pq，那么我们要找的就是 p 和 q，使得

  p+q-1 divides pq-1

假设我们固定 p，并寻找所有满足上述方程的素数 q。这个方程看起来不太好解，所以接下来的步骤是尽量消去 q。特别地，我们知道如果 a 能整除 b，那么 a 也能整除 b + ka，对于任何整数 k。因此

  p+q-1 divides pq - 1 - p(p+q-1)

简化这个可以得到条件

  p+q-1 divides p^2 - p + 1.

我们可以假设 p 是 n 的较小素因子。那么 p 就小于 10¹¹ 的平方根。因此，通过遍历所有小于 10¹¹ 平方根的素数 p，我们可以找到所有有两个因子的数字，然后找出 p^2-p+1 的因子，解出 q，并检查 q 是否是素数，看看 pq 是否是问题的解。

当然，这样做仍然会留下有超过两个素因子的整数。类似的方法在这里也适用，但会更复杂，需要进一步优化。

我有个问题无法解答，那就是为什么这个问题的表述这么复杂。难道作者不能简单地问 composite 整数的和，其中 n-phi(n) 能被 n-1 整除吗？所以也许我错过了什么重要的提示。

现在，已知有两个素因子的解后，我会尝试找一个潜在的算法来寻找有超过两个素因子的解。目标是找到一个算法，给定一个合成整数 m，找到所有素数 q，使得 mq 是一个解。也就是说，q 必须满足

  mq - phi(mq) divides mq - 1.

设

  F = mq - phi(mq).

那么当然

  F = (m-phi(m)) q + phi(m).

和两个素因子的情况一样，我们可以通过从上面方程的左边消去 q 来找到 F 的条件。因为 F 能整除 mq-1，它也能整除

  (m-phi(m))(mq - 1)

因此也能整除

  m F - (m-phi(m))(mq - 1)  = m phi(m) + m - phi(m).

因此，通过找到 m phi(m) + m - phi(m) 的所有因子 F，并检查 (F - phi(m)) / (m - phi(m)) 是否是素数，就可以找到给定 m 的所有解 mq。因为只有满足

 F == phi(m) (mod m - phi(m))

的因子 F 才能导致新的解，这个事实有时可以用来优化 m phi(m) + m - phi(m) 的因式分解。

回答于 2025-04-15 由 Python大师

分享举报

Project Euler不太喜欢在像StackOverflow这样的公共论坛上讨论问题。所有的任务都是让你自己去完成的，如果你遇到困难，可以询问一些具体的数学或编程概念，但你不能直接问如何解决当前的问题——这样就失去了Project Euler的意义。

这个项目的目的是让你自己去学习和想出解决方案，同时掌握新的概念。

回答于 2025-04-15 由 Python大师

分享举报

乘积质数。我的做法是，首先检查每两个质数的乘积，并把成功的结果存起来。然后，利用这些存下来的乘积，再去检查更多的质数组合（每三个质数的乘积中，肯定有两个质数的组合是有效的）。接着，继续用这些存下来的乘积，尝试四个质数、五个质数等等。

唯一的缺点是，你需要一个好的质数筛选器或者质数列表。

以下是对于N小于等于10^7的质数乘积列表：

2个质数
15, 85, 259, 391, 589, 1111, 3193, 4171, 4369, 12361, 17473, 25429, 28243, 47989, 52537, 65641,
68377, 83767, 91759, 100777, 120019, 144097, 186367, 268321, 286357, 291919, 316171, 327937,
346063, 353029, 360301, 404797, 406867, 524851, 531721, 558013, 563767, 633727, 705667, 738607,
910489, 970141, 1013539, 1080769, 1093987, 1184233, 1185421, 1223869, 1233823, 1261807,
1264693, 1455889, 1487371, 1529641, 1574383, 1612381, 1617379, 1657531, 1793689, 2016379,
2095087, 2130871, 2214031, 2299459, 2500681, 2553709, 2609689, 2617963, 2763697, 3047521,
3146677, 3397651, 3514603, 3539017, 3820909, 3961219, 4078927, 4186993, 4197901, 4499707,
4552411, 4935883, 4975687, 5103841, 5299351, 5729257, 5829877, 5864581, 6017299, 6236401,
6802531, 6856609, 8759011, 9059233, 9203377, 9301603, 9305311, 9526747, 9536899, 9583279,
9782347, 9900217

3个质数
255, 21845, 335923, 3817309

4个质数
65535

5个质数
83623935

回答于 2025-04-15 由 Python大师

分享举报

Project Euler 第245题

6 个回答

撰写回答