来自Project Euler,问题45:
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae: Triangle T_(n)=n(n+1)/2 1, 3, 6, 10, 15, ... Pentagonal P_(n)=n(3n−1)/2 1, 5, 12, 22, 35, ... Hexagonal H_(n)=n(2n−1) 1, 6, 15, 28, 45, ... It can be verified that T_(285) = P_(165) = H_(143) = 40755. Find the next triangle number that is also pentagonal and hexagonal.
[http://projecteuler.net/problem=45]
现在,为了求解它们,我取了三个变量,并将方程等同于A.
n(n + 1)/2 = a(3a - 1)/2 = b(2b - 1) = A
A=n、A、b 值的三重函数一致的数值
结果得到3个n和A的方程组。用夸克公式求解,得到3个方程组。
(-1 + sqrt(1 + 8*A ) )/2
( 1 + sqrt(1 + 24*A) )/6
( 1 + sqrt(1 + 8*A ) )/4
所以我的逻辑是测试A的值,在这个值上,三个方程给出了一个自然的+ve值。到目前为止,它对数字40755是正确的,但无法找到下一个高达1000万的数字。
(编辑):这是我在python 中的代码
from math import *
i=10000000
while(1):
i = i + 1
if(((-1+sqrt(1+8*i))/2).is_integer()):
if(((1+sqrt(1+24*i))/6).is_integer()):
if(((1+sqrt(1+8*i))/4).is_integer()):
print i
break
我的逻辑怎么错了?(为涉及的一些数学问题道歉。:))
假设:
- 所有的六边形也是三角形
heapq.merge
对于手头的任务非常方便(高效且节省代码)
然后这个:
import heapq
def hexagonals():
"Simplified generation of hexagonals"
n= 1
dn= 5
while 1:
yield n
n+= dn
dn+= 4
def pentagonals():
n= 1
dn= 4
while 1:
yield n
n+= dn
dn+= 3
def main():
last_n= 0
for n in heapq.merge(hexagonals(), pentagonals()):
if n == last_n:
print n
last_n= n
main()
几乎很快就会产生140755和你正在寻找的另一个数字,几秒钟后就会产生一个14位数的数字。只要你认为你烧够了电就停止这个程序。
如果您想避免"不透明"库,请使用以下main
(基本上是相同的算法,只是拼写出来):
def main():
hexagonal= hexagonals()
pentagonal= pentagonals()
h= next(hexagonal)
p= next(pentagonal)
while 1:
while p < h:
p= next(pentagonal)
if p == h:
print p
h= next(hexagonal)
时代看起来很相似,但我没有费心去衡量。
您的逻辑没有错,您的程序只是需要很长时间才能运行(据我估计,它应该在大约一个小时内提供答案)。我知道答案,并通过将i
设置为刚好低于它的值来测试您的程序。然后您的程序立即弹出正确的答案。
听从了埃斯库贝的建议。
实现的最简单方法是为每个序列制作3个生成器,并在中路由它们
heapq.merge
然后,如果你找到3个相同的保守密钥,你就得到了解决方案找到这个最简单的方法是usnig
itertools.groupby