问题 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 ----> 169871 ----> 45361 ----> 871872 ----> 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
来源: http://www.jianshu.com/p/e7db7125c148