项目欧拉问题245
我现在遇到问题245,但遇到了一些问题.我已经做了一些工作,但我觉得我没有采取任何实际步骤来解决它.这是我到目前为止所得到的:
我们需要找到带有a和b正整数的n = ab.我们还可以假设gcd(a,b)= 1而不失一般性,因此phi(n)= phi(ab)= phi(a)phi(b).
我们正在努力解决:
因此:
在这一点上,我认为实际看看这些数字是如何分配的是一个好主意.我一起攻击了一个蛮力程序,我用它来查找最多10个4的所有(复合)解决方案:
15, 85, 255, 259, 391, 589, 1111, 3193, 4171, 4369, 12361, 17473, 21845, 25429, 28243, 47989, 52537, 65535, 65641, 68377, 83767, 91759
重要的是,它看起来不会比问题所要求的10 11限制少得多.我发现的最有趣/最有用的一点是即使对于n的大值,k也很小.事实上,最大的k只有138.(另外,似乎k总是均匀.)
考虑到这一点,我猜想有可能考虑k的每个值,并找出k的值为n的值.
返回原始等式,请注意它可以重写为:
既然我们知道k:
这就是我所拥有的; 我仍在追求我的一些路线,但我想知道我是否错过了这一点!通过蛮力方法,我发现总和达到10 8,这是5699973227(n的解决方案只有237).
我几乎没有想法; 任何人都可以泄露一些提示吗？
更新:很多人已经做了很多工作,我们一起能够证明一些事情.这是一个清单:
n总是奇数,k总是偶数.k <= 10 5.5.n必须是无方形的.
我找到了当p = q时n = pq(2个素数因子)的每个解.我使用了对于2个素数q = k +因子(k ^ 2-k + 1)和p = k + [k ^ 2-k + 1] /因子(k ^ 2-k + 1)的事实.我们也知道2个素数k <q <2k.
对于具有2个更多素因子的n,所有n个素数都大于k.
项目Euler不喜欢在像StackOverflow这样的公共论坛上讨论问题.所有任务都是单独完成的,如果你遇到问题,你可能会为特定的数学或编程概念寻求帮助,但你不能只是决定如何解决手头的问题 - 取消项目Euler的观点.
重点是自己学习并提出解决方案,并学习新的概念.
- 当你尝试过,并且花费了很多精力来解决问题时,就像PythonPower明显的那样,没有必要继续把你的头撞到墙上 - 当你没有更多的东西可以自己学习时,你就达到了一个阶段.在这一点上,明智的做法是寻求帮助并寻求学习,而不是放弃.:P (12认同)
- 从主页:"利用互联网研究问题是值得鼓励的,因为在许多这些问题的表面下可能会发现隐藏的数学宝藏." (7认同)
- 研究正是他正在做的事情.他展示了自己的作品,对每一个暗示和猜测都进行了跟踪,并证明/反驳了它.您希望有人在寻求帮助之前(甚至之后)做什么？如何在不遇到它们的情况下"学习新概念"？ (7认同)
- 鼓励研究，而不是寻求谜题的解决方案。我的意思是对我来说，我看到的更多，就像你通过阅读意识到某个问题需要贝叶斯定律的知识一样，所以你向人们寻求帮助来实现贝叶斯分类程序，而不是寻求整个难题的解决方案。 (2认同)
让我继续一下壶开始,但尝试一种不同的方法.再次目标是找到具有两个不同因素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 11的平方根.因此,通过迭代10 11的平方根下的所有素数p ,找到p ^ 2-p + 1的除数,求解q并检查q是否为素数且pq是解决问题的方法.
当然,这仍然会使整数具有两个以上的素数因子.一种类似的方法也适用于此,但更多涉及并需要进一步优化.
我无法回答的一个问题是为什么这个问题的制定如此复杂.作者难道只是要求n-phi(n)除n-1的复合整数之和.所以也许我在那里错过了一个很大的暗示.
现在,已知具有两个素因子的解,我将尝试找到一种潜在的算法来寻找具有超过2个素因子的解.目标是找到一个算法,给定一个复合整数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.
F == phi(m) (mod m - phi(m))
可以导致新的解决方案,这个事实有时可以用来优化m phi(m)+ m - phi(m)的因子分解.
- 并不是的.当m = 53*211作为输入时,我的程序确实找到q = 349.虽然问题是找到一个很好的标准来选择需要测试的m的值.例如,如果m和phi(m)不是互质的,那么就没有必要对它们进行测试.我可以假设q是最大的素因子,因此我不需要测试所有m的高达10 ^ 11,但它仍然可能是一个很大的数字. (3认同)
小智 3
素数相乘。我所做的是，首先检查每个 2-prime 产品；存储成功的内容。然后使用存储的产品，检查那些具有更多素数的产品（暴力破解中显示的每个 3 素数产品都有一个有效的 2 素数子集）。使用这些存储的产品，并用 4 个素数、5 个素数等重试。
唯一的缺点是你需要一个好的筛子或素数列表。
以下是 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,73 8607,910489,970141,1013539,1080769, 1093987,1184233,1185421,1223869,1233823,12618 07,1264693, 1455889,1487371,1529641,1574383,1612381,1617379,1657531,1793689,20163 79,2095087,2130871,2214031,2299459,2500681,2553709,26 09689,2617963,2763697,30475 21,3146677,3397651,3514603,3539017,3820909, 3961219,4078927,4186993,4197901,44997 07,4552411,4935883,4975687,5103841,5299351,5729257,5829877,5864581,6017299,62364 01,6 802531,6856609,8759011,9059233,9203377,9301603,9305311,9526747,9536899, 95832 79,9782347,9900217 3 个质数 255,21845,335923,3817309 4 个质数 65535 5 个质数 83623935