p071.py 2.15 KB
Newer Older
1 2
# 
# Solution to Project Euler problem 71
3
# Copyright (c) Project Nayuki. All rights reserved.
4
# 
5
# https://www.nayuki.io/page/project-euler-solutions
6 7 8
# https://github.com/nayuki/Project-Euler-solutions
# 

9 10
import sys
if sys.version_info.major == 2:
11
	range = xrange
12

13

14 15 16
# We consider each (integer) denominator d from 1 to 1000000 by brute force.
# For a given d, what is the largest integer n such that n/d < 3/7?
# 
17
# - If d is a multiple of 7, then the integer n' = (d / 7) * 3 satisfies n'/d = 3/7.
18 19 20
#   Hence we choose n = n' - 1 = (d / 7) * 3 - 1, so that n/d < 3/7.
#   Since (d / 7) * 3 is already an integer, it is equal to floor(d * 3 / 7),
#   which will unifie with the next case. Thus n = floor(d * 3 / 7) - 1.
21
# - Otherwise d is not a multiple of 7, so choosing n = floor(d * 3 / 7)
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
#   will automatically satisfy n/d < 3/7, and be the largest possible n
#   due to the definition of the floor function.
# 
# When we choose n in this manner, it might not be coprime with d. In other words,
# the simplified form of the fraction n/d might have a denominator smaller than d.
# 
# Let's process denominators in ascending order. Each denominator generates a pair
# of integers (n, d) that conceptually represents a fraction, without simplification.
# Whenever the current value of n/d is strictly larger than the previously saved value,
# we save this current value of (n, d).
# 
# If we handle denominators in this way - starting from 1, counting up consecutively -
# then it is guaranteed that our final saved pair (n, d) is in lowest terms. This is
# because if (n, d) is not in lowest terms, then its reduced form (n', d') would have
# been saved when the smaller denominator d' was processed, and because n/d is
# not larger than n'/d' (they are equal), the saved value would not be overwritten.
# Hence in this entire computation we can avoid explicitly simplifying any fraction at all.
39
def compute():
40
	LIMIT = 1000000
41 42
	maxnumer = 0
	maxdenom = 1
43
	for d in range(1, LIMIT + 1):
44 45 46
		n = d * 3 // 7
		if d % 7 == 0:
			n -= 1
47
		if n * maxdenom > d * maxnumer:  # n/d > maxdenom/maxnumer
48 49 50 51 52 53 54
			maxnumer = n
			maxdenom = d
	return str(maxnumer)


if __name__ == "__main__":
	print(compute())