EulerProject.png
问题86-90参见：https://www.jianshu.com/p/87878ead47f2
91、直角三角形个数
下图中，点P(x1, y1)、点Q(x2, y2)、原点O(0,0)构成直角坐标系中的三角形ΔOPQ：
point.png
当点P和点Q的所有坐标都在0到2之间，也就是说0 ≤ x1, y1, x2, y2 ≤ 2时，恰好能构造出如下所示的14个直角三角形。
triangles.png
如果0 ≤ x1, y1, x2, y2 ≤ 50，能构造出多少个直角三角形。
Python3解答
#方法一：直接方法，判断三点是否组成直角三角形
Plist = [[x, y] for x in range(51) for y in range(51)]
Qlist = Plist.copy()
def judge(elist, xlist):
one = (elist[0] - xlist[0]) ** 2 + (elist[1] - xlist[1]) ** 2
two = (elist[0]) ** 2 + (elist[1]) ** 2
three = (xlist[0]) ** 2 + (xlist[1]) ** 2
blist = [one, two, three]
if 0 in blist:
return False
else:
if max(blist) * 2 == sum(blist):
return True
else:
return False
count = 0
for jjj in Plist:
for hhh in Qlist:
if judge(jjj, hhh):
count += 1
print(int(count * 0.5))
#方法二：根据几何知识，互相垂直的直线斜率乘积为-1**
def Euclidean(a, b):#计算最大公因数，辗转相除法
d = a % b
if d == 0:
return b
else:
while d != 0:
a, b = b, a % b
d = a % b
return b
count= 0
for i in range(1, 51):
for j in range(1, 51):
k = Euclidean(i, j)
count += min(int((50 - i) * k / j), int((j * k / i))) * 2
count += 50 * 50 * 3#在边上的
print(count)
答案：14234
92、数字链
将一个数的所有数字的平方相加得到一个新的数，不断重复直到新的数已经出现过为止，这构成了一条数字链。例如：
44 --> 32 --> 13 --> 10 --> 1 --> 1
85 --> 89 --> 145 --> 42 --> 20 --> 4 --> 16 --> 37 --> 58 --> 89
可见，任何一个到达1或者89的数字链都会循环下去。更令人惊奇的是，从任意数开始，最终都会到达1或89。
有多少个小于一千万的数最终会到达89。
Python3解答
def tonu(number):#数转化为数字平方的和
if number == 1:
return False
elif number == 89:
return True
else:
fu = str(number)
summ = 0
for jj in fu:
summ += int(jj) ** 2
return tonu(summ)
numdict = {}
for ii in range(1, 10000000):
fnu = 0
for jj in str(ii):
fnu += int(jj) * int(jj)
try:
numdict[fnu] += 1
except KeyError:
numdict[fnu] = 1
count = 0
for oo in range(1, 7 * 9 * 9 + 1):#小于1000万的数转化之后的范围。
if tonu(oo):
try:
count += numdict[oo]
except KeyError:
pass
print(count)
答案：8581146
93、算术表达式
使用集合{1, 2, 3, 4}中每个数字恰好一次以及"("，"+"，"−"，"*"，" /"，")"四则运算和括号，可以得到不同的正整数。例如，
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)
注意不允许直接把数字连起来，如12 + 34。
使用集合{1, 2, 3, 4}，可以得到31个不同的数，其中最大值是36，以及1到28之间所有的数。
若使用包含有4个不同数字a < b < c < d的集合可以得到从1到n之间所有的数，求其中使得n最大的集合，并将集合元素写成字符串abcd的形式。
Python3解答
import itertools
operator = ['+', '-', '*', '/']
#只存在五种结构
format = ['((%d%s%d)%s%d)%s%d', \
'(%d%s%d)%s(%d%s%d)', \
'(%d%s(%d%s%d))%s%d', \
'%d%s((%d%s%d)%s%d)', \
'%d%s(%d%s(%d%s%d))']
#数字和字母穿插
def Chuan(num, letter):
chuan = []
for jj in range(len(num)):
chuan.append(num[jj])
try:
chuan.append(letter[jj])
except IndexError:
pass
return chuan
#构建数字和算子的组合
def Combine(numlist, target, oplist = operator, form = format):
expre = []
for jj in list(itertools.permutations(numlist, len(numlist))):#数字
for ii in list(itertools.product(oplist, repeat = 3)):#算子
fu = Chuan(list(jj), list(ii))#交叉
for ff in form:#遍历每一种情况
try:
if eval(str(ff)%tuple(fu)) == target:
return True
except ZeroDivisionError:
pass
return False
n = 0
for a in range(1, 7):
for b in range(a + 1, 8):
for c in range(b + 1, 9):
for d in range(c + 1, 10):
tar = 1
while Combine([a, b, c, d], tar):
tar += 1
if n < tar:
cc = '%s%s%s%s'%(a,b,c,d)
n = tar
if tar == 1:
break
print(cc)
答案：1258
94、近似等边三角形
可以证明，不存在边长为整数的等边三角形其面积也是整数。但是，存在近似等边三角形 ，例如三边分别为5，5，6，其面积恰好为12。现定义有两条边一样长，且第三边与这两边最多相差为1的三角形为近似等边三角形。
对于所有边长和面积均为整数且周长不超过十亿的三角形，求其中所有近似等边三角形的周长之和。
Python3解答
#Pell方程x^2 - 3y^2 = 1， 初始解为(2, 1)
x = 2
y = 1
summ = 0
while 1:
ynum = 2 * y + 1 * x
xnum = x * 2 + 3 * y * 1
x = xnum
y = ynum
# 第一种(a, a+1, a+1)
# 化为((3a+4)/2)^2-3h^2=1，利用Pell方程
if 2 * xnum - 2 < 1e9:#周长限制
if (2 * xnum - 4) / 3 % 2==0:#判断边长为整数
squre = ynum * (xnum - 2) / 3
if int(squre) - squre == 0:#面积为整数
summ += 2 * xnum - 2
else:
break
# 第二种(a, a-1, a-1)
# 化为((3a-4)/2)^2-3h^2=1，利用Pell方程
if 2 * xnum + 2 < 1e9:##周长限制
if (2 * xnum + 4) / 3 % 2==0:#判断边长为整数
squre = ynum * (xnum + 2) / 3
if int(squre) - squre == 0:##面积为整数
summ += 2 * xnum + 2
else:
break
print(summ)
答案：518408346
95、亲和数链
一个数除了本身之外的其他因数称为真因数。例如，28的真因数有1、2、4、7和14。这些真因数的和恰好为28，因此称28是完全数。有趣的是，220的真因数之和是284，同时284的真因数之和是220，构成了一个长度为2的链，我们称之为亲和数对。
有一些更长的序列并不太为人所知。例如，从12496出发，可以构成一个如下长度为5的链：
12496 --> 14288 --> 15472 --> 14536 --> 14264 --> 12496 --> …
由于这条链最后又回到了起点，称之为亲和数链。
找出所有元素都不超过100万的亲和数链中最长的那条，并给出其中最小的那个数。
Python3解答
maxnum = 1000000
factorsum = [0, 1] + [0] * (maxnum - 2)
for i in range(1, maxnum):
for j in range(i * 2, maxnum, i):
factorsum[j] += i
#开始计算最长链的最小值
minnum = 0
leng = 0
allist = []
for kk in range(2, maxnum):
sign = 1
falist = []
clo = factorsum[kk]
copynum = clo
while clo not in falist:#判断是否重复，终止链
falist.append(clo)
if clo > 1e6 or clo == 1:
sign = 0
break
clo = factorsum[clo]
if sign and clo - copynum == 0:#开始结束均为同一个数
length = len(falist)
if length > leng:#选取最长的链
leng = length
minnum = min(falist)
print(minnum)
答案：14316
持续更新，欢迎讨论，敬请关注！！！
网友评论