Python3 欧拉计划 问题86-90
EulerProject.png
问题81-85参见：https://www.jianshu.com/p/8c3ec805433d
86、长方体内最短直线路径
蜘蛛spider在一个6*5*3大小的长方体盒子的一角，而苍蝇fly则恰好位于其对角。沿着盒子的表面，从spider到fly最短的“直线”距离是10=(62 +(3+5)2)1/2，其路径如下图所示：
path.png
然而，对于任意长方体，最短路径实际上一共有3种可能；而且，最短路径的长度也并不一定为整数。
当M=100时，若不考虑长方体的旋转，所有长、宽、高均不大于M且均为整数的长方体中，对角的最短距离是整数的恰好有2060个；100是使得该数目超过两千的最小M值；当M=99时，该数目为1975。
找出使得该数目超过一百万的最小M值。
Python3解答
import math
length = 3
count = 0
sign = 0
while 1:
for jj in range(3, 2 * length):#[a, 1, 1],[a, a, a]均不可能
boot = (jj ** 2 + length ** 2) ** 0.5
if int(boot) - boot == 0:#判断最短距离恰好是整数
if jj > length:
count += length - math.ceil(jj / 2) + 1
elif jj < length:
count += int(jj / 2)
#不会存在相等的情况
if count > 1000000:
sign = 1
break
if sign == 1:
break
if sign == 1:
break
else:
length += 1
print(length)
答案：1818
87、素数幂三元组
28是最小的可以表示为一个素数的平方，加上一个素数的立方，再加上一个素数的四次方的数。在小于50的数中，一共有4个数满足这一性质：
28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24
小于五千万的数中，可以这样表示的数的个数。
Python3解答
import numpy as np
import itertools
def Comprime(m, s):#得到素数的s次方
n = int(m ** (1 / s)) + 1
isprime = [True] * (n + 1) # 质数标识
isprime[0] = isprime[1] = False
result = [] # 质数列表
for i in range(2, n + 1):
if not isprime[i]:
continue
else:
result.append(i)
for j in range(i * 2, n + 1, i):
isprime[j] = False
return np.array(result) ** s
squre = Comprime(50000000, 2)#平方
cube = Comprime(50000000, 3)#立方
forth = Comprime(50000000, 4)#四次方
print((len(set(sum(list(i)) for i in itertools.product(squre, cube, forth) if sum(list(i)) < 50000000))))
答案：1097343
88、积和数
若自然数N能够同时表示成一组至少包括两个自然数集合{a1, a2, … , ak}中元素的的积与和，也就是有N = a1 + a2 + … + ak = a1 × a2 × … × ak成立，则N被称为积和数。例如，6是积和数，因为6 = 1 + 2 + 3 = 1 × 2 × 3。
固定集合中元素的个数k，我们称满足上述性质的最小的N值为K的最小积和数。当k 分别为 2、3、4、5、6时，最小积和数如下所示：
k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6
因此，对于2≤k≤6，所有的最小积和数的和为4+6+8+12 = 30。注意8只被计算了一次。已知对于2≤k≤12，所有最小积和数构成的无重复元素的集合是{4, 6, 8, 12, 15, 16}，这些数的和是61。
对于2≤k≤12000，所有最小积和数构成的无重复元素集合的元素和是。
Python3解答
#获得一个数除去本身和1之外的含有2个因子的列表
def fact(n):
factlist = []
for jj in range(2, int(n ** 0.5) + 1):
if n % jj == 0:
factlist.append([jj, n // jj])
return factlist
#分解字典
fadict = {}
for i in range(24001):
fadict[i] = fact(i)
#获得一个数的所有因子乘积表达式
for ii in fadict:
if len(fadict[ii]) == 0:
pass
else:
falist = []
for jj in fadict[ii]:
lelist = len(jj)
pisk = fadict[jj[-1]]
if len(pisk) != 0:
for dd in pisk:
cc = jj[: lelist - 1] + dd
falist.append(cc)
fadict[ii] += falist
#开始计算
resultdict ={}
for ike in range(2, 24001):
if len(fadict[ike]) == 0:
pass
else:
for jjj in fadict[ike]:
cc = ike - sum(jjj) + len(jjj)
try:
if resultdict[cc] > ike:
resultdict[cc] = ike
except KeyError:
resultdict[cc] = ike
cdict = {i: resultdict[i] for i in resultdict if i <= 12000}
print(sum(list(set(list(cdict.values())))))#无重复元素集合的元素的和
答案：7587457
89、罗马数字表示法
要正确地用罗马数字表达一个数，必须遵循一些基本规则。尽管符合规则的写法有时会多于一种，但对每个数来说总是存在一种最好的写法。例如，数16就至少有下面的六种写法：
IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI
然而，根据规则，只有XIIIIII和XVI是合理的写法，而后一种因为使用了最少的数字而被认为是最好的写法。
在文件roman.txt中包含了一千个合理的罗马数字写法，但并不都是最好的写法；有关罗马数字的明确规则，可以参考关于罗马数字。
求出将这些数都写成最有效的写法所节省的字符数。注意：可以假定文件中的所有罗马数字写法都不包含连续超过四个相同的字符。
Python3解答
import re
romandict = {'I': 1, 'V': 5, 'X': 10, 'L':50, 'C': 100, 'D': 500, 'M': 1000,}
fan=open(r'C:\Users\GWT9\Desktop\p089_roman.txt')#数据文件
an =[]
while 1:
x=fan.readline()
if len(x) == 0:
break
an.append(x.replace('\n',''))
fan.close()
##正则表达式
reformat= ['IV', 'IX', 'XL', 'XC', 'CD', 'CM']
#Roman -->Arabic numerals
def RoToAr(exlist, exdict = romandict, exre = reformat):
digit = []
for jj in exlist:
#满足减法法则
subb = 0
for rere in exre:
result = re.findall(r'%s'%rere, jj)
if len(result) != 0:
for cc in result:
subb += 2 * exdict[cc[0]]
summ = 0
#总和
for rr in jj:
summ += exdict[rr]
#存储
digit.append(summ - subb)
return digit
romandict = {'I': 1, 'V': 5, 'X': 10, 'L':50, 'C': 100, 'D': 500, 'M': 1000, 'IV': 4, 'IX': 9, 'XL': 40, 'XC': 90, 'CD': 400, 'CM': 900}
dictroman = {romandict[i] : i for i in romandict}
#Arabic numerals -->Roman
def ArtoRo(exlist, exdict = dictroman):
#Arabic
#arlist = RoToAr(exlist)
#Roman number
romanlist = sorted(list(exdict.keys()), reverse=True)
#存储
ar = []
for aa in exlist:
roman = ''
while aa != 0:
for jnum in romanlist:
if aa >= jnum:
cc = int(aa / jnum)
roman += cc * exdict[jnum]
aa -= cc * jnum
ar.append(roman)
return ar
#Computer
arabic = RoToAr(an)
roman = ArtoRo(arabic)
sim = 0
for ii in range(len(an)):
sim += len(an[ii]) - len(roman[ii])
print(sim)
答案：743
90、立方体数字对
在一个立方体的6个面上分别标上从0到9数字集合内的不同数字，另一个立方体也如此。将这两个立方体按不同的方向、不同的前后顺序并排摆放，我们可以得到各种各样的两位数。如下图所示：
cube.png
事实上，通过选择两个立方体上的数字，可以摆放出所有小于100的平方数：01、04、09、16、25、36、49、64和81(不包括00)。例如，一个立方体上标上{0, 5, 6, 7, 8, 9}，在另一个立方体上标上{1, 2, 3, 4, 8, 9}。
在这个问题中，允许将标有6或9的面颠倒过来互相表示，只有这样，如{0, 5, 6, 7, 8, 9}和{1, 2, 3, 4, 6, 7}这样本来无法表示09的标法，才能够摆放出全部九个平方数。
在考虑什么是不同的标法时，关注的是立方体上有哪些数字，而不关心它们的顺序。也就是说：
{1, 2, 3, 4, 5, 6}等价于{3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6}不同于{1, 2, 3, 4, 5, 9}
现在允许在摆放两位数时将6和9颠倒过来互相表示，两个立方体有多少中不同的标法可以摆放出所有的100以内的平方数。
Python3解答
import itertools
squre = ['0%d'%(dn ** 2) if len(str((dn ** 2))) == 1 else '%d'%(dn ** 2) for dn in range(1, 10)]#100以内的平方数
def judge(elist, xlist, dictlist = squre):#
alllist = []
#69可颠倒
if '6' in elist:
elist.append('9')
if '9' in elist:
elist.append('6')
if '6' in xlist:
xlist.append('9')
if '9' in xlist:
xlist.append('6')
for ee in elist:
for xx in xlist:
alllist.append(ee + xx)
alllist.append(xx + ee)
#判断是否可以全部表示
for dd in dictlist:
if dd not in alllist:
return False
return True
ff = 0
strdigit = [str(i) for i in range(10)]
count = 0
for ii in itertools.combinations(strdigit, 6):#一个立方体10个数中选择6个
for jj in itertools.combinations(strdigit, 6):#另一个立方体10个数中选择6个
ff += 1
if judge(list(ii), list(jj)):#判断是否可以完全表示平方数
count += 1
print(int(count / 2))#因为多算了一倍
答案：1217
持续更新，欢迎讨论，敬请关注！！！
