Python3 欧拉计划 问题66-70

EulerProject.png
问题61-65参见：https://www.jianshu.com/p/ce99a41bc728

66、丢番图方程

  考虑如下形式的二次丢番图方程：
      x² – Dy² = 1
举例而言，当D=13时，x的最小值出现在649² – 13×180² = 1。可以断定，当D是平方数时，这个方程不存在正整数解。
  对于D= {2, 3, 5, 6, 7}分别求出x取最小值的解，我们得到：
      3² – 2×2²= 1
      2² – 3×1² = 1
      9² – 5×4² = 1
      5² – 6×2² = 1
      8² – 7×3² = 1
因此，对于所有D ≤ 7，当D=5时x的最小值最大。
  对于D ≤ 1000，求使得x的最小值最大的D值。

Python3解答

#Pell方程解题思路
#由X^2-D*Y^2=1。可得根号D约等于X/Y。而根号D恰好可以变为连分数的形式
def GetPell(number):
    sboot=number**0.5
    #判断是否为完全平方数
    if int(sboot)-sboot==0:
        return [number]
    else:
        #开始计算根号D的连分数形式
        P=0
        Q=1
        a=int(sboot)
        #第0和第1个渐进分数
        p=[1,a]#分子
        q=[0,1]#分母
        while p[1]**2-number*(q[1]**2)!=1:
            #中间变量
            P=a*Q-P
            Q=(number-P**2)/Q
            a=int((int(sboot)+P)//Q)
            #渐进分数
            pp=a*p[1]+p[0]#分子
            qq=a*q[1]+q[0]#分母
            #存储
            p=[p[1],pp]
            q=[q[1],qq]
        return [p[1],number,q[1]]
#开始计算
x=0
d=0
for ipell in range(1001):
    result=GetPell(ipell)
    if len(result)==3:#排除完全平方的数
        if x<result[0]:#选择最小值
            x=result[0]
            d=result[1]
        elif x==result[0] and d<result[1]:#一样的X值，选择D最小的值
            d=result[1]
print(d)
答案：661

67、最大路径和(进阶版)

  从下面展示的三角形的顶端出发，不断移动到在下一行与其相邻的元素，能够得到的最大路径和是23。
     3
   7 4
  2 4 6
  8 5 9 3
如上图，最大路径和为 3 + 7 + 4 + 9 = 23。
  在文件triangle.txt中包含了一个100行的三角形，求从其顶端出发到达底部，计算能够得到的最大路径和。
  这是第18题的进阶版。由于总路径一共有2⁹⁹条，穷举每条路经来解决这个问题是不可能的！即使你每秒钟能够检查10¹²条路径，全部检查完也需要两千万年。需要利用一个非常高效的算法才能解决这个问题。

Python3解答

#读取数据
fan=open(r'C:\Users\GWT9\Desktop\p067_triangle.txt')
an=[]
for i in range(100):
    an.append([])
    x=fan.readline()
    for j in range(100):
        try:
            an[i].append(int(x[j*3:(j*3)+2]))
        except ValueError:
            pass
fan.close()
#路径和最小动态规划
for ii in range(len(an)-2,-1,-1):
    for j in range(len(an[ii])):
        an[ii][j]=max(an[ii+1][j],an[ii+1][j+1])+an[ii][j]#动态规划思想
print(an[0][0])
答案：7273

  动态思想系列讲解

68、“魔力”五边形环

  考虑下图中的“魔力”三角形环，在其中填入1至6这6个数，每条线上的三个数加起来都是9。 Magic.png

  从最外侧结点所填的数中最小的数（在这个例子中是4,3,2）开始，按顺时针方向连接数字。按照此种方式每个解都能被唯一地描述。例如，上面这个解可以记作：4,3,2; 6,2,1; 5,1,3。将环填满后，每条线上的总和一共有四种可能：9、10、11和12，总共有下面8种填法，见下图：

sum.png

  把解集中的数字连接起来，可以构造一个9位数字串；对于三角形环来说，最大的数字串就是432621513。
  在如下的“魔力”五边形环中，

five.png

在其中填入1至10这10个数，根据不同的填写方式，可以组成16位或17位数字串。在“魔力”五边形环中，最大的16位数字串是。

Python3解答

import itertools as it
import numpy as np
#判断共享的数字集合
def magic(n):
    #数字列表
    select = list(range(1, 2*n + 1))
    #可能的数组列表
    plist = []
    #返回n个数字的组合
    for ii in it.combinations(select,n):
        if sum(list(ii)) % n == 0:#共同的数字之和必须能被n整除
            plist.append(list(ii))
    return plist

def comadd(exlist):
    #原始组合
    yuanshi = np.array(exlist)
    after = np.array(exlist[1:]+[exlist[0]])
    #关系字典
    save = {}
    for ii in range(len(yuanshi)):
        save[yuanshi[ii] +after[ii]] = [yuanshi[ii], after[ii]]
    return save

def judge(exlist):
    #去差集
    cha = list(set(list(range(1, 2 * len(exlist) + 1))).difference(set(exlist)))
    #计算exlist的可能的组合,
    problist = []
    pailie = it.permutations(exlist[1:], len(exlist) - 1)
    for i in pailie:
        if list(i)[::-1] not in problist:#去除掉组合重复的
            problist.append(list(i))
    #存储的字典
    savedict = {}
    for hh in problist:
        hh.insert(0, exlist[0])
        sadict = comadd(hh)
        if len(sadict.keys()) == len(cha):#如果字典长度不够，说明存在数字和相同的情况，去掉这种情形
            # 计算problist中的每一个组合是否满足条件
            sumlist = list(np.array(sorted(list(sadict.keys()))) + np.array(sorted(cha, reverse = True)))
            if len(set(sumlist)) == 1:
                savedict[tuple(cha)] = sadict
    return savedict

#定义输出数字序列的函数
def Transnum(exdict, keynum, weizhi, emptylist, keylist, sumdi):
    emptylist += str(sumdi - keynum) + str(exdict[keynum][weizhi]) + str( exdict[keynum][weizhi - 1]) + ','
    #选取键序列中的最小值
    keylist.append(keynum)
    for jj in exdict:
        if jj not in keylist:
            if exdict[keynum][weizhi - 1] == exdict[jj][weizhi]:
                keynum = jj
                return Transnum(exdict, keynum, weizhi, emptylist, keylist, sumdi)
    return emptylist

#输出所有的可能性
savelist = []
for idi in magic(5):
    #字典
    ddict = judge(idi)
    if len(ddict) != 0:
        #键中的最小值
        keynu = min(list(list(ddict.keys())[0]))
        #值中键的最大值
        numley = max(list(list(ddict.values())[0].keys()))
        for idd in [0, 1]:
            numstr = Transnum(list(ddict.values())[0], numley, idd, '', [], keynu + numley)
            savelist.append(numstr)
            print('%s: %s'%(keynu + numley, numstr))

#判断16数字最大的
lastnumber = 0
for j in savelist:
    #去掉逗号
    dele = j.replace(',','')
    if len(dele) == 16:
        #获得数字
        if lastnumber < int(dele):
            lastnumber = int(dele)
print(lastnumber)
答案：
所有“魔力”五边形环：
14: 635,752,824,941,1013,
14: 653,1031,914,842,725,
16: 2410,5101,817,673,934,
16: 2104,943,637,871,5110,
16: 259,493,637,871,1015,
16: 295,1051,817,673,439,
17: 278,584,3410,6101,917,
17: 287,971,6110,3104,548,
17: 1610,3104,548,782,926,
17: 1106,962,728,584,3410,
19: 1810,2107,379,496,568,
19: 1108,586,469,397,2710,
最大的16位数字串是：6531031914842725

69、欧拉函数之比值

  在小于n的数中，与n互质的数的数目记为欧拉函数φ(n)(有时也称为φ函数)。例如：1、2、4、5、7和8均小于9且与9互质，故φ(9)=6。

euler.png

  从上图可以看出，对于n ≤ 10，当n=6时n/φ(n)最大。当n ≤ 1,000,000时，求使得n/φ(n)取得最大值的n。

Python3解答

n = 1000000
isprime = [True] * (n + 1) #质数标识
isprime[0] = isprime[1] = False
result = [] #质数列表
euler = [1, 1] + list(range(2, n + 1))#欧拉函数表

for i in range(2, n + 1):
    if not isprime[i]:
        continue
    else:
        result.append(i)
        euler[i] = i - 1
        for j in range(i * 2, n + 1, i):
            isprime[j] = False
            euler[j] *= (1 - (1 / i))
#n/φ(n)
funceuler = {i : i /euler[i] for i in range(0, n + 1)}#计算n/φ(n)
print(max(funceuler.items(), key = lambda x : x[1])[0])#计算n/φ(n)最大值对应的n值
答案：510510

70、欧拉函数之重排

  在小于n的数中，与n互质的数的数目记为欧拉函数φ(n)(有时也称为φ函数）。例如，因为1、2、4、5、7和8均小于9且与9互质，故φ(9)=6。1被认为和任意正整数互质，所以φ(1)=1。
  有趣的是，φ(87109)=79180，而79180是87109的一个重排。
  在1 < n < 10⁷中，有些n满足φ(n)是n的一个重排，求这些值中使n/φ(n)最小的一个。

Python3解答

n = 10000000
isprime = [True] * (n + 1) #质数标识
isprime[0] = isprime[1] = False
result = [] #质数列表
euler = [n, n] + list(range(2, n + 1))#欧拉函数表

for i in range(2, n + 1):
    if not isprime[i]:
        continue
    else:
        result.append(i)
        euler[i] = i - 1
        for j in range(i * 2, n + 1, i):
            isprime[j] = False
            euler[j] *= (1 - (1 / i))
#n/φ(n)
funceuler = {i : i /euler[i]  for i in range(0, n + 1) if sorted(str(i)) == sorted(str(int(euler[i])))}#只选择φ(n)和n是重排的.

minkey = min(funceuler.items(), key = lambda x : x[1])[0]
print(euler[minkey])
print(minkey)
答案：φ(8319823)=8313928
最小的n值为8319823

持续更新，欢迎讨论，敬请关注！！！