题目71：将最简真分数按照升序排列

欧拉计划

Ordered fractions

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

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

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

题目：

考虑分数 n/d, 其中 n 和 d 是正整数。如果 n<d 并且最大公约数 HCF(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 左边第一个分数的分子是多少？

jerryxjr1220

1. i=428570, j=999997
   
2. [Finished in 0.1s]
   
3. 
   
4. most, mosti, mostj = 0,0,0
   
5. 
   
6. for j in range(1,1000001):
   
7.     i = j*3//7
   
8.     if i/j < 3/7:
   
9.         if most < i/j:
   
10.             most = i/j
    
11.             mosti = i
    
12.             mostj = j
    
13. print (f'i={mosti},j={mostj}')

复制代码

愤怒的大头菇

1. from fractions import Fraction
   
2. import math
   
3. def Prime(x):
   
4.     if x>1:
   
5.         if x==2:
   
6.             return True
   
7.         if x%2==0:
   
8.             return False
   
9.         for i in range(3,int(math.sqrt(x)+1),2):
   
10.             if x%i==0:
    
11.                 return False
    
12.         return True
    
13.     return False
    
14. def Dig(x):
    
15.     list1=[]
    
16.     if Prime(x):
    
17.         list1.append(x)
    
18.     else:
    
19.         for i in range(2,int(math.sqrt(x)+1)):
    
20.             if x%i == 0:
    
21.                 list1.extend([i,int(x/i)])
    
22.     return list1
    
23. def Hcf(x,y):
    
24.     if x!=y:
    
25.         if x==1:
    
26.             return True
    
27.         for each in Dig(y):
    
28.             if x%each == 0:
    
29.                 return False
    
30.         return True
    
31.    
    
32. list2 = [Fraction(1,7),Fraction(2,7),Fraction(3,8)]
    
33. for i in range(4,428571):
    
34.     y = int(7*i/3)+1
    
35.     while True:
    
36.         if Hcf(i,y):
    
37.             list2.append(Fraction(i,y))
    
38.             break
    
39.         else:
    
40.             y += 1
    
41. list2.sort()
    
42. print(list2[-1])

复制代码

结果：428570/999997
答案是428570

愤怒的大头菇

一如既往得慢

芒果加黄桃

1. # encoding:utf-8
   
2. # 最接近3/7的真分数   分母<1000000
   
3. from time import time
   
4. from math import sqrt
   
5. def getPrimes(n):
   
6.     primes = [True] * n
   
7.     primes[0], primes[1] = False, False
   
8.     for (i, prime) in enumerate(primes):
   
9.         if prime:
   
10.             for j in range(i * i, n, i):
    
11.                 primes[j] = False
    
12.     return [k for (k, v) in enumerate(primes) if v]
    
13. def findPrimeFactors(n, l_pr, s_pr):
    
14.     if n in s_pr:
    
15.         return [n]
    
16.     sqr_n = int(sqrt(n))
    
17.     result = list()
    
18.     for pr in l_pr:
    
19.         if n % pr == 0:
    
20.             result.append(pr)
    
21.             result.extend(findPrimeFactors(int(n / pr), l_pr, s_pr))
    
22.             break
    
23.         if pr > sqr_n:
    
24.             break
    
25.     return result
    
26. def euler071(N=1000000):
    
27.     l_primes = getPrimes(N)
    
28.     s_pr = set(l_primes)
    
29.     l_pr = [x for x in l_primes if x <= int(sqrt(N)) + 1]
    
30.     maxfz, maxfm = int(3 / 7 * N), N
    
31.     maxrt, a, b = 0, 0, 0
    
32.     for i in range(maxfz, 2, -1):
    
33.         for j in range(int(i * 7 / 3), maxfm):
    
34.             t = i / j
    
35.             if t < 3 / 7 :  # 满足题目条件
    
36.                 if t > maxrt:  # 比已找到的更接近3/7
    
37.                     s_i = set(findPrimeFactors(i, l_pr, s_pr))
    
38.                     s_j = set(findPrimeFactors(j, l_pr, s_pr))
    
39.                     if not(s_i & s_j):  # 没有公共的质数因子
    
40.                         maxrt, a, b = t, i, j  
    
41.                 else:
    
42.                     break         
    
43.     print(maxrt, a, b)
    
44. if __name__ == '__main__':
    
45.     start = time()
    
46.     euler071()
    
47.     print('cost %.6f sec' % (time() - start))
    

复制代码

0.42857128571385716 428570 999997
cost 1.133000 sec

najin

改写了一下，用的matlab，
成功解决
结果是
      428570      999997

时间已过 0.053004 秒。
>>

永恒的蓝色梦想

1. min_difference = 1
   
2. min_numerator = 0
   
3. three_div_seven = 3 / 7
   
4. 
   
5. 
   
6. for denominator in range(1000000, 0, -1):
   
7.     numerator = 3 * denominator // 7
   
8.     difference = three_div_seven - numerator / denominator
   
9. 
   
10.     if difference and difference < min_difference:
    
11.         min_difference = difference
    
12.         min_numerator = numerator
    
13. 
    
14. 
    
15. print(min_numerator)

复制代码

debuggerzh

428570

Process returned 0 (0x0)   execution time : 649.486 s
Press any key to continue.
效率极低……求指点

1. #include<algorithm>
   
2. #include<iostream>
   
3. #include<set>
   
4. using namespace std;
   
5. 
   
6. const int M = 1e5;
   
7. const double ub = 3.0/7;
   
8. int ct = 0;
   
9. bool prime[M];
   
10. int factor[M];
    
11. set<int> fac_n;
    
12. 
    
13. void euler_sieve(){
    
14.   prime[1] = false;
    
15.   for (int i = 2;i <= M;i++) prime[i] = true;
    
16. 
    
17.   for (int i = 2;i <= M;i++){
    
18.     if (prime[i]) factor[++ct] = i;
    
19.     for (int j = 1;j <= ct && i*factor[j] < M;j++){
    
20.       prime[i*factor[j]] = false;
    
21.       if (i % factor[j] == 0) break;
    
22.     }
    
23.   }
    
24. }
    
25. 
    
26. bool co_prime(int x,int y){//x < y
    
27.   if (x == 1) return true;
    
28.   if (prime[y]) return true;
    
29.   if (prime[x] && y % x)  return true;
    
30.   if (y == x*2 + 1) return true;
    
31. 
    
32.   for (set<int>::iterator it = fac_n.begin();it != fac_n.end();++it){
    
33.     if (y % *it == 0) return false;
    
34.   }
    
35.   return true;
    
36. }
    
37. 
    
38. void parse(int x,set<int> & s){
    
39.   for (int i = 1;x != 1;i++){
    
40.     int t = factor[i];
    
41.     while(x % t == 0) {s.insert(t); x /= t;}
    
42.   }
    
43. }
    
44. 
    
45. int main(){
    
46.   double lb = 1.0/3;
    
47.   int ans;
    
48.   euler_sieve();
    
49. 
    
50.   for (int d = 4;d <= M;d++){
    
51.     for (int n = 1;n < (d+1)/2;n++){
    
52.       double t = (double)n / d;
    
53.       if (lb < t && t < ub){
    
54.         fac_n.clear();
    
55.         parse(n,fac_n);
    
56.         if (co_prime(n,d) )  {lb = t; ans = n;}
    
57.       }
    
58.     }
    
59.   }
    
60.   cout << ans << endl;
    
61.   return 0;
    
62. }
    

复制代码

永恒的蓝色梦想

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. 
   
5. 
   
6. int main() {
   
7.     ios::sync_with_stdio(false);
   
8. 
   
9.     long double min_difference = 1, difference;
   
10.     unsigned long long denominator, result = 0, numerator;
    
11. 
    
12. 
    
13.     for (denominator = 1; denominator <= 1000000; denominator++) {
    
14.         numerator = 3 * denominator / 7;
    
15.         difference = 3.0L / 7 - (long double)numerator / denominator;
    
16. 
    
17.         if (difference && difference < min_difference) {
    
18.             min_difference = difference;
    
19.             result = numerator;
    
20.         }
    
21.     }
    
22. 
    
23. 
    
24.     cout << result << endl;
    
25.     return 0;
    
26. }

复制代码

debuggerzh

debuggerzh 发表于 2020-8-29 18:33
428570

Process returned 0 (0x0)   execution time : 649.486 s

第6行应该是1e6，调试忘记改了

debuggerzh

永恒的蓝色梦想 发表于 2019-8-4 09:47

感谢大神的思路！以下是改进版本：
428570

Process returned 0 (0x0)   execution time : 0.248 s
Press any key to continue.
只枚举分母，计算最接近结果的分子，大大减少循环次数

1. #include<algorithm>
   
2. #include<iostream>
   
3. #include<set>
   
4. using namespace std;
   
5. 
   
6. const int M = 1e6;
   
7. const double ub = 3.0/7;
   
8. int ct = 0;
   
9. bool prime[M];
   
10. int factor[M];
    
11. set<int> fac_n;
    
12. 
    
13. void euler_sieve(){
    
14.   prime[1] = false;
    
15.   for (int i = 2;i <= M;i++) prime[i] = true;
    
16. 
    
17.   for (int i = 2;i <= M;i++){
    
18.     if (prime[i]) factor[++ct] = i;
    
19.     for (int j = 1;j <= ct && i*factor[j] < M;j++){
    
20.       prime[i*factor[j]] = false;
    
21.       if (i % factor[j] == 0) break;
    
22.     }
    
23.   }
    
24. }
    
25. 
    
26. bool co_prime(int x,int y){//x < y
    
27.   if (x == 1) return true;
    
28.   if (prime[y]) return true;
    
29.   if (prime[x] && y % x)  return true;
    
30.   if (y == x*2 + 1) return true;
    
31. 
    
32.   for (set<int>::iterator it = fac_n.begin();it != fac_n.end();++it){
    
33.     if (y % *it == 0) return false;
    
34.   }
    
35.   return true;
    
36. }
    
37. 
    
38. void parse(int x,set<int> & s){
    
39.   for (int i = 1; ;i++){
    
40.     int t = factor[i];
    
41.     while(x % t == 0) {s.insert(t); x /= t;}
    
42.     if (x == 1 || prime[x]) break;
    
43.   }
    
44.   if (prime[x]) s.insert(x);
    
45. }
    
46. 
    
47. int main(){
    
48.   double lb = 1.0/3;
    
49.   int ans;
    
50.   euler_sieve();
    
51. 
    
52.   for (int d = 4;d <= M;d++){
    
53.     int n = (int)(d*3 - 1) / 7;
    
54.       double t = (double)n / d;
    
55.       if (lb < t && t < ub){
    
56.         fac_n.clear();
    
57.         parse(n,fac_n);
    
58.         if (co_prime(n,d) )  {lb = t; ans = n;}
    
59.       }
    
60.   }
    
61.   cout << ans << endl;
    
62.   return 0;
    
63. }
    

复制代码

永恒的蓝色梦想

debuggerzh 发表于 2020-8-30 11:26
感谢大神的思路！以下是改进版本：
428570

并不需要判断质数。

guosl

1. /*
   
2. 428570
   
3. 0.161768
   
4. */
   
5. #include <iostream>
   
6. #include <algorithm>
   
7. using namespace std;
   
8. 
   
9. int main(void)
   
10. {
    
11.   int n = 0, d = 1;
    
12.   for (int i = 2; i <= 1000000; ++i)
    
13.   {
    
14.     for (int j = (3 * i + 6) / 7; 999 * j >= 428 * i; --j)
    
15.     {
    
16.       if (7 * j >= 3 * i)
    
17.         continue;
    
18.       if (n*i < j*d)
    
19.       {
    
20.         n = j;
    
21.         d = i;
    
22.       }
    
23.     }
    
24.   }
    
25.   cout << n << endl;
    
26.   return 0;
    
27. }

复制代码

guosl

这道题我们先从数学上来讨论一下：对m<n的真分数，我们有以下事实：
1. m/n>m/(n+1)
2. m/n>(m-1)/n
3. m/n>(m-1)/(n-1)
4. m/(n+1) > (m-1)/n , m/(n+1) > (m-1)/(n-1) ,(m-1)/(n-1)>(m-1)/n。总结就是： m/n>m/(n+1) > (m-1)/(n-1)>(m-1)/n，当m/n=3/7时。
在本题中3/7=428571/999999，那么我们可以通过分母加1，分子减1，或分子与分母同时减1，或分子分母同时加1来调整与3/7的距离。但这些调整都预示着分子就在428571的附件，分母就在999999的附近。
为了省却调整的不确定性，我们干脆就在分母d是999990~1000000之间枚举，而分子就是428560~3*d/7之间枚举。

1. /*
   
2. 答案：428570
   
3. */
   
4. #include <iostream>
   
5. using namespace std;
   
6. 
   
7. int gcd(int x, int y)
   
8. {
   
9.   if (y == 0)
   
10.     return x;
    
11.   int z = x % y;
    
12.   while (z != 0)
    
13.   {
    
14.     x = y;
    
15.     y = z;
    
16.     z = x % y;
    
17.   }
    
18.   return y;
    
19. }
    
20. 
    
21. int main(void)
    
22. {
    
23.   int n0 = 0, d0 = 1;
    
24.   for (int d = 999990; d <= 1000000; ++d)
    
25.   {
    
26.     for (int n = 428560; 7 * n < 3 * d; ++n)
    
27.     {
    
28.       long long l1 = n0, l2 = d0;
    
29.       l1 *= d;
    
30.       l2 *= n;
    
31.       if (l1 < l2)
    
32.       {
    
33.         n0 = n;
    
34.         d0 = d;
    
35.       }
    
36.     }
    
37.   }
    
38.   cout << n0 / gcd(n0, d0) << endl;
    
39.   return 0;
    
40. }

复制代码

TLM

应该是测不到时间，毕竟连循环都没有

1. # 3/7约等于m/n
   
2. # 3n-7m=1 ==> 3/7=(m+1/7)/n
   
3. # 3n=7m+1 ==> 3n%7=1
   
4. # n%7=5
   
5. d=1000000
   
6. n=d//7*7+5
   
7. if n>d:
   
8.     n=n-7
   
9. m=(3*n-1)//7
   
10. print(m)

复制代码

salt_eto

本题等效于寻找n/m,使得3/7-n/m最小
3/7-n/m＝(３m-7n)/7m
使得分子＝１，m尽可能大即可
时间：<0.001ms

1. int test71 (int n)
   
2. {
   
3.     for (int i = n; i >0; i--)
   
4.     {
   
5.         if(i * 3% 7==1)
   
6.         return i * 3/ 7;
   
7.     }
   
8. }

复制代码

时空伴随者

1. if __name__ == '__main__':
   
2.     import datetime, time
   
3. 
   
4.     print(datetime.datetime.now().strftime('%F %T'))
   
5.     start = time.time()
   
6.     N = 1000000
   
7.     m = (N - 5) // 7
   
8.     print(f'Problem 71 : {m * 3 + 2}, {m * 7 + 5}')
   
9.     print("用时 %.6f 秒" % (time.time() - start))
   
10. 
    
11. 2024-04-23 21:32:18
    
12. Problem 71 : 428570, 999997
    
13. 用时 0.000000 秒

复制代码