Python3 欧拉计划 问题71-75

EulerProject.png
问题66-70参见：https://www.jianshu.com/p/d0fad6213433

71、有序分数

  考虑形如n/d的分数，其中n和d均为正整数。如果n < d且其最大公约数为1，则该分数称为最简真分数。
  如果将d ≤ 8的最简真分数构成的集合按大小升序列出，我们得到：
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可以看出2/5是3/7直接左邻的分数。
  将所有d ≤ 1,000,000的最简真分数按大小升序排列，求此时3/7直接左邻的分数的分子。

Python3解答

#得到一个数的质因数
def computer(n):
    prilist = []
    startnum = 2
    while startnum ** 2 <= n:
        if n % startnum == 0:
            n = n // startnum
            if startnum not in prilist:
                prilist.append(startnum)
            startnum = 2
        else:
            startnum += 1
    if n not in prilist:
        prilist.append(n)
    return prilist

for iii in range(1000000, 1, -1):
    dd = 3 * iii - 1
    if dd % 7 == 0:
        b1 = computer(iii)
        b2 = computer(dd // 7)
        if len(list(set(b1) & set(b2))) == 0:#求交集
            print('分数为%d/%d'%(dd // 7, iii))
            break
答案：分数为428570/999997，分子为425870

72、分数个数

  考虑形如n/d的分数，其中n和d均为正整数。如果n < d且其最大公约数为1，则该分数称为最简真分数。
  如果将d ≤ 8的最简真分数构成的集合按大小升序列出，我们得到：
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可以看出该集合中共有21个元素。
  求出d ≤ 1,000,000的最简真分数构成的集合中共有多少个元素。

Python3解答

#欧拉函数之和等于最简真分数个数
n = 1000000
isprime = [True] * (n + 1) #质数标识
isprime[0] = isprime[1] = False
result = [] #质数列表
euler = [0, 0] + 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))
print(int(sum(euler)))
答案：303963552391

73、区间内的分数个数

  考虑形如n/d的分数，其中n和d均为正整数。如果n < d且其最大公约数为1，则该分数称为最简真分数。
  如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出，我们得到：
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可以看出在1/3和1/2之间有3个分数。
  将d ≤ 12,000的最简真分数构成的集合排序后，在1/3和1/2之间有多少个分数。

Python3解答

#辗转相除法计算最大公因数
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 ii in range(4, 12001):
    for gg in range(int(ii / 3) + 1, int(ii / 2) + 1):#在三分之一和二分之一之间
        if Euclidean(ii, gg) == 1:
            count += 1
print(count)
答案：7295372

74、数字阶乘之链

  145之所以广为人知，是因为它的各位数字的阶乘之和恰好等于本身：
    1! + 4! + 5! = 1 + 24 + 120 = 145
169也具有这样的性质，从169开始不断地取各位数字的阶乘之和构成了具有三个数字的循环回到169；事实上，只存在三个这样的循环：
169 ----> 363601 ----> 1454 ----> 169
871 ----> 45361 ----> 871
872 ----> 45362 ----> 872
不难证明，从任意数字出发最终都会陷入循环。例如，
69 ----> 363600 ----> 1454 ----> 169 ----> 363601 (----> 1454)
78 ----> 45360 ----> 871 ----> 45361 (----> 871)
540 ----> 145 (----> 145)
从69开始可以得到一个拥有五个不重复项的链，但是从一个小于一百万的数出发能够得到的最长的无重复项链包含有60项。
  从小于一百万的数出发，有多少条链恰好包含有60个不重复项。

Python3解答

stdict = {0: 1}#数字阶乘字典
start = 1
while start < 10:
    stdict[start] = start * stdict[start - 1]
    start += 1
def transdigit(num, di = stdict):#数转化为数字阶乘之和
    strnum = str(num)
    st = 0
    for ii in strnum:
        st += di[int(ii)]
    return st
def duging(number):#数字阶乘之链
    fu =[]
    while number not in fu:
        fu.append(number)
        dd = transdigit(number)
        number = dd
    fu.append(number)
    return fu
result = {}
count = 0
for iii in range(999999, 0, -1):
    if iii not in result:
        nn = duging(iii)
        legn = len(nn)
        result[iii] = legn - 1
        if legn - 61 == 0:
            count += 1
        jwei = nn.index(nn[-1])
        for iij in range(1, legn - 1):
            if nn[iij] not in result:
                if iij < jwei:
                    result[nn[iij]] = legn - iij - 1
                else:
                    result[nn[iij]] = legn - jwei -1
            else:
               break
print(count)
答案：402

75、唯一整数边直角三角形

  只能唯一地折成整数边直角三角形电线的最短长度是12厘米；除此之外，还有很多长度的电线都只能唯一地折成整数边的直角三角形，例如：
  12厘米: (3,4,5)
  24厘米: (6,8,10)
  30厘米: (5,12,13)
  36厘米: (9,12,15)
  40厘米: (8,15,17)
  48厘米: (12,16,20)
相反地，有些长度的电线，比如20厘米，不可能折成整数边的直角三角形，而另一些长度则有多个解；例如，120厘米的电线可以折成三个不同的整数边直角三角形。
  120厘米: (30,40,50), (20,48,52), (24,45,51)
  记电线长度为L，对于L ≤ 1,500,000，有多少种取值只能唯一地弯折成整数边直角三角形。

Python3解答

number = 1500000
fu = [0 for i in range(0, number + 1)]
count = 0
#辗转相除法计算最大公因数
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
for iii in range(2, int((number / 2) ** 0.5)):
    for jjj in range(1, iii):
        if (iii + jjj) % 2 == 1 and Euclidean(jjj, iii) == 1:
            ee = 2 * iii * jjj
            ff = iii ** 2 - jjj ** 2
            dd = jjj ** 2 + iii ** 2
            ssum = int(ee + dd + ff)
            if ssum < number:
                for jj in range(ssum, number, ssum):#所有解
                    fu[jj] += 1
            else:
                break
print(fu.count(1))#只有一种解的个数
答案：161667

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