p071.py 2.15 KB
 Nayuki Minase committed Jul 26, 2015 1 2 ``````# # Solution to Project Euler problem 71 `````` Nayuki committed Dec 27, 2016 3 ``````# Copyright (c) Project Nayuki. All rights reserved. `````` Nayuki Minase committed Jul 26, 2015 4 ``````# `````` Nayuki Minase committed Feb 05, 2016 5 ``````# https://www.nayuki.io/page/project-euler-solutions `````` Nayuki Minase committed Jul 26, 2015 6 7 8 ``````# https://github.com/nayuki/Project-Euler-solutions # `````` Nayuki Minase committed Aug 13, 2015 9 10 ``````import sys if sys.version_info.major == 2: `````` Nayuki Minase committed Dec 09, 2015 11 `````` range = xrange `````` Nayuki Minase committed Aug 13, 2015 12 `````` `````` Nayuki Minase committed Jul 26, 2015 13 `````` `````` Nayuki committed Mar 08, 2018 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? # `````` Nayuki committed Mar 10, 2018 17 ``````# - If d is a multiple of 7, then the integer n' = (d / 7) * 3 satisfies n'/d = 3/7. `````` Nayuki committed Mar 08, 2018 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. `````` Nayuki committed Mar 10, 2018 21 ``````# - Otherwise d is not a multiple of 7, so choosing n = floor(d * 3 / 7) `````` Nayuki committed Mar 08, 2018 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. `````` Nayuki Minase committed Jul 26, 2015 39 ``````def compute(): `````` Nayuki committed Mar 08, 2018 40 `````` LIMIT = 1000000 `````` Nayuki Minase committed Jul 26, 2015 41 42 `````` maxnumer = 0 maxdenom = 1 `````` Nayuki committed Mar 08, 2018 43 `````` for d in range(1, LIMIT + 1): `````` Nayuki Minase committed Jul 26, 2015 44 45 46 `````` n = d * 3 // 7 if d % 7 == 0: n -= 1 `````` Nayuki committed Mar 08, 2018 47 `````` if n * maxdenom > d * maxnumer: # n/d > maxdenom/maxnumer `````` Nayuki Minase committed Jul 26, 2015 48 49 50 51 52 53 54 `````` maxnumer = n maxdenom = d return str(maxnumer) if __name__ == "__main__": print(compute())``````